用牛顿法实现平方根函数

我按照 Go 指南 实现了一个平方根函数:用牛顿法实现平方根函数。

计算机通常使用循环来计算的平方根。从某个猜测的值开始,我们可以根据的近似度来调整,产生一个更好的猜测。这里有一个牛顿法的动画演示可以在 GeoGebra 找到。

我们将估计值与目标的距离变化表示为函数,计算出点和切线斜率,然后由点斜式计算切线和轴的交点

重复调整的过程,猜测的结果会越来越精确,得到的答案也会尽可能接近实际的平方根。

在提供的 func Sqrt 中实现它。无论输入是什么,对的一个恰当的猜测为 1。 要开始,请重复计算 10 次并随之打印每次的值。观察对于不同的值(1、2、3 ...), 你得到的答案是如何逼近结果的,猜测提升的速度有多快。

exercise-loops-and-functions.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package main

import (
"fmt"
"math"
)

func Sqrt(y float64) float64 {
x, loop := y, 1
for math.Abs(x*x-y) > 1e-12 {
x -= (x*x - y) / (2 * x)
fmt.Println("loop", loop, "x =\t", x)
loop++
}
return x
}

func main() {
fmt.Println("my sqrt:\t", Sqrt(2))
fmt.Println("math.Sqrt:\t", math.Sqrt(2))
}

然后,修改循环条件,使得当值停止改变(或改变非常小)的时候退出循环。观察迭代次数大于还是小于 10。 尝试改变的初始猜测,如。你的函数结果与标准库中的 math.Sqrt 接近吗?

最后的结果是,上面的循环跑了五次才能达到 math.Sqrt 的精度。显然我的写的代码效率更低,因为这里不仅做了一些无用的算数还调用了库函数,浪费了宝贵的计算资源。

关于 math.Sqrt 是如何实现的?可以看到 src/math/sqrt.go,它不仅处理了一些特殊情况(NaN0Inf)、大量应用了移位操作(<<>>)还指导你使用硬件 sqrt 指令。