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

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:

image

Python:

image

Haskell:

image

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! :blush:

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

image

I'm surprised I didn't know about this sooner, wow!

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

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

image

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! :slight_smile:

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

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

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
}

// Head recursion
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.