# Code Review + Why is this Fibonacci code so slow?

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()
``````

``````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
}

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

Speed ~0.015 ~0.2 ~2.9

Pictures on how I got to these results:

## Python:

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!

1 Like

add the `--release` flag : `cargo build --release`

9 Likes

Besides the `--release` flag to enable optimization, most of the time here is spent in the string conversion. This is a known area that needs improvement in `BigUint`, which I hope to make time for soon.

16 Likes

The code is still slower than python here, so if I can't find anything that brings this less than the python speeds, I'll mark this as the answer

1 Like

On my system 94.76% of the time is spent in big num formatting when running the rust version in release mode.

3 Likes

Thank you for the statistics on the problem @cuviper mentioned!

The same applies to Haskell, you can enable (the highest level of) optimization with `ghc main.hs -O2`. It doesnβt seem to make that much of a difference though, presumably since the `Integer` implementation is always optimized anyways (using `GMP` internally).

2 Likes

Doesn't make much of a difference for this Haskell code, but thank you for the tip, I'll use it in the future when coding in Haskell!

1 Like

You can also try inlining the `fib` function to see if that speeds it up

A very similar question about slow Fibonacci in Rust came up here only weeks ago. Using much the same algorithm I think. Optimizing Fast Fibonacci Computation

That discussion led to forum member gvissers writing a Fibo in Rust. Above and beyond the call of duty they have included use of various big number crates and their own hand rolled big integer arithmetic for comparison.

That code calculates and prints all the digits of the first Fibonacci number to contain one million digits. That is fibo(4784969). And is now in my fibo_4784969 repository where the results of doing this as a coding challenge in various languages are presented. GitHub - ZiCog/fibo_4784969: The million digit Fibonacci number challenge. Calculate fibo(4784969) in various languages.

Anyway, I tweaked gvissers code to produce fibo(500000) as per the question in the OP, with the following results. Shown for all the different big int crates gvissers supports plus my C++ attempt with my hand made big integer math, plus the Python code given by the OP for comparison:

binary hand made big integer by gvissers:

``````β time ./target/release/fibo_4784969 -b binary > fibo.out
computing F(500000): 0.021s
printing F(500000): 0.115s
./target/release/fibo_4784969 -b binary > fibo.out  0.14s user 0.00s system 98% cpu 0.145 total``````

decimal hand made big integer by gvissers:

``````β time ./target/release/fibo_4784969 -b decimal  > fibo.out
computing F(500000): 0.053s
printing F(500000): 0.000s
./target/release/fibo_4784969 -b decimal > fibo.out  0.06s user 0.00s system 96% cpu 0.061 total``````

ibig crate:

``````β time ./target/release/fibo_4784969 -b ibig  > fibo.out
computing F(500000): 0.007s
printing F(500000): 0.021s
./target/release/fibo_4784969 -b ibig > fibo.out  0.03s user 0.00s system 91% cpu 0.036 total``````

gmp crate:

``````β time ./target/release/fibo_4784969 -b gmp  > fibo.out
computing F(500000): 0.002s
printing F(500000): 0.007s
./target/release/fibo_4784969 -b gmp > fibo.out  0.01s user 0.00s system 85% cpu 0.017 total``````

num_bigint crate:

``````β time ./target/release/fibo_4784969 -b num_bigint  > fibo.out
computing F(500000): 0.009s
printing F(500000): 0.285s
./target/release/fibo_4784969 -b num_bigint > fibo.out  0.30s user 0.00s system 99% cpu 0.303 total``````

rug crate:

``````β time ./target/release/fibo_4784969 -b rug   > fibo.out
computing F(500000): 0.002s
printing F(500000): 0.008s
./target/release/fibo_4784969 -b rug > fibo.out  0.01s user 0.00s system 84% cpu 0.017 total``````

Python:

``````β time python3 fibo.py
python3 fibo.py  0.23s user 0.02s system 95% cpu 0.258 total``````

My C++ with self made big integer math:

``````β time ./fibo_karatsuba > fibo.txt
./fibo_karatsuba > fibo.txt  0.03s user 0.01s system 89% cpu 0.041 total``````

In summary:

``````fibo(500000) Total compute + print time in seconds.

Rust + gmp             - 0.017
Rust + rug             - 0.017
Rust + ibig            - 0.036
C++ + hand rolled math - 0.041
decimal by gvissers    - 0.061
binary by gvissers     - 0.145
Python                 - 0.258
Rust + num_bigint      - 0.303``````

All timings on a MacBook Pro M1, 16GB RAM.

I'm glad to see my hand rolled big integer solution in C++ is holding up well. Python is shamefully slow even if it uses gmp under the hood.

A big thanks to gvissers for the Rust entry to the Million Digit Fibo Challenge. I have been putting off writing a Rust version of my entry for a couple of years now. Now it's done!

Aside: One chap claimed he would beat all compiled languages by writing a fibo(4784969) solution in ARM assembler. He has not been heard of for two years now...

14 Likes

Good to see my Rust entry has been merged

For comparison, here are some timings on a Core i7-6700HQ laptop. Since the Rust compiler uses LLVM as a backend, I have added a comparison where I have also compiled @ZiCog 's C++ code with clang. (BTW, ZiCog,my program also has a `-n` flag that lets you set the index of the Fibonacci number you wish to compute, no need to adjust the code).

``````Rust + gmp         0.004
Rust + rug         0.007
Rust + ibig        0.013
babs, decimal      0.020
ZiCog, C++, clang  0.021
decimal            0.022
ZiCog, C++, g++    0.024
binary             0.097
num_bigint         0.248
``````

What can we learn from this? Not all that much that we did not already know. If you want speed, use gmp. @tczajka is doing a stellar job with his pure Rust `ibig` library. If you only use Karatsuba multiplication, you will all end up in the same ballpark (variations in the timings are larger than the differences between the different solutions here). Conversion to decimal in `num_bigint` is slow, something the author is aware of and trying to fix. Same for my own code, though less extreme. And for some reason, my 5 year old laptop is faster than a MacBook Pro

5 Likes
• You can convert from primitives to `BigUint` with the `From`/`Into` traits, there's no need to parse them from strings.
• There's no need for `nth` to be a `BigUint` if it's coming from an `usize` anyway. Also, there's no way you could ever compute the `usize::MAX`-th fibonacci number anyway since the address space would not be enough to store the intermediate results.
• You can do operations between `BigUint` and primitives, so you don't need `zero`, `one` and `two`.
``````// Import bigUint
use num::BigUint;
// Write to file
use std::fs::write;

// Get the final value
fn fibonacci(nth: usize) -> BigUint {
fib(nth).0
}

fn fib(nth: usize) -> (BigUint, BigUint) {
// Break recursion if fib reaches zero
if nth == 0 {
return (0u8.into(), 1u8.into());
}
// Would number divide evenly by 2?
let modulo_rem = nth % 2;
// Subtract nth by modulo rem and divide by 2 to do floor division
let (a, b): (BigUint, BigUint) = fib((nth - modulo_rem) / 2);

// Algorithm...
let c = &a * (&b * 2u8 - &a);
let d = &a * &a + &b * &b;

if modulo_rem == 1 {
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");
}
``````

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.