Discussion on: Challenge: Write the recursive Fibonacci algorithm in a different language.

View post

I did this some time ago in Rust.

My first approach (the naive one) is very similar to @rapidnerd 's (George Marr's) solution in R and @andreanidouglas ' (Douglas R Andreani's) solution in Python:

fn fib(n: u64) -> u64 {
  match n {
    0 => 0,
    1 => 1,
    _ => fib(n-1) + fib(n-2),
  }
}

I realized that this solution quickly exceeded in execution time for n > 40, so I optimized it using a mathematical theorem:

Given that n and p are integers, and that n = 2p + 1, i. e. n is odd, the n-th fibonacci number is then

fib(n) = fib(p + (p+1)) = fib(p)² + fib(p+1)²

This means, we can break down numbers with odd indices into to numbers with about the half of the index – and do this again and again and again. This dramatically reduces execution time:

fn fib_fast(n: u64) -> u64 {
  match n {
    0 => 0,
    1 => 1,

    // even
    _ if n % 2 == 0 => fib_fast(n-1) + fib_fast(n-2),

    // odd
    _ => {
      let a = (n-1)/2;
      let b = n-a;
      let fib_a = fib_fast(a);
      let fib_b = fib_fast(b);
      return fib_a*fib_a + fib_b*fib_b;
    },
  }
}

Inspired by @avalander 's answer, I also added this even faster algorithm:

fn fib_super_fast(n: u64, i: u64, curr: u64, prev: u64) -> u64 {
  if i >= n {
    return curr;
  }

  return fib_super_fast(n, i + 1, curr + prev, curr);
}

fib_fast and fib_super_fast execute within microseconds even for higher indices. However, indices of 94 and higher cause a crash:

thread 'main' panicked at 'attempt to add with overflow', src/main.rs:42:35

Some performance measurements:

Enter n:
5
fib_super_fast(n) = 5 (0µs)
fib_fast(n)       = 5 (0µs)
fib(n)            = 5 (1µs)

Enter n:
20
fib_super_fast(n) = 6765 (1µs)
fib_fast(n)       = 6765 (10µs)
fib(n)            = 6765 (536µs)

Enter n:
40
fib_super_fast(n) = 102334155 (1µs)
fib_fast(n)       = 102334155 (54µs)
fib(n)            = 102334155 (1908011µs)

Enter n:
45
fib_super_fast(n) = 1134903170 (2µs)
fib_fast(n)       = 1134903170 (15µs)
fib(n)            = 1134903170 (21216762µs)

Enter n:
90
fib_super_fast(n) = 2880067194370816120 (2µs)
fib_fast(n)       = 2880067194370816120 (958µs)

Enter n:
93
fib_super_fast(n) = 12200160415121876738 (3µs)
fib_fast(n)       = 12200160415121876738 (152µs)

Enter n:
94
thread 'main' panicked at 'attempt to add with overflow', src/main.rs:42:35

Avalander • Aug 22 '18 • Edited

Nice!

Since writing my implementation I've remembered that the parameter i is unnecessary and you can decrease n instead until it's 0.

fn fib_super_fast(n: u64, curr: u64, prev: u64) -> u64 {
  if n <= 0 {
    return curr;
  }

  return fib_super_fast(n - 1, curr + prev, curr);
}

By the way, you didn't set default values for curr and prev, how does that work, do you need to call it with fib_super_fast(n, 1, 0)?

Felix Edelmann • Aug 22 '18

Yes, I do. But I have to use fib_super_fast(n, 1, 1, 0) as my other implementations also begin with 1. The code for calling the fibonacci methods is:

fn main() {
  loop {
    println!("Enter n:");

    let mut n_str = String::new();
    io::stdin().read_line(&mut n_str).expect("Failed to read line");
    let n = user_input_to_int(n_str);

    let t0 = SystemTime::now();
    let fib_super_fast_n = fib_super_fast(n, 1, 1, 0);
    let t1 = SystemTime::now();
    println!("fib_super_fast(n) = {} ({}µs)", fib_super_fast_n, time_difference(t0, t1));

    let t0 = SystemTime::now();
    let fib_fast_n = fib_fast(n);
    let t1 = SystemTime::now();
    println!("fib_fast(n)       = {} ({}µs)", fib_fast_n, time_difference(t0, t1));

    let t0 = SystemTime::now();
    let fib_n = fib(n);
    let t1 = SystemTime::now();
    println!("fib(n)            = {} ({}µs)", fib_n, time_difference(t0, t1));
  }
}

David Wickes • Aug 22 '18

Just for a nice style, you could factor out the returns as if is an expression...

fn fib_super_fast(n: u64, curr: u64, prev: u64) -> u64 {
  if n == 0 {
    curr
  } else {
    fib_super_fast(n - 1, curr + prev, curr)
  }
}