Newton's method in Go
While taking A Tour of Go, there was a very interesting exercise which involved Newton's method. The exercise was to implement Newton's method in Go. In this blog post I will briefly look at Newton's method and show you my implementation of it in Go.
The exercise
(...) implement a square root function: given a number x, we want to find the number z for which z² is most nearly x.
—A Tour of Go: Flowcontrol 8
This can be achieved with Newton's method.
Newton's method
Newton's method is a method for finding successively better approximations to the roots (or zeroes) of a real-valued function.
Newton's method starts with a function f defined over the real numbers x, the function's derivative f' and x0 as an initial guess for a root of the function f. In case the function satisfies the assumptions made in the derivation of f and the initial guess is close, then a better approximation x1 is:
This process is then repeated until a sufficiently accurate value is reached, as follows:
Wikipedia has a cool animation:

The function f is shown in blue and the tangent line is in red. We see that xn + 1 is a better approximation than xn for the root x of the function f.
—Wikipedia
Go Go Go
In Go's standard library, there already exists a function to solve this problem: math.Sqrt
.
I have implemented it by myself as follows—I think the code and the comments speak for themselves:
package main
import (
"fmt"
"math"
)
func Sqrt(x float64) (float64) {
// There are some special cases that we need to
// handle, before we can start with the real
// calculations.
if x == 0 || math.IsNaN(x) || math.IsInf(x, 1) {
fmt.Println("Special case!")
return x
}
if x < 0 {
fmt.Println("Special case!")
return math.NaN()
}
// Start with some guess for z
//
// Declare and initialize this floating point
// value by giving it a floating point syntax
//
// Also possible:
// var z float64 = 1
//
// or using conversion:
// x := float64(1)
z := 1.0
// Iterate only 10 times, because after 10 iterations we
// should be close enough to the output of math.Sqrt
for i := 0; i < 10; i++ {
// Adjust z based on how close z^2 is to x
calculation := z - (z*z-x)/(2*z)
// Stop loop once calculation has not
// changed since last iteration
if calculation == z {
break
}
z = calculation
}
return z
}
func main() {
// Declare and initialize an array of float64's
//
// We will use these values to test our Sqrt and
// compare it to math.Sqrt
a := [7]float64{0, 0.25, 0.44, 0.9, 6, 187, 2233}
// Iterate over the array we just created
for i := 0; i < 7; i++ {
ourSqrt := Sqrt(a[i])
mathSqrt := math.Sqrt(a[i])
fmt.Println("Sqrt output for", a[i], "as x is", ourSqrt)
fmt.Println("math.Sqrt output for", a[i], "as x is", mathSqrt)
fmt.Println("Difference between our Sqrt and math.Sqrt is", math.Abs(ourSqrt-mathSqrt), "\n")
}
}
The output:
Special case!
Sqrt output for 0 as x is 0
math.Sqrt output for 0 as x is 0
Difference between our Sqrt and math.Sqrt is 0
Sqrt output for 0.25 as x is 0.5
math.Sqrt output for 0.25 as x is 0.5
Difference between our Sqrt and math.Sqrt is 0
Sqrt output for 0.44 as x is 0.6633249580710799
math.Sqrt output for 0.44 as x is 0.6633249580710799
Difference between our Sqrt and math.Sqrt is 0
Sqrt output for 0.9 as x is 0.9486832980505138
math.Sqrt output for 0.9 as x is 0.9486832980505138
Difference between our Sqrt and math.Sqrt is 0
Sqrt output for 6 as x is 2.449489742783178
math.Sqrt output for 6 as x is 2.449489742783178
Difference between our Sqrt and math.Sqrt is 0
Sqrt output for 187 as x is 13.674794331177344
math.Sqrt output for 187 as x is 13.674794331177344
Difference between our Sqrt and math.Sqrt is 0
Sqrt output for 2233 as x is 47.25462940284264
math.Sqrt output for 2233 as x is 47.25462940284264
Difference between our Sqrt and math.Sqrt is 0
You can run it yourself in The Go Playground.
Let me know what you think about my approach.
Note that the result becomes less accurate as x becomes larger.
UPDATE 2018-05-30: I was told there is a bug in my code—and there is. The code fails if x
in main()
is between 0.0
and 1.0
. I will fix it and share the fix with you.
UPDATE 2018-06-12: Bug is fixed, I have updated the code in this blogpost. See the old code here.