Three ways to implement sqrt(): fixed iteration, error control and standard library comparison
1. When learning the official Go tutorial a Tour of Go, I encountered a very classic exercise:
Implement a square root function sqrt(x). as shown in Figure 1
This exercise involves not only Go’s loops and functions, but also introduces a very important numerical calculation method:
Newton iteration method (Newtons method).
This article will demonstrate how to get from a simple version through three step-by-step examples,
Step by step to achieve a more precise and robust square root function:
- Fixed 10 cycles
- Stop using error control
- Compare the results with the standard library Math.sqrt
All code is organized in the following directory:
go-tour/
├── sqrt-iterations/
├── sqrt-epsilon/
├── sqrt-iteration-count/
2. Introduction to the Newton Iteration Method
The goal of the square root is:
Given a number x, find a number z, so that:
Z² ≈ X
The Newtonian method makes it closer to the real value by constantly revising the Z.
The update formula for each step is as follows:
z = z – (zz – x) / (2z)
where:
- z*z – x represents the current error
- 2*z represents the derivative of the function z²
- Each update brings the result closer to the real value
This method converges very fast,
It usually takes only a few iterations to achieve very high precision.
3. Example 1: Fixed 10 iterations, corresponding to sqrt-iterations/main.go
package main
import (
"fmt"
)
func Sqrt(x float64) float64 {
z := 1.0 // 初始猜测值
for i := 0; i < 10; i++ {
z -= (z*z - x) / (2 * z)
fmt.Println("iteration", i, "z =", z)
}
return z
}
func main() {
fmt.Println("result:", Sqrt(2))
}
4. Example of running results
can be observed:
After each cycle, the value of Z will quickly approach √2.
Usually after the 4th~5th iteration,
The result is very close to the real value.
package main
import (
"fmt"
)
func Sqrt(x float64) float64 {
z := 1.0 // 初始猜测值
for i := 0; i < 10; i++ {
z -= (z*z - x) / (2 * z)
fmt.Println("iteration", i, "z =", z)
}
return z
}
func main() {
fmt.Println("result:", Sqrt(2))
}
5. Example 2: Use Epsilon to control convergence + compare math.sqrt correspondence: sqrt-epsilon/main.go
package main
import (
"fmt"
"math"
)
func Sqrt(x float64) float64 {
z := 1.0 // 初始猜测值
const epsilon = 1e-10 // 精度控制
for {
prev := z
z -= (z*z - x) / (2 * z)
// 判断变化是否足够小
if math.Abs(z-prev) < epsilon {
break
}
}
return z
}
func main() {
fmt.Println("My sqrt:", Sqrt(2))
fmt.Println("Math sqrt:", math.Sqrt(2))
}
6. Example of running results
Why is this better?
This way:
Automatically judge convergence
Avoid meaningless calculations
Improve program efficiency
To verify that our implementation is correct,
The results can be compared to Math.sqrt in the Go standard library.
As you can see, the two are almost exactly the same (exactly equal).
/app/go-tour/sqrt-epsilon # go run main.go My sqrt: 1.4142135623730951 Math sqrt: 1.4142135623730951
7. Example 3: Count the number of iterations (observe convergence efficiency) Corresponding: sqrt-iteration-count/main.go
package main
import (
"fmt"
"math"
)
func Sqrt(x float64) float64 {
z := 1.0 // 初始猜测值
const epsilon = 1e-10 // 精度控制
count := 0
for {
prev := z
z -= (z*z - x) / (2 * z)
count++
// 判断变化是否足够小
if math.Abs(z-prev) < epsilon {
break
}
}
fmt.Println("iterations:", count)
return z
}
func main() {
fmt.Println("result:", Sqrt(2))
}
8. Example of running results
Features:
statistics count
output iterations
Use:
Observe the algorithm efficiency.
Normally:
iterations: 5
High-precision results can be obtained in just 5 times.
/app/go-tour/sqrt-iteration-count # go run main.go iterations: 5 result: 1.4142135623730951
