fibonacci.go

package main

import (
	"fmt"
	"math/big"
	"os"
	"strconv"
	"time"
	"unsafe"
)

func main() {
	if 2 != len(os.Args) {
		die("Usage: fibonacci <num>")
	}
	n_, err := strconv.ParseUint(os.Args[1], 0, 32)
	if nil != err {
		die("Bad number:", os.Args[1])
	}
	n := uint(n_)

	t_q := time.Now()
	f_q := fibonacci(n, false)
	fmt.Printf("%s (%s, quick method)\n", f_q, time.Since(t_q))

	t_nm := time.Now()
	f_nm := nomatrix_fibonacci(n)
	fmt.Printf("%s (%s, no matrix)\n", f_nm, time.Since(t_nm))

	t_sp := time.Now()
	f_sp := fibonacci(n, true)
	fmt.Printf("%s (%s, simple matrix power function)\n", f_sp, time.Since(t_sp))
}

func die(args ...interface{}) {
	if 0 == len(args) {
		fmt.Fprintln(os.Stderr, "Error.")
	} else {
		fmt.Fprintln(os.Stderr, args...)
	}
	os.Exit(1)
}

func fibonacci(n uint, simple bool) *big.Int {
	v0 := Vector{big.NewInt(0), big.NewInt(1)}
	m1 := Matrix{big.NewInt(0), big.NewInt(1),
		big.NewInt(1), big.NewInt(1)}
	var mn Matrix
	if simple {
		mn = m1.SimplePower(n)
	} else {
		mn = m1.Power(n)
	}
	vn := multiplyToVector(mn, v0)
	return vn[0]
}

func nomatrix_fibonacci(n uint) *big.Int {
	f := big.NewInt(0)
	fn := big.NewInt(1)
	for i := uint(0); i < n; i++ {
		fnn := big.NewInt(0).Add(f, fn)
		f, fn = fn, fnn
	}
	return f
}

// matrix 2x2:
// | m[0] m[1] |
// | m[2] m[3] |
type Matrix [4]*big.Int

func (m Matrix) Copy() (c Matrix) {
	c[0], c[1], c[2], c[3] = m[0], m[1], m[2], m[3]
	return
}

// vector:
// | v[0] |
// | v[1] |
type Vector [2]*big.Int

func multiply(a, b Matrix) Matrix {
	product := Matrix{
		big.NewInt(0).Add(big.NewInt(0).Mul(a[0], b[0]), big.NewInt(0).Mul(a[1], b[2])),
		big.NewInt(0).Add(big.NewInt(0).Mul(a[0], b[1]), big.NewInt(0).Mul(a[1], b[3])),
		big.NewInt(0).Add(big.NewInt(0).Mul(a[2], b[0]), big.NewInt(0).Mul(a[3], b[2])),
		big.NewInt(0).Add(big.NewInt(0).Mul(a[2], b[1]), big.NewInt(0).Mul(a[3], b[3])),
	}
	//fmt.Printf("%s * %s = %s\n", a, b, product) /////////////
	return product
}

func multiplyToVector(m Matrix, v Vector) Vector {
	product := Vector{
		big.NewInt(0).Add(big.NewInt(0).Mul(m[0], v[0]), big.NewInt(0).Mul(m[1], v[1])),
		big.NewInt(0).Add(big.NewInt(0).Mul(m[2], v[0]), big.NewInt(0).Mul(m[3], v[1])),
	}
	//fmt.Printf("%s * %s = %s\n", m, v, product) /////////////
	return product
}

var one Matrix

func init() {
	one = Matrix{big.NewInt(1), big.NewInt(0), big.NewInt(0), big.NewInt(1)}
}

func (m Matrix) Power(n uint) Matrix {
	result := one.Copy()
	tmp := m.Copy()
	for i, mask := uintptr(0), uint(1); i < 8*unsafe.Sizeof(n); i++ {
		if mask > n {
			break
		}
		//fmt.Printf("i=%d mask=%x(%b)\n", i, mask, mask)/////////////
		if 0 != (mask & n) {
			result = multiply(result, tmp)
		}
		tmp = multiply(tmp, tmp)
		mask <<= 1
	}
	//fmt.Printf("Power(%s, %d) = %s\n", m, n, result) //////////////////
	return result
}

func (m Matrix) SimplePower(n uint) Matrix {
	result := one.Copy()
	for i := uint(0); i < n; i++ {
		result = multiply(result, m)
	}
	//fmt.Printf("SimplePower(%s, %d) = %s\n", m, n, result) //////////////////
	return result
}