bminer · June 7, 2019 01:51 · Jun 7, 2019
diff --git a/isqrt.go b/isqrt.go
@@ -0,0 +1,68 @@
+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)
+}
No results found