GCが標準で備わっていてかつ高速な言語を使えるようになりたいと思い、Goに入門。公式のチュートリアル「A Tour of Go」を読み進めています。その中に練習問題がいくつか用意されています。当記事は、関数に関する練習問題「Exercise: Loops and Functions」を解いた記録です。
コード
package main
import (
"fmt"
)
func Sqrt(x float64) float64 {
z := 1.0
for i := 0; i < 10; i++ {
z -= (z*z - x) / (2 * z)
}
return z
}
func main() {
fmt.Println(Sqrt(2))
}
解説
コード
用意された関数を任意回ループするだけなので簡単です。このアルゴリズムはA Tour of Go で紹介されている通り、「ニュートン法」に基づくものです。
ニュートン法
ニュートン法は以下の式で与えられ、近似的に解を導出できます。
x_{n+1} = x_{n} - \frac{f(x)}{f'(x)}
今回求めるxの平方根をzとします。すると考えればよい関数が以下に定まります。
f(z) = z^{2} - x
zはxの平方根なので
z^{2}=x
すなわち
z^{2} - x = 0
となるようにしたいわけです。つまり
f(z) = 0
ですから、これはf(x)の解に他なりません。
f(x)の一階微分f'(x)を導出しておきましょう。
f'(x) = 2z
少し手計算してみます。A Tour of Goにある通り
z_{0} = 1.0
とします。
\begin{align}
z_{1} &= z_{0}-\frac{f(z_{0})}{f'(z_{0})}\\
&=1.0 - \frac{-1}{2}\\
&=1.5
\end{align}
\begin{align}
z_{2} &= z_{1}-\frac{f(z_{1})}{f'(z_{1})}\\
&=1.5 - \frac{0.25}{3}\\
&≒1.416666666
\end{align}
第3項目で小数点第2位まで期待の値になりました。
最後に
コード自体は簡単でしたが、ニュートン法はそれなりに高度なアルゴリズムみたいです。次元次数共に２なので簡単？でしたが、もっと高次元にも適用できるようです。