Go: Newton's method for square root

gistfile1.go

/*
A Tour of Go: page 44
http://tour.golang.org/#44

Exercise: Loops and Functions

As a simple way to play with functions and loops, implement the square root function using Newton's method.

In this case, Newton's method is to approximate Sqrt(x) by picking a starting point z and then repeating: z - (z*z - x) / (2 * z)


To begin with, just repeat that calculation 10 times and see how close you get to the answer for various values (1, 2, 3, ...).

Next, change the loop condition to stop once the value has stopped changing (or only changes by a very small delta). See if that's more or fewer iterations. How close are you to the math.Sqrt?

Hint: to declare and initialize a floating point value, give it floating point syntax or use a conversion:

	z := float64(1)
	z := 1.0
*/

package main

import (
	"fmt"
	"math"
)

const DELTA = 0.0000001
const INITIAL_Z = 100.0

func Sqrt(x float64) (z float64) {
    z = INITIAL_Z
    
    step := func() float64 {
    	return z - (z*z - x) / (2 * z)
    }
    
    for zz := step(); math.Abs(zz - z) > DELTA
    {
    	z = zz
	zz = step()
    }
    return
}

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

Seems like the initial value of Z should be a very high number to give a start difference in iterations as the number gets bigger. The smaller values are positive for Z:=100

package main

import (
"fmt"
"math"
)

const DELTA = 0.0000001
const INITIAL_Z = 100.0

func nSqrt(x float64) (z float64) {
z = INITIAL_Z

step := func() float64 {
	return z - (z*z - x) / (2 * z)
}

i := 0
for zz := step(); math.Abs(zz - z) > DELTA
{
	z = zz
	fmt.Println("nSqrt iteration",i+1.0,"yields", z)
	zz = step()
	i++
}
return

}

func Sqrt(x float64) float64 {
z := 10000.0
lowestz := x
for i := 1.0; ; i++ {
z -= (zz - x) / (2z)
if z < lowestz {
if (lowestz - z ) < 1 {
return math.Round(lowestz)
}
lowestz = z
fmt.Println("Sqrt iteration",i, "yields", lowestz)
} else {
fmt.Println("Sqrt iteration",i, "yields", z)
}
}
return -1.0
}

func main() {
x := 88446264882046.0
fmt.Println(math.Sqrt(x),"is the Math.sqrt of",x)
fmt.Println(Sqrt(x),"is the sqrt of",x)
fmt.Println(nSqrt(x),"is the nSqrt of",x)
}

9.404587438162612e+06 is the Math.sqrt of 8.8446264882046e+13
Sqrt iteration 1 yields 4.4223182441023e+09
Sqrt iteration 2 yields 2.2111691220398436e+09
Sqrt iteration 3 yields 1.1056045609068596e+09
Sqrt iteration 4 yields 5.528422795037274e+08
Sqrt iteration 5 yields 2.7650113206446457e+08
Sqrt iteration 6 yields 1.384105043735723e+08
Sqrt iteration 7 yields 6.952475924039575e+07
Sqrt iteration 8 yields 3.5398457082733385e+07
Sqrt iteration 9 yields 1.8948524021609366e+07
Sqrt iteration 10 yields 1.1808118325449023e+07
Sqrt iteration 11 yields 9.64920561384981e+06
Sqrt iteration 12 yields 9.407688110605048e+06
Sqrt iteration 13 yields 9.404587949136695e+06
9.404588e+06 is the sqrt of 8.8446264882046e+13
nSqrt iteration 1 yields 4.4223132446023e+11
nSqrt iteration 2 yields 2.21115662330115e+11
nSqrt iteration 3 yields 1.1055783136505748e+11
nSqrt iteration 4 yields 5.527891608252874e+10
nSqrt iteration 5 yields 2.763945884126436e+10
nSqrt iteration 6 yields 1.3819731020632118e+10
nSqrt iteration 7 yields 6.909868710315565e+09
nSqrt iteration 8 yields 3.454940755153831e+09
nSqrt iteration 9 yields 1.7274831775453014e+09
nSqrt iteration 10 yields 8.637671885197371e+08
nSqrt iteration 11 yields 4.3193479223662525e+08
nSqrt iteration 12 yields 2.1606977993465686e+08
nSqrt iteration 13 yields 1.0823956057167856e+08
nSqrt iteration 14 yields 5.4528347469662406e+07
nSqrt iteration 15 yields 2.807518552031814e+07
nSqrt iteration 16 yields 1.5612760710839875e+07
nSqrt iteration 17 yields 1.063887956936863e+07
nSqrt iteration 18 yields 9.476186945198271e+06
nSqrt iteration 19 yields 9.404857931423109e+06
nSqrt iteration 20 yields 9.404587442052443e+06
nSqrt iteration 21 yields 9.404587438162612e+06
9.404587438162612e+06 is the nSqrt of 8.8446264882046e+13

Hmm. Folks, I don't get it. z and zz? Why? One variable in loop is enough.

package main

import (
	"fmt"
	"math"
)

func Sqrt(x float64) (float64) {
	z := 100.0
	for math.Abs(z - math.Sqrt(x)) > 0.000000000001 {
		z = (z - (z * z - x) / (2 * z))
	}
	return z
}

func main() {
	n := 456789
	fmt.Println(Sqrt(n), math.Sqrt(n))
}

um.. does this make sense?

package main

import (
	"fmt"
	"math"
)

var DELTA = 0.0001

func Sqrt(x float64) float64 {
	z := 1.0
	for ; math.Abs(z*z-x) > DELTA; z -= (z*z - x) / (z * 2) {
	}
	return z
}

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

Excellent solution!

package main

import (
"fmt"
"math"
)

const Delta = 1e-10

func sqrt(x float64) float64 {
z, old := 1.0, 1.1
for math.Abs(old-z) > Delta {
old = z
z = z - (zz-x)/(2z)
}
return z
}

func main() {
fmt.Println(sqrt(2))
}

um.. does this make sense?

package main

import (
	"fmt"
	"math"
)

var DELTA = 0.0001

func Sqrt(x float64) float64 {
	z := 1.0
	for ; math.Abs(z*z-x) > DELTA; z -= (z*z - x) / (z * 2) {
	}
	return z
}

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

very sweet code.

package main

import (
	"fmt"
	"math"
)

func Sqrt(x float64) float64 {
	var zi float64 = x/2
	delta := 0.00000001
	z := zi - (zi*zi - x) / (2*zi)
	
	for math.Abs(z-zi) > delta {
		zi = z
		z -= (zi*zi - x) / (2*zi)
		fmt.Printf("%v, %v\n", zi, z)
	}
	return z
}

func main() {
	fmt.Println(Sqrt(0.5))
	fmt.Println("real value = " + fmt.Sprint(math.Sqrt(0.5)))
}

func Sqrt(x float64) float64 {
	z := 1.0
	epsilon := 1e-6
	lim := 10

	for i := 0; i < lim && math.Abs(z*z-x) > epsilon; i++ {
		z -= (z*z - x) / (2 * z)
	}
	return z

}