# 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
// 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()
}

//
// 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 := 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.