Is there a more elegant Go implementation of Newton's method?

Question

I'm doing the Go tutorials and am wondering whether there is a more elegant way to compute a square root using Newton's method on Exercise: Loops and Functions than this:

func Sqrt(x float64) float64 {
    count := 0
    var old_z, z float64 = 0, 1
    for ; math.Abs(z-old_z) > .001; count++ {
        old_z, z = z, z - (z*z - x) / 2*z
    }
    fmt.Printf("Ran %v iterations\n", count)
    return z
}

(Part of the specification is to provide the number of iterations.) Here is the full program, including package statement, imports, and main.

Shalna

Answer 1

First, you algorithm is not correct. The formula is:

You modelled this with:

z - (z*z - x) / 2*z

But it should be:

z - (z*z - x)/2/z

Or

z - (z*z - x)/(2*z)

(Your incorrect formula had to run like half a million iterations even to just get as close as 0.001! The correct formula uses like 4 iterations to get as close as 1e-6 in case of x = 2.)

Next, initial value of z=1 is not the best for a random number (it might work well for a small number like 2). You can kick off with z = x / 2 which is a very simple initial value and takes you closer to the result with fewer steps.

Further options which do not necessarily make it more readable or elegant, it's subjective:

You can name the result to z so the return statement can be "bare". Also you can create a loop variable to count the iterations if you move the current "exit" condition into the loop which if met you print the iterations count and can simply return. You can also move the calculation to the initialization part of the if:

func Sqrt(x float64) (z float64) {
    z = x / 2
    for i, old := 1, 0.0; ; i++ {
        if old, z = z, z-(z*z-x)/2/z; math.Abs(old-z) < 1e-5 {
            fmt.Printf("Ran %v iterations\n", i)
            return
        }
    }
}

You can also move the z = x / 2 to the initialization part of the for but then you can't have named result (else a local variant of z would be created which would shadow the named return value):

func Sqrt(x float64) float64 {
    for i, z, old := 1, x/2, 0.0; ; i++ {
        if old, z = z, z-(z*z-x)/2/z; math.Abs(old-z) < 1e-5 {
            fmt.Printf("Ran %v iterations\n", i)
            return z
        }
    }
}

Note: I started my iteration counter with 1 because the "exit" condition in my case is inside the for and is not the condition of for.

Moyra

Yipes! Thanks for answering the question I should have asked (is my algorithm correct?) as well as the one that I asked. – Shalna

Answer 2

package main

import (
    "fmt"
    "math"
)

func Sqrt(x float64) float64 {
    z := 1.0
    // First guess
    z -= (z*z - x) / (2*z)
    // Iterate until change is very small
    for zNew, delta := z, z; delta > 0.00000001; z = zNew {
        zNew -= (zNew * zNew - x) / (2 * zNew)
        delta = z - zNew
    }
    return z
}

func main() {
    fmt.Println(Sqrt(2))
    fmt.Println(math.Sqrt(2))
}

Does