[Python]平方根の誤差

概要

ABC191 D - Circle Lattice Points で平方根を求める際に、浮動小数点数を返す sqrt は正方向に $1$ 以上の誤差を持つことがあり WA であった。
整数 $n$ に対して $a^2 \le n$ を満たす最大の整数 $a$ を得るには、int(sqrt(n)) ではなく isqrt を使うと良い。

検証

手軽に計算可能な $1 \le n \le 10^7$ の範囲では int(sqrt(n)) != isqrt(n) である $n$ は見つからなかった。
調べたところ $2^{52}+2^{27} = 4,503,599,761,588,224$ が条件を満たす最小の数だそう。

FWIW, assuming IEEE 754 semantics (with C's double matching IEEE 754's binary64), the smallest n for which int(math.sqrt(n)) doesn't give the right result is n = 252 + 227
Exactness of integer square root in Python - Stack Overflow

n = 2**52 + 2**27
print(int(sqrt(n)), isqrt(n))
# 67108865 67108864

今回の問題の制約内では、 $|X| \le 10^5$ かつ、小数第 4 位を整数として扱うと $(10^9)^2=10^{18}$ の平方根を求めることがあり、この誤差を考慮する必要がある。

なお、$n$ がさらに大きくなると 1 < int(sqrt(n)) - isqrt(n) となることにも注意したい。たとえば

n = 2**109
print(n, int(sqrt(n))-isqrt(n))
# 649037107316853453566312041152512 2

参考

math --- 数学関数 — Python 3.9.1 ドキュメント