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 x₀ 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 x₁ 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 x_{n + 1} is a better approximation than x_n 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.