はじめに
こんにちは。エンジニアを目指す大学3年生です。
AtCoder 「競プロ典型 90問」の22問目
を解いていて、
int(a/b)とa//bの違いで
WAとACが変わったことに衝撃を受けたので、
その違いについて調べました。
結論、
「a/bはfloatを返し、a//bはintを返す」ことにより、
オーバーフローが発生するかどうかの違いでした。
気づいた背景
「競プロ典型 90問」の22問目を解いていて、
※この記事では問題は省略します。
下のコードではうまく行かず
022_cubic_cake.py
import math
a, b, c = map(int, input().split())
gcd = math.gcd(a, b)
gcd = math.gcd(gcd, c)
# 1000000000000000000 999999999999999999 999999999999999998 の場合
# gcd == 1 になる
a = int(a/gcd) - 1
b = int(b/gcd) - 1
c = int(c/gcd) - 1
print(a+b+c)
ターミナル
% python3 022_cubic_cake.py
1000000000000000000 999999999999999999 999999999999999998
2999999999999999997
下のコードではうまくいきました。
022_cubic_cake.py
import math
a, b, c = map(int, input().split())
gcd = math.gcd(a, b)
gcd = math.gcd(gcd, c)
# 1000000000000000000 999999999999999999 999999999999999998 の場合
# gcd == 1 になる
a = a//gcd - 1 # 上との違いはここだけ
b = b//gcd - 1 # 上との違いはここだけ
c = c//gcd - 1 # 上との違いはここだけ
print(a+b+c)
ターミナル
% python3 022_cubic_cake.py
1000000000000000000 999999999999999999 999999999999999998
2999999999999999994
なんで？
と純粋に疑問に思ったのが、int(a/b)とa//bの違いに気づいた背景です。
普段、どっちも同じだと信じて使っていたので衝撃でした...。
２つの違い
以下のpythonのドキュメントを見ると
- intは精度の上限がない。
- floatはCのdoubleで実装されている。
ことが分かります。
また、以下のドキュメントを見ると
floatでは、数字を決めるのは53ビットであることが分かります。
53ビットを超える数は近似されるので、
この問題は正しく結果を出せなかったのだと理解できました。
実際、今回扱った数字は53ビット以上でした。
% python3
>>> 2**53<1000000000000000000
True
つまり、２つの違いは、
精度に上限があるかどうか
であることが分かります。
具体的には、intには精度の上限はなく、floatは53ビットという上限がありました。
まとめ
整数（int）は精度に上限がないことは驚きでした...！
これからは、int(a/b)は極力避け、a//bを使おうと思います。
また、今後もプログラミングをする中で
気づいたことは積極的にアウトプットしていきたいです。