AtCoderのABC165 B問題「1%」のオーバーフローについて

Question

前提・実現したいこと

AtCoderのABC165 B問題でオーバーフローが発生する理由（原理など）を知りたいです。

発生している問題・エラーメッセージ

積を求めるやり方ではテストケース「99-after-contest-01.txt」でWAとなってしまいました。

while (yokin < X) {
        t++;
        yokin *= 1.01;
    }

一方、除算を行って足し合わせる以下のコードではうまく行きました。

while (yokin < X) {
        t++;
        yokin += yokin/100;
    }

どんな入力でオーバーフローが発生したのか見当がつきません。オーバーフローについて検索してみたのですが、同様のケースが見つからず、よくわかりませんでした。
前者のコードにおけるオーバーフローが具体的にどんな場合について、どのような原理で発生するのか、教えていただけないでしょうか。

Comments

[maai]

yokinの型はdoubleですか？long longですか？

[marronnier]

yokin、Xともにlong longです。記入忘れていました。すみません。

Answer 1

オーバーフローではなく丸め誤差でしょう

long long int a = 999999999999999999; //10^18 - 1
long long int b = a;
a += a / 100; //=> 1009999999999999998(正しい)
b *= 1.01; //=> 1010000000000000000(間違ってる)

浮動小数点型だと倍精度でも15桁ほどの精度しか出ないので、こういう大きな数を扱う場合は浮動小数点を使ってはいけません。

Comments

[marronnier]

そういうことだったんですね！
試しにyokinの値が異なる箇所を出力してみたところ、合点が行きました。
ありがとうございます。これからこのような誤差が出ないように気をつけます！

Answer 2

前者のコードでのyokinがdoubleなどの実数型であるなら、条件である「小数点以下切り捨て」に合わなくなります。後者が整数での除算をしているなら、この条件は満たされます。

Comments

[marronnier]

情報が足らずすみません、どちらもlong long型です。