Skip to content

Instantly share code, notes, and snippets.

# abesto/gist:3476594

Created August 26, 2012 09:27
Show Gist options
• Save abesto/3476594 to your computer and use it in GitHub Desktop.
Go: Newton's method for square root
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* 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 commented Apr 17, 2016

Excellent solution!

### johnlabarge commented Jul 6, 2016

"return" should be return z

### matr1xp commented Aug 10, 2016

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

### wklm commented Nov 5, 2016 • edited Loading

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 commented Feb 23, 2017

@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 commented Jun 23, 2017 • edited Loading

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.

Nice

### thomaspurchas commented Nov 1, 2017

@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 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 commented Jul 19, 2018

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

### 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 commented Apr 15, 2020

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 commented Apr 29, 2020 • edited Loading

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-- 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 commented Jul 13, 2020

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 commented Jul 13, 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))
}
``````

very sweet code.

### idmcalculus commented Jul 17, 2021

``````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 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 commented Aug 20, 2024

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

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