(2024/01/25 追記)
この記事で紹介している方法は整数の除算でのみ適用できる考え方でしたが，小数であっても使えるかのような内容になってしまっていましたので記事に修正を加えました．
@fujitanozomuさん，ご指摘ありがとうございました。
はじめに
この記事は、一関高専Advent Calender2023 25日目の記事です。
こんにちは。
最近競技プログラミングをやり始めたのですが、今まで特に気にしていなかった計算量や低レイヤ－での実装なんかも気にする必要があって、大変ですが、とてもいい勉強になります。
今回はそんな中でも私が苦しめられた、pythonでの除算の切り上げ切り捨ての書き方について書いていきたいと思います。
ちなみにここで言う切り上げ切り捨てはそれぞれ以下のことを指します。
- 切り上げ: 正の無限大への丸め
- 切り捨て: 負の無限大への丸め
目次
結論
早速ですが誤差が出る間違った書き方と正しい書き方を書いておきます
ここではAをBで割ることを考えます
間違った方法
import math
# 切り上げ
math.ceil(A / B)
# 切り捨て
math.floor(A / B)
正しい方法
# 切り上げ
(A + B - 1) // B
# 切り捨て
A // B
何が問題？
実際に例とともに問題点を見てみましょう
上記の方法の実行結果を比較します．
A = 1040302749724122076
B = 23879
import math
# 切り上げ
print(math.ceil(A / B))
# 43565591093602
# 切り捨て
print(math.floor(A / B))
# 43565591093602
# 切り上げ
print((A + B - 1) // B)
# 43565591093602
# 切り捨て
print(A // B)
# 43565591093601
このように結果が変わってしまいます．
そこで，除算の部分の実行結果を見てみます
A = 1040302749724122076
B = 23879
print(A / B)
# 43565591093602.0
print(A // B)
# 43565591093601
一見，きれいに割り切れているようにも見えますが，そうではないことがわかります．さらに以下のようなサイトなどで実行してみるとこのような結果が得られます
以上のことから，問題のある方法では，最初の除算と，そのあとの，切り上げ切り捨てという２回の丸めが行われていることがわかります．
考え方
では２つ目の方法がなぜ正しいのかを考えていきます．
正しい証明など気になる方は各自で調べてみてください．
今回の問題点は，2回丸めが行われることでした．
なので，最初の計算の段階で丸めてしまえば問題ないです。
この時切り捨てに関しては、以下の通り、すでにpythonの演算子が用意されています
A // B
では切り捨てはどうすればいいのか?答えは切り捨てを使って、切り上げを表現します。
それが上記の式(A + B - 1) // Bです.
なぜ、これが成り立つのかを考えます。
まずA / Bをあまり付きで考えてみます
商をrとして次のパターンに分けられます
A / B = r 余り 0A / B = r 余り 1-
A / B = r 余り 2
~~ A / B = r 余り r-3A / B = r 余り r-2-
A / B = r 余り r-1
上の式を切り上げる場合、最初のパターンを除いて、r+1になります。
これらの式を元に(A + B - 1) // Bを同様に考えてみます.
A / B = r 余り B - 1A / B = r+1 余り 0-
A / B = r+1 余り 1
~~ A / B = r+1 余り r-4A / B = r+1 余り r-3A / B = r+1 余り r-2
すると最初の場合以外に1が足される形になりました。
こうすることで、切り捨てで切り上げを表現できるようになったので、誤差なく切り捨てと切り上げをできるようになりました。