Hi all,
I'm a Rust newbie that's been fooling around with Fibonacci's numbers as a starting point. I have included my implementation to compute Fibonacci numbers quickly for very large indices below. It runs in about 12 seconds for n = 10^9 (on the optimized release build). It's essentially a Rust translation of the Dijikstra's recurrence equation with memoization as implemented by mhw here. The Julia implementation, benchmarked on the same computer with n = 10^9, runs in about 9 seconds. The results are consistent across multiple runs.
With that in mind, my next goal is to optimize the implementation further so I can at least get runtimes that are on par if not better than Julia's. From the look of things it's clear that the Rust implementation is at least on the same order of magnitude in terms of speed. What's left to improve is likely minor mechanical inefficiencies. My thoughts on this right now:
-
The Rust version is doing an extra hash than what is absolutely necessary due to first checking the existence of the key, then hash again to get the value (if it exists) or hash again in order to insert the new value. I would like to modify this to use the entry.or_insert() pattern to avoid the extra hash. However so far I've always ended up losing the fight against the borrow checker.
-
Maybe we can avoid some clones?
-
Maybe we can avoid moving the cache around all the time and instead use borrow? This I am doubtful as the implementation is recursive. Each recursive call must use mutable borrow since new values can potentially be inserted, but you can't have multiple mutable borrows.
I probably missed a trillion other things. Any suggestions on this? Thanks!
use rug::Integer;
use rug::ops::Pow;
use std::collections::HashMap;
pub fn fast_fibonacci(target_n: usize) -> Integer {
let cache: HashMap<usize, Integer> = HashMap::new();
let (result, _) = fib_dijk(target_n, cache);
return result
}
fn is_even(n: usize) -> bool {
return n & 1 == 0
}
fn fib_dijk_helper(target_n: usize, cache: HashMap<usize, Integer>) -> (Integer, HashMap<usize, Integer>) {
if target_n <= 1 {
return (Integer::from(target_n), cache)
} else {
let half_n = target_n >> 1;
let (x, cache) = fib_dijk(half_n, cache);
let x_2 = Integer::from((&x).pow(2));
if is_even(target_n) {
let (y, cache) = fib_dijk(half_n-1, cache);
let result = 2*x*y + x_2;
return (result, cache)
} else {
let (z, cache) = fib_dijk(half_n+1, cache);
return (x_2 + z.pow(2), cache)
}
}
}
fn fib_dijk(target_n: usize, cache: HashMap<usize, Integer>) -> (Integer, HashMap<usize, Integer>) {
if cache.contains_key(&target_n) {
return (cache.get(&target_n).unwrap().clone(), cache)
} else {
let (result, mut cache) = fib_dijk_helper(target_n, cache);
cache.insert(target_n, result.clone());
return (result, cache)
}
}
