PythonのisqrtをGoで実装｜整数平方根を誤差なく求める方法

Aru

浮動小数点演算には精度誤差がつきもので、特に平方根のような計算では、結果を整数に丸める際に意図しない誤差が発生することがあります。Pythonではこうした問題を避けるために math.isqrt() という便利な関数が標準で用意されています。本記事では、Pythonの isqrt 関数と同等の関数をGo言語で実装してみました。

Contents

はじめに
ニュートン法（Newton-Raphson法）
Go言語のプログラム
まとめ

はじめに

Go言語で y := int(math.Sqrt(x)) と書くと、一見して「x の平方根を整数に丸めた値が得られる」ように見えますが、実際には浮動小数点演算による誤差の影響で、意図しない値になることがあります。

私自身、AtCoderのABCコンテスト400のC問題を解いた際に、この演算誤差の罠にハマり、正しいはずのコードが通らないという経験をしました。Pythonではこうした問題に対処するために math.isqrt() という整数平方根を求める関数が用意されており、これを使えば誤差の心配なくACできます。

本記事では、Pythonの isqrt 関数と同等の処理をGo言語で実装し、$\lfloor \sqrt(x) \rfloor$を正しく計算する関数を作成してみます。

簡単に調べられる範囲$10^8$程度の範囲では、誤差が問題な値を見つけられませんでした。調べてみたところ、$2^{52}+2^{27}$という値が誤差の出る数値だそうです。

以下のプログラムで確認済み

import math

x = 2**52 + 2**27

print(int(math.sqrt(x))) # 67108865
print(math.isqrt(x)) # 67108864

参考URL（Qiita）: [Python]平方根の誤差

ニュートン法（Newton-Raphson法）

ニュートン法（正式には Newton-Raphson法）は、ある関数の根（= 0 になる点）を数値的に求める反復法です。

ある関数$f(x)$に対して、

$$f(x) = 0$$

となるような$x$を求める、つまり「方程式の解の近似を求める」のがこの方法です。

🔁 アルゴリズムの基本式

初期値 x0x_0x0 を決めて、以下の式で値を繰り返し更新していきます。

$$
x_{n+1} = x_n – \frac{f(x_n)}{f'(x_n)}
$$

ここで、$f′(x_n)$は$f(x)$ の微分です。

この式は、点$x$における接戦がx軸と交わる点を次の値として近似していくものです。

この操作を繰り返して行うことで、解に徐々に近づいていきます。

🔢 平方根（√n）を求める場合に応用する

平方根を求める場合、まず、$x^2 = n$という式を考えます。この式は次のように変形することができます。

$$
f(x) = x^2 – n = 0
$$

この関数$f(x)$にニュートン法の式を適用すると、以下になります。

$$
x_{n+1}=x_n – \frac{f(x_n)}{f'(x_n)} = x_n−\frac{x_n^2 – n}{2x_n}
$$

これを整理すると、以下になります。

$$
x_{n+1} = \frac{x_n + \frac{n}{x_n}}{2}
$$

したがって、$x_{n+1}$が変化しなくなるまで繰り返すと平方根が求まります。

上記の式は、非常に効率よく収束するらしいです

Go言語のプログラム

先ほど説明したニュートン法のアルゴリズムを、Go言語で実装すると次のようになります。

func isqrt(n int) int {
	if n == 0 || n == 1 {
		return n
	}
	x := n
	y := (x + 1) / 2
	for y < x {
		x = y
		y = (x + n/x) / 2
	}
	return x
}

この実装では、浮動小数点演算を一切使わず、すべて整数演算のみで $\lfloor \sqrt{n} \rfloor$ を計算しています。つまり、int(math.Sqrt(float64(n)) のような浮動小数点演算に起因する誤差を回避することができます。

実装したiqrtの特徴

浮動小数点誤差なし
誤差を発生させずに、 $\lfloor \sqrt{n} \rfloor$ を計算可能

まとめ

AtCoder ABC400 の C 問題を解いているとき、int(math.Sqrt(...)) を使っていたせいで微妙な誤差にハマってWAを量産してしまいました。Python には math.isqrt() があり、このような問題を簡単に回避できますが、Go には標準でそのような関数は用意されていません。

そこで、 整数演算だけで平方根の切り捨てを正確に求める isqrt 関数 を Go 言語で実装してみました。

$10^7$くらいまでは問題ないので、math.Sqrtの誤差が問題になるとは思っていませんでした。今後は気をつけたいです。

#sqrt #誤差