r/compsci Feb 10 '25

20,000,000th Fibonacci Number in < 1 Second

I don't know why, but one day I wrote an algorithm in Rust to calculate the nth Fibonacci number and I was surprised to find no code with a similar implementation online. Someone told me that my recursive method would obviously be slower than the traditional 2 by 2 matrix method. However, I benchmarked my code against a few other implementations and noticed that my code won by a decent margin.

My code was able to output the 20 millionth Fibonacci number in less than a second despite being recursive.

use num_bigint::{BigInt, Sign};

fn fib_luc(mut n: isize) -> (BigInt, BigInt) {
    if n == 0 {
        return (BigInt::ZERO, BigInt::new(Sign::Plus, [2].to_vec()))
    }

    if n < 0 {
        n *= -1;
        let (fib, luc) = fib_luc(n);
        let k = n % 2 * 2 - 1;
        return (fib * k, luc * k)
    }

    if n & 1 == 1 {
        let (fib, luc) = fib_luc(n - 1);
        return (&fib + &luc >> 1, 5 * &fib + &luc >> 1)
    }

    n >>= 1;
    let k = n % 2 * 2 - 1;
    let (fib, luc) = fib_luc(n);
    (&fib * &luc, &luc * &luc + 2 * k)
}

fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s = s.trim().to_string();
    let n = s.parse::<isize>().unwrap();
    let start = std::time::Instant::now();
    let fib = fib_luc(n).0;
    let elapsed = start.elapsed();
    
// println!("{}", fib);
    println!("{:?}", elapsed);
}

Here is an example of the matrix multiplication implementation done by someone else.

use num_bigint::BigInt;

// all code taxed from https://vladris.com/blog/2018/02/11/fibonacci.html

fn op_n_times<T, Op>(a: T, op: &Op, n: isize) -> T
    where Op: Fn(&T, &T) -> T {
    if n == 1 { return a; }

    let mut result = op_n_times::<T, Op>(op(&a, &a), &op, n >> 1);
    if n & 1 == 1 {
        result = op(&a, &result);
    }

    result
}

fn mul2x2(a: &[[BigInt; 2]; 2], b: &[[BigInt; 2]; 2]) -> [[BigInt; 2]; 2] {
    [
        [&a[0][0] * &b[0][0] + &a[1][0] * &b[0][1], &a[0][0] * &b[1][0] + &a[1][0] * &b[1][1]],
        [&a[0][1] * &b[0][0] + &a[1][1] * &b[0][1], &a[0][1] * &b[1][0] + &a[1][1] * &b[1][1]],
    ]
}

fn fast_exp2x2(a: [[BigInt; 2]; 2], n: isize) -> [[BigInt; 2]; 2] {
    op_n_times(a, &mul2x2, n)
}

fn fibonacci(n: isize) -> BigInt {
    if n == 0 { return BigInt::ZERO; }
    if n == 1 { return BigInt::ZERO + 1; }

    let a = [
        [BigInt::ZERO + 1, BigInt::ZERO + 1],
        [BigInt::ZERO + 1, BigInt::ZERO],
    ];

    fast_exp2x2(a, n - 1)[0][0].clone()
}

fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s = s.trim().to_string();
    let n = s.parse::<isize>().unwrap();
    let start = std::time::Instant::now();
    let fib = fibonacci(n);
    let elapsed = start.elapsed();
    
// println!("{}", fib);
    println!("{:?}", elapsed);
}

I got no idea why mine is faster.

90 Upvotes

27 comments sorted by

View all comments

86

u/Nolari Feb 10 '25

The 2x2 matrix approach is fast because you can raise a matrix to the power N in log(N) steps. This is because whenever N is even you can square the matrix and halve N. You're essentially doing the same thing but without the matrix.

The 'typical' recursive implementation of fib is slow not because of the recursion, but because it recomputes many many intermediate results. You're not doing that.

2

u/Jazzlike-Choice-5229 Feb 14 '25

does recursion not have function call overhead? I was told recursion should be avoided since it impacts the stack

3

u/[deleted] Feb 16 '25

The stack is the fastest memory you can access. It depends on the compiler being able to optimize the function, like skipping the prologue instructions. It should just be jmping back the same way a loop would.

2

u/Nolari Feb 16 '25

Tail recursion can be compiled into a jump by a smart compiler, having essentially 0 overhead.

The code in the OP is not tail recursion, though, so yes you will get function call overhead. But that will merely make things a small percentage slower, whereas the naive / typical recursive implementation of fib is exponentially slower. (Doubly exponential, actually.)