-
-
Save abesto/3476594 to your computer and use it in GitHub Desktop.
| /* | |
| 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)) | |
| } |
"return" should be return z
that's a "naked" return (without arguments) and returns the named return values which is (z float64)
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?
@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.
My solution is without math.Abs.
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
@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.
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
}
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))
}
Using recursion:
https://gist.github.com/mannharleen/8f6717f892912d603699b51da4cad2ec
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))
}
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
}
Excellent solution!