I was out on the hunt to find fast fibonacci code to find the nth number in a fibonacci sequence.
I found this website and I tested the code online. I adjusted the code to save the 500000th number of the sequence to a file called fib.txt
Python code:
def fibonacci(n):
if n < 0:
raise ValueError("Negative arguments not implemented")
return _fib(n)[0]
def _fib(n):
if n == 0:
return (0, 1)
else:
a, b = _fib(n // 2)
c = a * (b * 2 - a)
d = a * a + b * b
if n % 2 == 0:
return (c, d)
else:
return (d, c + d)
f = open("fib.txt", "w")
f.write(str(fibonacci(500000)))
f.close()
Haskell code:
fibonacci :: Integer -> Integer
fibonacci n | n >= 0 = fst (fib n)
fib :: Integer -> (Integer, Integer)
fib 0 = (0, 1)
fib n =
let (a, b) = fib (div n 2)
c = a * (b * 2 - a)
d = a * a + b * b
in if mod n 2 == 0
then (c, d)
else (d, c + d)
main = writeFile "fib.txt" $ show $ fibonacci 500000
Rust code, coded by me
// Import bigUint
extern crate num;
use num::bigint::BigUint;
// Write to file
use std::fs::write;
// Convert str to BigUint
fn to_big(nth: &str) -> BigUint { nth.parse::<BigUint>().unwrap() }
// Get the final value
fn fibonacci(nth:usize) -> BigUint {
fib(to_big(nth.to_string().as_str()),&to_big("0"),&to_big("1"),&to_big("2")).0
}
// Head recursion
fn fib(nth: BigUint,zero:&BigUint,one:&BigUint,two:&BigUint) -> (BigUint,BigUint) {
// Break recursion if fib reaches zero
if &nth == zero {
return (zero.clone(),one.clone());
}
// Would number divide evenly by 2?
let modulo_rem = &nth % two;
// Subtract nth by modulo rem and divide by 2 to do floor division
let (a,b) : (BigUint,BigUint) = fib((nth-&modulo_rem)/two,zero,one,two);
// Algorithm...
let c = &a * (&b * two - &a);
let d = &a * &a + &b * &b;
if &modulo_rem == one {
let summed = c+&d;
return (d,summed);
} else {
return (c,d);
}
}
fn main() {
let data = fibonacci(500000);
write("fib.txt", data.to_string()).expect("Unable to write file");
}
Average results (in seconds):
| Haskell | Python | Rust | |
|---|---|---|---|
| Speed | ~0.015 | ~0.2 | ~2.9 |
Pictures on how I got to these results:
Rust:
Python:
Haskell:
In the above results, Python is fast, Haskell is extremely fast, but Rust is slow, around 15 times slower than Python.
I use Rust very little and I would love advice from experienced developers on how I can improve the quality and performance of my fibonacci Rust code to help me improve as a programmer.
Thank you in advance! 
