go二分法和牛顿迭代法求平方根

二分法

  • 求根号5
  • 折半:5/2=2.5
  • 平方校验: 2.5*2.5=6.25>5,并且得到当前上限2.5
  • 再次向下折半:2.5/2=1.25
  • 平方校验:1.25*1.25=1.5625<5,得到当前下限1.25
  • 再次折半:2.5-(2.5-1.25)/2=1.875
  • 平方校验:1.875*1.875=3.515625<5,得到当前下限1.875

牛顿迭代法

newton
可以理解函数f(x) = x²,使f(x) = num的近似解,即x² - num = 0的近似解。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package main
import (
"fmt"
"math"
)
func NewtonSqrt(num float64) float64 {
x := num / 2.0
var y float64 = 0
count := 1
for math.Abs(x-y) > 0.00000001{
// fmt.Println(count, x)
count += 1
y = x
x = (1.0/2.0)*x+(num*1.0)/(x*2.0)
}
return x
}
func BinarySqrt(num float64) float64 {
y := num/2.0
low := 0.0
up := num
count := 1
for math.Abs(y * y - num) > 0.00000001{
// fmt.Println(count, y)
count += 1
if y*y > num{
up = y
y = low+(y-low)/2
}else{
low = y
y = up-(up-y)/2
}
}
return y
}
func main() {
fmt.Println("math sqrt", math.Sqrt(5))
fmt.Println("Newton sqrt", NewtonSqrt(5))
fmt.Println("binary sqrt", BinarySqrt(5))
}

精度0.00000001,在亿分之一;
二分法经过27次迭代;
牛顿法只迭代了3次,是二分法的十倍;
系统sqrt是最快最准的,不知道采用了什么原理实现的?