Skip to content

Instantly share code, notes, and snippets.

@abesto
Created August 26, 2012 09:27
Show Gist options
  • Save abesto/3476594 to your computer and use it in GitHub Desktop.
Save abesto/3476594 to your computer and use it in GitHub Desktop.
Go: Newton's method for square root
/*
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))
}
@nocdib
Copy link

nocdib commented Apr 17, 2016

Excellent solution!

@johnlabarge
Copy link

"return" should be return z

@matr1xp
Copy link

matr1xp commented Aug 10, 2016

that's a "naked" return (without arguments) and returns the named return values which is (z float64)

@wklm
Copy link

wklm commented Nov 5, 2016

while calling math.Abs(zz - z) you're going to get result like +2.148810e+001 bacuse of floating point precision. Please take a look:
https://play.golang.org/p/4xvF1Xl_Kq

How is it possible that the loop breaks?

@ozanmuyes
Copy link

@wklm Please see the code at https://play.golang.org/p/7dAtalgCFD. Upon run the results for each iteration can be observed. The thing is in your code, you print out the delta before calculating the new z and zz - so the second print statement in Sqrt function reflects the updated value - which will be considered for the next iteration condition.
PS: Sorry for reanimating a zombie thread - by the way good solution OP.

@awm086
Copy link

awm086 commented Jun 23, 2017

https://play.golang.org/p/57cdE3ZDQO
can someone please explain the math behind taking the abs value? does the z values alternate between negative and positive. I feel like I should know this already.

@voidnerd
Copy link

Nice

@thomaspurchas
Copy link

@awm086 the z value won't alternate between negative and positive, but the delta might. There is no guaranty that a z value calculated in this iteration will alway be larger than in the previous iteration.

Obvious example of this would be providing an x value that is the same or smaller than z, the loop will exit immediately.

@rshrimp
Copy link

rshrimp commented Jan 4, 2018

func Sqrt(x float64) float64 {
z :=1.0
temp := z
for i:=1; i < 10; i++ {
z= z - (zz-x)/(2z)
if diff:= math.Abs(z-temp); diff>0.000001{
temp=z
continue
}else{
break
}
}
return z
}

@soumojit
Copy link

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))
}

@mannharleen
Copy link

@shalomb
Copy link

shalomb commented Nov 16, 2019

package main

import (
	"fmt"
	"math"
)

func Sqrt(x float64) (z float64) {
	z = x
	_z := z

	for {
		z -= (z*z-x)/(2*z)
		if math.Abs(_z-z) == 0 { break }
		_z = z;
	}
	return
}

func main() {
	fmt.Printf("\n%v\n%v", Sqrt(500), math.Sqrt(500))
}

@muni2773
Copy link

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

@canis
Copy link

canis commented Apr 29, 2020

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))
}

@jhn--
Copy link

jhn-- commented Jun 6, 2020

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))
}

@shengui919
Copy link

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))
}

@shengui919
Copy link

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.

@idmcalculus
Copy link

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)))
}

@pyfreyr
Copy link

pyfreyr commented Sep 28, 2023

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

}

@IbalArrasyid
Copy link

z := 1.0
// First guess
z -= (zz - x) / (2z)
// 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

amazinggg

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment