Skip to content

Instantly share code, notes, and snippets.

@bminer

bminer/isqrt.go

Created Jun 7, 2019
Embed
What would you like to do?
package main
import (
"fmt"
"strings"
)
// odds computes the square root by adding odd numbers together until n is
// reached.
// Cost: 4 commands per loop; O(n) loops
func odds(n int) (int, int) {
odds := 1
temp := 0
i := 0
for n > temp {
temp += odds
i++
odds += 2
}
return i, i
}
// newton computes the square root using newton's method
// Cost: 6 commands per loop; O(log2(n)) loops
func newton(num int) (int, int) {
// high initial estimate
n := (num / 2) + 1
// n1 = (n + num/n) / 2
n1 := num
n1 /= n
n1 += n
n1 /= 2
i := 0 // not needed; just for benchmarking
for n1 < n {
i++ // not needed; just for benchmarking
n = n1
// n1 = (n + num/n) / 2
n1 = num
n1 /= n
n1 += n
n1 /= 2
}
return n, i
}
func test(f func(int) (int, int)) {
for i := 1; i <= 101; i++ {
sqrt, _ := f(i)
fmt.Println(i, sqrt)
}
fmt.Println(strings.Repeat("-", 80))
}
func main() {
test(odds)
test(newton)
// Suppose you were 50 blocks away...
n := 50
sqrt, iter := odds(n * n)
fmt.Println("odds", sqrt, "cost", iter*4)
sqrt, iter = newton(n * n)
fmt.Println("newton", sqrt, "cost", iter*6)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment