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

I was checking out the Rust version of the above code, BigInt crate to be specific and it blew my mind! 🤯

   500,000 took   1.07 s.   (104,494 digits)
 1,000,000 took   3.97 s.   (208,988 digits)
 5,000,000 took 100.95 s. (1,044,938 digits) [1.6 Minutes]
10,000,000 took 406.98 s. (2,089,877 digits) [6.7 Minutes]

Rust program was able to utilize 100% of CPU.
Memory Usage: 500 Kb - 3 Mb (While outputting the whole Big Int String).

---

I installed the Golang compiler and did a benchmark on my system.

   500,000 took    3.62 s.   (104,494 digits)
 1,000,000 took   15.11 s.   (208,988 digits)
 5,000,000 took  386.85 s. (1,044,938 digits)  [6.4 Minutes]
10,000,000 took 1896.96 s. (2,089,876 digits) [31.6 Minutes] 😅

I lost patience after 5+ minutes (351 Seconds) for the number 5 million, In my first try 😅, so had to run it again to do justice to Golang.
Memory remained around ~10 - 40mb.
It was unable to use 100% of processor.

P.S. I know micro benchmarks don't make sense in real world, I was just curious. I am writing my observation down here, in case someone else is curious in the future, or I myself want to check these out.

My system specs:

Intel®` Core™ i5-7200U CPU @ 2.50GHz × 4
15.5 Gb
Thinkpad L470
Fedora 34 - 64-bit

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++ {