[Python]割り算の商の誤差

はじめに
まとめ
検証
おまけ： Decimalくんの限界

はじめに

Pythonはintにどれだけ大きい数を入れてもオーバーフローしない。

（一般的な他の言語は、int型の符号付き32bitの場合、+2,147,483,647～-2,147,483,648の範囲を超える値を格納しようとした際に発生。大体、21億円超えたぐらいから注意）

Pythonの整数型はどのように実装されているのか

しかし、Pythonは大きなintの割り算の商を計算したときに、誤差が出る。

int(10 ** 20 / 1 ) == 10 ** 20　は当たり前にTrueだが、

int(10 ** 30 / 1 ) == 10 ** 30　はFalseになる。謎み

誤差がないようにするには、切り捨て除算を使ったり、Decimalを使ったりするっぽい

小数計算の誤差とDecimal関数による対応

Pythonでは小数点以下の数値をの計算をすると、誤差が生じてしまいます。正しく計算するときにはDecimal関数を使います。Decimal関数ではgetcontext().precを使うと有効桁数を自由に設定することができます。

　今回は幾つぐらいの計算で誤差が出るのかと、その対策法を適当にまとめた。

まとめ

とりま、AtCoderとかで大きなint型を使う除算の商だけ求めたい時は、切り捨て除算: M // Nを使おう。

なんか、切り捨て除算は浮動小数点を経由しないぽい。

誤差の深掘りについては、気が向いたらやるかも…?

検証

以下の４種類の手法で、 $10 ^ n \div 1$ を $1 <= n <= 100$ まで計算する

int(10 ** n / 1)
10 ** n // 1
math.floor(10 ** n / 1)
int(Decimal(10 ** n) / Decimal(1))

import math
from decimal import Decimal

def test(M: int, digit: int):
    N = 1
    print("Test: ", M, "**", digit)
    M = M ** digit

    normal_div = int(M / N)
    print("通常の除算: int(M/N)", normal_div, normal_div == M)

    ceil_div = M // N
    print("切り捨て除算: M//N ", ceil_div, ceil_div == M)

    math_floor_div = math.floor(M / N)
    print("math.floor使用: math.floor(M/N)", math_floor_div, math_floor_div == M)

    decimal_div = int(Decimal(M)/Decimal(N))
    print("Decimal使用: int(Decimal(M)/Decimal(N))", decimal_div, decimal_div == M)

    print("---------------------")

for digit in range(1, 101):
    test(10, digit)

# 出力結果

# ...
# ---------------------
# Test:  10 ** 22
# 通常の除算: int(M/N) 10000000000000000000000 True
# 切り捨て除算: M//N  10000000000000000000000 True
# math.floor使用: math.floor(M/N) 10000000000000000000000 True
# Decimal使用: int(Decimal(M)/Decimal(N)) 10000000000000000000000 True
# ---------------------
# Test:  10 ** 23
# 通常の除算: int(M/N) 99999999999999991611392 False
# 切り捨て除算: M//N  100000000000000000000000 True
# math.floor使用: math.floor(M/N) 99999999999999991611392 False
# Decimal使用: int(Decimal(M)/Decimal(N)) 100000000000000000000000 True
# ---------------------
# ...
# ---------------------
# Test:  10 ** 100
# 通常の除算: int(M/N) 10000000000000000159028911097599180468360808563945281389781327557747838772170381060813469985856815104 False
# 切り捨て除算: M//N  10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 True
# math.floor使用: math.floor(M/N) 10000000000000000159028911097599180468360808563945281389781327557747838772170381060813469985856815104 False
# Decimal使用: int(Decimal(M)/Decimal(N)) 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 True
# ---------------------

$10 ^ {23} \div 1$ あたりで、

int(M / N)
math.floor(M / N)

で誤差が発生.

とりあえず、 $10 ^ {100} \div 1$ まで

切り捨て除算：M // N

Decimal除算：int(Decimal(str(M))/Decimal(str(N)))

はOK

おまけ： Decimalくんの限界

切り捨て除算は、 $10 ^ {1000000} \div 1$ までは確認。この辺りから少し出力が遅くなる。

多分、計算資源と時間があれば、無限にOKのはず。

print(10 ** (10 ** 5) // 1 == 10 ** (10 ** 5))
# True
print(10 ** (10 ** 6) // 1 == 10 ** (10 ** 6))
# True

Decimalは $10 ^ {100000} \div 1$ まで、OKだが、 $10 ^ {1000000} \div 1$ でdecimal.Overflow

割り算の誤差とかでなく、純粋にDecimalくんのオーバーフロー

print(int(Decimal(10 ** (10 ** 5))/Decimal(1)) == 10 ** (10 ** 5))
# True
print(int(Decimal(10 ** (10 ** 6))/Decimal(1)) == 10 ** (10 ** 6))
# Traceback (most recent call last):
#   File "/Users/test.py", line 59, in <module>
#     print(int(Decimal(10 ** (10 ** 6))/Decimal(1)) == 10 ** (10 ** 6))
#               ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
# decimal.Overflow: [<class 'decimal.Overflow'>]

宇宙とか、素粒子レベルで生活している人でなければ、大丈夫か