Skip to content

Instantly share code, notes, and snippets.

@callerobertsson
Last active January 14, 2022 15:49
Show Gist options
  • Save callerobertsson/67b674d996a65b5e9b00 to your computer and use it in GitHub Desktop.
Save callerobertsson/67b674d996a65b5e9b00 to your computer and use it in GitHub Desktop.
Golang: Fibonacci Big Number
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
}

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

@derpycoder
Copy link

derpycoder commented Aug 31, 2021

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

@paulborile
Copy link

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment