Worse than dynprog solution :(

fibonacci using binets formula

package main

import (
	"fmt"
	"math"
	"math/big"
	"runtime"
)

func doPow(v *big.Rat, n int64) (*big.Rat) {
	if n == 0 {
		return big.NewRat(1,1)
	}
	if n == 1 {
		return v
	}
	square := big.NewRat(1,1)	
	for n > 0 {
		if n & 1 == 1 {
			square.Mul(square, v)
			n -= 1
		} 
		
		v.Mul(v, v)
		n = n >> 1		
	}		
	return square
}

func fib(n int64) (*big.Int) {
	if n < 2 {
		return big.NewInt(n)
	}
	
	p, m, sqr5 := new(big.Rat), new(big.Rat), new(big.Rat)
	sqr5f := math.Sqrt(5.0)
	
	c := make(chan int, 3)
	
	go func() {
		p.SetFloat64(float64(1 + sqr5f))
		p = doPow(p, n)		
		c <- 1
	}()
	go func() {
		m.SetFloat64(float64(1 - sqr5f))
		m = doPow(m, n)		
		c <- 1
	}()
	go func() {
		sqr5.SetFloat64(float64(sqr5f))
		t := doPow(big.NewRat(2,1), n)		
		sqr5.Mul(sqr5, t)		
		c <- 1
	}()
		
	<-c
	<-c
	<-c	
	
	p.Sub(p, m)	
	
	p.Quo(p, sqr5)	
	
	num := p.Num()
	return num.Div(num, p.Denom())
		
}

func main() {
	runtime.GOMAXPROCS(runtime.NumCPU())		
	
	for i := 0; i < 10; i++ {
		fmt.Println(fib(int64(i)))
	}
}