isqrt.go

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