Golang: Fibonacci Big Number

fibonacci.go

package main

import (
	"fmt"
	"math/big"
)

func main() {

	for i := 1; i <= 10; i++ {
		n := big.NewInt(int64(i))
		fmt.Printf("The %v:th fibonacci number is %v\n", n, fibonacci(n))
	}

	n := big.NewInt(1001)

	fmt.Printf("The %v:th fibonacci number is %v\n", n, fibonacci(n))

	n = big.NewInt(500 * 1000)

	fmt.Printf("The %v:th fibonacci number has %v digits\n", n, len(fibonacci(n).String()))

}

func fibonacci(n *big.Int) *big.Int {

	f2 := big.NewInt(0)
	f1 := big.NewInt(1)

	if n.Cmp(big.NewInt(1)) == 0 {
		return f2
	}

	if n.Cmp(big.NewInt(2)) == 0 {
		return f1
	}

	for i := 3; n.Cmp(big.NewInt(int64(i))) >= 0; i++ {
		next := big.NewInt(0)
		next.Add(f2, f1)
		f2 = f1
		f1 = next
	}

	return f1
}

result.md

Results

Compared with data from http://www.bigprimes.net/archive/fibonacci/

$ go build && time ./fibonacci
The 1:th fibonacci number is 0
The 2:th fibonacci number is 1
The 3:th fibonacci number is 1
The 4:th fibonacci number is 2
The 5:th fibonacci number is 3
The 6:th fibonacci number is 5
The 7:th fibonacci number is 8
The 8:th fibonacci number is 13
The 9:th fibonacci number is 21
The 10:th fibonacci number is 34
The 1001:th fibonacci number is 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
The 500000:th fibonacci number has 104494 digits

real    0m6.729s
user    0m6.700s
sys     0m0.422s

The calculation of the 500000:th fibonacci is a bit time consuming :-)

Comparing this to other algorithms I had to change line 38 to start from 2 :
for i := 2; n.Cmp(big.NewInt(int64(i))) >= 0; i++ {