ベスパリブ

プログラミングを主とした日記・備忘録です。ベスパ持ってないです。

Python: 切り捨てはmath.floor()より//演算子を使ったほうが良いかも

環境はPython3.6.5です。

まずは以下の計算結果を見てください。

gist.github.com

なぜ?

float型において、有効数字が16桁以上の値を表現しようとすると誤差が生じてしまう可能性があるからです。

N//3 のような整数同士の切り捨て除算は内部処理的にint型のまま演算されるので(たぶん)、誤差が発生しないのだと思います。

よって、整数同士の切り捨て除算の場合、//演算子を使ったほうが誤差が発生する可能性が低いので、そちらを使ったほうが良いかもしれません。

調査と解説

以下は、詳しい解説になります。

まず、//演算子とmath.floor()の違いというか、それぞれがどんなことをしているかというのを調査し、整理します。

//演算子

公式ドキュメントの二項算術演算の説明によれば、/(除算)および//(切り捨て除算)は次のようなことをしています。

/ (除算: division) および // (切り捨て除算: floor division) は、引数同士の商を与えます。数値引数はまず共通の型に変換されます。整数の除算結果は浮動小数点になりますが、整数の切り捨て除算結果は整数になります; この場合、結果は数学的な除算に 'floor' 関数 を適用したものになります。ゼロによる除算を行うと ZeroDivisionError 例外を送出します。

要約すると、次のようになります。

# 整数の除算結果は浮動小数点数
print(6/2)
# 3.0

# 整数の切り捨て除算結果は整数
print(6//2)
# 3

整数の切り捨て除算結果は整数」がミソで、じゃあfloat型の切り捨て除算結果の場合はどうなるかというと、

print(7.0//2)
# 3.0

float型になります。

math.floor()

次はmath.floor()についてですが、公式リファレンスのmath.floor()の説明によると以下のことが書いてあります。

math.floor(x)

x の「床」 (x 以下の最大の整数) を返します。 x が浮動小数点数でなければ、内部的に x._floor_() が実行され、 Integral 値が返されます。

引数 x が浮動小数点数でなければ、Integral値が返されるようです。Integral値についての説明は省くとして(あんまりわからないし)、要約するとint型に変換された値が返ってくると考えます。

ここでも「引数 x が浮動小数点数でなければ」という条件がついています。じゃあ浮動小数点数の場合はどうなるんだよという話ですが、見た目の挙動は触ってみた感じ変わりません(int型に変換されます)。内部的には知らないです。floor()の実装はたぶんここですが、数分ソースを追いかけたあと、眼鏡をクイッして終わりました。

これまでのことをまとめると、処理の流れは次のようになると思います。

  • b//a

    • b が整数ならば、整数が返る
    • b がfloat型ならば、float型が返る
  • floor(x)

float型の有効数字

Pythonのfloat型はC言語でいうところのdouble型(64bitの倍精度浮動小数点数1で、その有効数字は約16桁です(Wikipedia調べ)。

よって、有効数字が16桁以上の値を表現しようとすると誤差が生じてしまう可能性があります。これは演算させるさせないは関係ありません。

a = 9999999999999999.  # 有効数字16桁
print(a)
# 1e+16
print(f"{a:.10f}")
# 10000000000000000.0000000000

また、f-strings(フォーマット済み文字列リテラル)で出力するとき、float型に変換する処理をおこなうと、同様の理由で誤差が出ることがあるので注意しましょう。

a = 100000000000000000000
b = a//3
print(b)
# 33333333333333333333
print(f"{b:.10f}")  # floatに変換するので誤差が発生
# 33333333333333331968.0000000000
print(f"{b:18d}")
# 33333333333333333333

結論とまとめ

というわけで、途中の演算で有効数字が16桁以上のfloat型になると、誤差が生じる可能性が出てきます。

floor(N/3)について解説すると、

c = N/3       # この時点で有効数字16桁以上のfloat型になり、誤差が発生する
b = floor(c)  # 誤差が発生した値を切り捨て除算し、整数部を取り出す
print(b)
# 333333333333333312

N//3について解説すると、

a = N//3  # float()型に変換されることはないので、誤差は発生しない
print(a)
# 333333333333333333

ただし、float型の切り捨て除算は誤差が発生します。

N = 1000000000000000000.  # 10**18のfloat値
a = N//3  # 有効数字16桁以上のfloat型になり、誤差が発生する
print(a)
# 3.333333333333333e+17
print(f"{a:.10f}") 
# 333333333333333312.0000000000

以上の理由で、math.floor()演算子より、//演算子を使ったほうが良いと主張します。おわり。

おまけ1

AtCoder Beginner Contest 131: C - Anti-Divisionで、floor()を使うとWAになり、//演算子を使うとACになったのが調査のきっかけです。

# -*- coding:utf-8 -*-
"""解説
B以下の整数のうち、CでもDでも割り切れないものの個数をCountBとする
A以下の整数のうち、CでもDでも割り切れないものの個数をCountAとする
求める答えは、CountB - CountA
・CountBの求め方
B以下の整数のうち、Cで割り切れるものの個数はCountB_C = B//C
B以下の整数のうち、Dで割り切れるものの個数はCountB_D = B//D
B以下の整数のうち、CでもDでも割り切れるものの個数はCountB_CD = B//lcm(C,D)
CountB = B - (CountB_C + CountB_D - CountB_CD)
"""
from fractions import gcd
from math import floor

def solve():
    A, B, C, D = list(map(int, input().split()))
    def lcm(a, b):
        """ aとbの最小公倍数を返す """
        return a*b // gcd(a, b)

    def f(x):
        """ 1以上x以下の整数のうち、CでもDでも割り切れないものの個数を返す """
        #return x - (floor(x/C) + floor(x/D) - floor(x/lcm(C,D)))  # こっちだとWA
        return x - (x//C + x//D - x//lcm(C,D))  # こっちだとAC

    ans = f(B) - f(A-1)

    print(ans)


if __name__ == "__main__":
    solve()

おまけ2

追記2019/09/02

AtCoder Beginner Contest 139: D - ModSumでも似たような注意が必要です。

問題文と解説は省略しますが、要は 1~N-1 までの和を出力する問題です。

# -*- coding:utf-8 -*-

def solve():
    N = int(input())

    # O(N)じゃ間に合わない

    """
    i   = 1 2 3 4 5 6 7 8
    P_i = 2 3 4 5 6 7 8 1

    ↑これが最大値なのでは?
    つまり、
    ・P_i = i + 1
    ・P_N = 1
    にすると、1 ~ N-1の和が答えになる。
    """
    # N = 10**9-1
    ans = (1+(N-1))*(N-1)//2  # 整数同士の切り捨て除算(//)は浮動小数点数(float型)に変換されることはないので、誤差は発生しない
    # ans = int((1+(N-1))*(N-1)/2)  # 除算(/)の結果はfloat型に変換されるので、誤差が発生しうる(N = 10**9-1で誤差が発生する)
    print(ans)

if __name__ == "__main__":
    solve()