a%b=0なるa,bに対するa//bとint(a/b)の違いとは?

Question

#問題

AtCoder ABC185 C問題より

#方針
(L-1)C(11)を出力すれば良いのは一目瞭然です。

#WAコード

L = int(input())

from math import factorial

ans = factorial(L - 1) / (factorial(L - 12) * factorial(11))

print(int(ans))

#ACコード

L = int(input())

from math import factorial

ans = factorial(L - 1) // (factorial(L - 12) * factorial(11))

print(ans)

#質問
今回の問題の範囲で、factorial(L-1)はfactorial(L-12)*factorial(11)で割り切れることは保証されますので、(L-1)C(11)の値はどうあがいても整数です。従って、割り算の結果をint型に切り替えておけば十分であろうと考えましたが、Wrong Answerが表示されました。一方、//で商を求めるという形では、Acceptedが表示されました。浅学な自分にとっては両者は同じではないのだろうか？と考えましたが、どのような違いで正解不正解の差が上記2コードで出たのでしょうか。素人質問で恐縮ですが、ご教授お願い申し上げます。

Answer 1

なお、この問題の制約下で答えは2**63未満

一般的なPythonで使われる浮動小数点数は、整数についても2の53乗までしか正確な値を保証できません（仮数部が53ビットしかありません）。絶対値がそれより大きな整数を浮動小数点数にした場合、近い値に丸められる可能性があります。

Comments

[kay_ventris4]

初めて知りました。その為//を使って浮動小数点の議論の介入の余地を与えないことが重要なのですね。
ご丁寧にありがとうございました。

Answer 2

Pythonの/演算子の結果はfloat(64ビット浮動小数点数)です。これは結果が数学的に整数であるかに関係なくfloatになります。

floatの有効桁数はintより少ないので、結果が大きくなるとintより不正確になります。

実際に確かめてみます。

from math import factorial

for L in range(12,200):

    ans1 = int( factorial(L - 1) / (factorial(L - 12) * factorial(11)) )
    ans2 = factorial(L - 1) // (factorial(L - 12) * factorial(11))
    if ans1 != ans2:
        print((L,ans1,ans2))

(156, 21616536107173176, 21616536107173175)
(158, 25008606629045128, 25008606629045130)
(160, 28877836722507436, 28877836722507435)
(164, 38292619070202592, 38292619070202588)
(168, 50419551102990880, 50419551102990876)
(172, 65942612131162224, 65942612131162221)
...(省略)

と大きい値で結果が異なっていることがわかります。

Comments

[kay_ventris4]

確かにLが大きくなるとint()による丸めが雑になってきていますね。
この為//で浮動小数点の誤差を考えないようにしているということでしたか。
大変勉強になりました。ありがとうございます。