python：x=9^n A=log[9]xの場合、なぜn=5だけがA=4.999・・・なのでしょうか

Question

前提・実現したいこと

初めてなのでどうかお手柔らかにお願いします。

pythonにて
『AtCoder Beginner Contest 099のC - Strange Bank』に挑戦していたのですが、テストケースの『04.txt』だけなんどやっても『WA』となります。

発生している問題・エラーメッセージ

特になし

該当のソースコード

import math


def chmin(G, i, new):
    if new < G[i]:
        G[i] = new


N = int(input())
a = math.floor(math.log(N, 6))
b = math.floor(math.log(N, 9))
A = [6 ** c for c in range(1, a+1)]
B = [9 ** d for d in range(1, b+1)]
C = [1] + A + B
dp = [N] * 200000
dp[0] = 0
for x in range(N):
    for y in C:
        chmin(dp, x + y, dp[x] + 1)
print(dp[N])

試したこと

どうやら「9^5の49059」だけがエラーになっている様です。
6^5の7776や
9^4の6561、
9^6の531441
は問題ないみたいなのですが、9^5だけがダメです。

そこで順番に出力してみたのですが、

import math
A = [9 ** a for a in range(10)]
b = [math.floor(math.log(i, 9)) for i in A]
print(b)
# [0, 1, 2, 3, 4, 4, 6, 7, 8, 9]

となり、

A = [9 ** a for a in range(10)]
b = [(math.log(i, 9)) for i in A]
print(b)
# [0.0, 1.0, 2.0, 3.0, 4.0, 4.999999999999999, 6.0, 7.0, 8.0, 9.0]

となってしまいます。なぜ５だけ？？と困っています。
もしかすると２進数とかの兼ね合いで起きてしまうのかなぁとも思うのですが。
そこで解決策というか、「こういう時には対数を使ってはいけない」とか作法があるなら教えていただきたいところです。どうぞよろしくお願いします。
（あと質問の仕方が間違っていたら、それも教えてほしいです。）

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Answer 1

この場合整数で回答することを求められており途中で小数が混入することは考慮されていません。対数の考え方は大雑把に言えば指数の逆であったはずです。つまり整数の割り算を繰り返すことによって対数と同様の計算が整数のみで可能なはずです。解説にもあるとおり単純なループと整数の計算のみで実装されています。

小学生に算数を教えていた頃はよく言っていたものでした。「円が小数になるのはおかしいだろ？」と。というわけで問題から意図を読み取って果たして小数が許される問題なのか判断しましょう。

Comments

[hanshinyuusyou]

ありがとうございます！
整数の問題に小数が発生するやり方では歪みがでますよね・・・
[9 ** n for n in range(10) if 9 ** n <= N]
N以下での９のn乗のリストにしてみたらうまくいきました！

Answer 2

２進数とかの兼ね合いで起きてしまう

方向性としては合っています。
簡潔に言うと、コンピュータでは2進数の浮動小数点数が広く使われており、小数や非常に大きい数などは基本的には正確に表せないので、そのような数が計算の中で出てくると誤差が出ます。

「こういう時には対数を使ってはいけない」とか作法

2進浮動小数点数で表せない数、たとえば0.1などの小数が計算途中で出てくるような計算は、厳密な解が欲しいときには使ってはいけません。
今回の問題ですが、コンピュータで普通に扱える対数は底が2と10とeくらいで、任意の底の対数は扱えません。それ以外の底を扱う時はたぶん「ln n/ln m」のような計算を行っているはずです。試しに(JavaScriptで)Math.log(9**i)/Math.log(9)を計算すると同様にn=5,10,13,15で誤差が出ました。(なお17以上は9^nが正確に表せない)

Comments

[actorbug]

Pythonの公式ドキュメントに、log(x)/log(base)で計算していると書いてありますね
https://docs.python.org/ja/3/library/math.html#math.log

[hanshinyuusyou]

なんと丁寧な回答をありがとうございます！
整数→対数をとる→累乗、ならば誤差が出るのはわかるのに、
整数→累乗→対数をとる、なのに何故誤差が出るのだ？？と悩んでました。恐らくこの発想自体が「人間が計算している」からなのですね。

log(x)/log(base)なら確かに出ますね。裏側ではそんな風に計算しているのですね。勉強になりました！厳密解が必要な場合は注意します。

Answer 3

rangeの値を増やしてみると分かりますが、「5だけ」ではなく、10, 13, 15, 17, ………と同じ状態(丸め誤差)が発生します。

これは浮動小数点数で実数表現する上で避けられないので、今回のように近傍の整数値が必要なのであれば、math.floorではなく、小数点以下1位で四捨五入してから整数化してください。

-b = [math.floor(math.log(i, 9)) for i in A]
+b = [int(round(math.log(i, 9), 1)) for i in A]

Answer 4

別に対数に限った話ではありません。

>>> print((1.0/49)*49)
0.9999999999999999

答えが整数であることがわかっているときは、小数点以下を四捨五入すればいいのですが、一般的には避ける方法はありません。

これはpythonの問題ではなく、C/C++などを使っても同じです。