doubleの罠?
Project Euler Problem 210をJavaで解いていて、方法はあってるはずのにどうして解けてないかなーって思ったら次のところがまずかったらしい。Dはlong型で、かなり大きい(10^17程度)値。
long sqd = (long)Math.sqrt(D); if(sqd * sqd == D)sqd--;
sqrtした時点でdouble型になって精度的に問題が出る(丸め誤差かな)範囲なので、上のようにしたがこれではだめらしい。
ぐぐってでた正解らしきコードはこんな感じに書いてた。実際これであっていた。
long sqd = (long)Math.ceil(Math.sqrt(D))-1
書き方うまいなーとおもいつつも、どうにも腑に落ちないので、並行して計算させ異なるところを列挙させたところ、
D=10656292301203759のときに、√D=103229318.9999999903・・となって、
上の方のコードではなぜか値が繰り上がってsqd=103229319になってしまうらしい。何たる理不尽。
つまり、次のように書けばいいということだ。
long sqd = (long)StrictMath.sqrt(D); if(sqd * sqd >= D)sqd--;
やっぱり腑に落ちねぇ!