Fibonacci with memoization - how to store hashmap

code review
#1

I'm going through the book again, since I'm a bit rusty on Rust :stuck_out_tongue_winking_eye:

I'm at chapter 3 now and I've implemented a function to calculate the nth Fibonacci number. To test, I run a loop from 1 to 99 and calculate the Fibonacci term at each number. I want it to memoize the values, because currently it is getting slow at about n = 40 because it's doing the work of calculating all terms down to term 1 each time.

I want to save the nth Fibonacci term in a hashmap with key = n and value = Fib(n) and first check my map before calculating all the terms down to term 1 again.

However, the map would need to be declared in a scope bigger than that of the function. This is now my problem. What is the best way of achieving that? static mut? I know that's not very popular here for good reason. static RefCell? Anything else?

My fibonacci function for reference:

fn fibonacci(n: usize) -> u128 {
    if n == 1 {
        1
    } else if n == 2 {
        1
    } else {
        fibonacci(n - 1) + fibonacci(n - 2)
    }
}
#2

once_cell+Mutex if you want multi-threaded caching, and thread_local+RefCell for single-threaded caching.

fn fibonacci(n: usize) -> u128 {
    thread_local! {
        static CACHE: RefCell<HashMap<usize, u128>> = Default::default();
    }

    // or
    
    use once_cell::sync::Lazy;
    static Lazy<Mutex<HashMap<usize, 128>>> = Lazy::new(Default::default);

    if n == 1 {
        1
    } else if n == 2 {
        1
    } else {
        fibonacci(n - 1) + fibonacci(n - 2)
    }
}
1 Like
#3

It's never static mut. Why don't you just pass it as an argument?

fn fibonacci(n: usize, cache: &mut HashMap<usize, u128>) -> u128 {
    if n < 2 {
        1
    } else if let Some(&result) = cache.get(&n) {
        result
    } else {
        let result = fibonacci(n - 1, cache) + fibonacci(n - 2, cache);
        cache.insert(n, result);
        result
    }
}

You can always use this with a global cache if needed. But you probably don't need to; it's perfectly usable with a HashMap that you declare inside main(), for example.

Even better: since your keys are always going to be consecutive integers, and due to the recursion structure of the function, it's always going to be filled from 0 to n, you can do it more efficiently using a plain old Vec:

fn fibonacci(n: usize, cache: &mut Vec<u128>) -> u128 {
    if n < 2 {
        1
    } else if let Some(&result) = cache.get(n) {
        result
    } else {
        let result = fibonacci(n - 1, cache) + fibonacci(n - 2, cache);
        cache.resize(n + 1, result);
        result
    }
}
3 Likes
#4

I know this is a bit contrived because it's an exercise in memoisation and not writing performant code, but with something as trivial as fibonacci you'll find the overhead from cache lookups will be orders of magnitude more than just using a more efficient algorithm.

When I was first learning about memoisation in Python, I was using Redis to cache intermediate fibonacci terms and wondered why the memoising version was 1000x slower than the naive one :sweat_smile:

2 Likes
#5

That does seem like a real enterprise™ solution, though!

1 Like
#6

If you are looking for a challenge...

How about a Rust entry for the The Million Digit Fibonacci Number Challenge:
GitHub - ZiCog/fibo_4784969: The million digit Fibonacci number challenge. Calculate fibo(4784969) in various languages.

The challenge being to write a program that produces all the digits of the first Fibonacci number that has one million digits, which happens to be fib(4784969), without using any library that is non-standard to the language.

I have been contemplating rewriting my C++ solution in Rust for some time but have been too afraid to make a start! That solution uses the Karatsuba algorithm for big integer multiplication and an optimised fibo algorithm. It is the fastest solution so far.

I posed the fib(4784969) challenge a while ago on the Raspberry Pi forum only because I wanted to show off how easy it was to do in Python with it's big integer capability. But things got out of hand and soon I had challengers in all kind of languages, as you see in the repo.

Still missing a solution in Rust...

2 Likes
#7

Just to pile on the alternative algorithms conversation, you can achieve a linear algorithm without appeal to memoization or the closed-form expression, by simply avoiding recursion and keeping track of two values at a time. And if u128 is indeed large enough, put those 180-some results in a hardcoded array for a constant-time solution :slight_smile: .

Practical note: If you're not going to go with some sort of BigNums, returning a Result or Option to signal overflow is a more correct approach.

Peeking at the book, they might have expected you to use a loop instead of recursion. Or just not have cared if your solution was efficient, being such an early chapter, heh.

#8

I have quickly whipped up a solution using naïve ripple-carry adding. It's slow (O(N^2)), but it runs in reasonable time (little less than 4 minutes on my 2015 MacBook). It's here.

How do you count Fibonacci numbers? What is fib(0), fib(1)? Is it…

  • (0, 1)? (the convention I like)
  • (1, 1)?
  • (1, 2)?

Using my own convention as marked above, the result is here. The program printed the hexadecimal representation, which I then converted to decimal using Python.

2 Likes
#9

For the million digit challenge we counted such that:

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
...
Which is the same as Wolfram: fibonacci(4) - Wolfram|Alpha

Looks like you have the correct answer there. Now for some optimisation. I just tried my C++ version, in the repo linked above, on my new MacBook Pro M1. It does it in about 160ms using multiple cores. Or about 500ms on a single core.

An unmentioned rule of the challenge is that the program has to produce the digits, in decimal, itself. And no non-standard language features or libraries of ones selected language to be used.

Interestingly when one does this with Python using it's big integer capability, which uses gmp under the hood I believe, the calculation proceeds very quickly but producing the digits to print takes ages.

My solution uses arrays of 64 bit integers to hold the big integers. Each element holding a "digit" of the big integer in base ten billion. This makes it very quick to produce the decimal result at the end.

It uses the Karatsuba algorithm for multiplication of big integers. You will find a few examples of fast fibo algorithm in there. The one I used was developed from this page: Fast Fibonacci algorithms

Of course that pesky GMP library has a big fibonacci function built in that is way faster :frowning:

#10

It's not recursion per se that causes the slowdown, but the exponential growth of the process; it's possible to write a linear recursive algorithm that can find fibonacci(99) without breaking a sweat, even in debug mode. (With optimizations it looks like it compiles to a loop, so it doesn't even waste stack space. Perhaps someday we will have the become keyword to formalize that.)

Of course this is morally equivalent to just writing a loop, so maybe it doesn't have the aesthetic appeal of the simple O(2n) recurrence formula.

#11

Yeah, often a recursive algorithm is a nice "divide and conquer" optimisation. Like quick sort, FFT or karatsuba etc. But that recursive fibo is an exercise in divide and multiply the amount of work to do by two. Or worse.

#12

I think the beauty of the naive recursive solution for Fibonacci is in that it flows directly from the mathematical definition. It's literally just the definition translated from mathematical language to Rust. A loop or the linear recursion @trentj gave isn't as obviously correct. I need to check and think through it.

I do think memoization will help my algorithm. `fibonacci(40) is the first one to take seconds to run. This means that lookup for anything from 40 and above will need to have a performance penalty of seconds to slow the code down, which I believe to be unlikely :stuck_out_tongue_winking_eye: I'll of course have to test.

However, I think the suggestion by @H2CO3 to use a Vec instead of HashMap is very good. (Why didn't I think of it!)

@RustyYato since there is std::lazy::Lazy now, which should be preferred? Lazy or once_cell?

#13

You also gave me a nice rabbit hole to dive into in finding faster Fibonacci algorithms... Thanks!

#14

They are the same :slight_smile: , but given that Lazy is only on nightly, it's not available to everyone just yet.

1 Like
#15

Just realized it's only on nightly. rust-analyzer almost made me excited!

#17

How so? The loop is perfectly obvious: if you need to sum the previous two numbers to get to the next one, you just store the last two. Since there's literally no more to the algorithm, it doesn't require any particular clever insight or transformation.

#18

True, but it isn't quite as brain dead as taking the mathematical definition that Fib(n) = Fib(n-1) + Fib(n-2); Fib(0) = 0 and Fib(1) = 1 and literally just translating to Rust (or whatever other language).

#19

This is one of those cases where I think functional programming takes a perfectly simple solution and turns it into a complicated mess.

The world may be built on mathemetics, but mutability and iteration are every bit as valid concepts as function application.

The simple solution (that also gets F(0) correct):

fn main() {
    for n in 0..20 {
        println!("{}", fib(n))
    }
}

fn fib(n: usize) -> usize {
    let mut low = 0;
    let mut high = 1;
    if n == 0 {
        low
    } else {
        for i in 1..n {
            let old_low = low;
            low = high;
            high = old_low + high;
        }
        high
    }
}

Of course this doesn't check for overflow.
If I needed to cache the results, I'd just throw them in a vec and pass it as an argument, doing a O(1) lookup in the vec and pushing new results if they aren't already there.

#20

That is an interesting view of the Fibonacci.

I have been puzzling for a decade or two now why that recursive fibo is so often seen as an early example in so many tutorials about this programming language or that. It seemed totally nuts to me. For reasons:

  1. When we were taught about Fibonacci in early high school maths it was in terms of taking a 0 and a 1 and adding them. Then taking the result and that second number and adding them. And so on. It was an iterative loop. That is how we did it with pencil and paper.

  2. When it came to my first steps in programming, some years later in BASIC, of course we did it as that iterative loop. Being totally ignorant of any other way to think about it. Besides, how would you do recursion in line good old fashioned line numbered BASIC? Who would want to do recursion in assembler unless one had to?

  3. Recursion was an "advanced" programming technique. Something my friends studying CS at university talked about. We had high level programming languages that did not support recursive functions. In fact, in my whole career I don't recall ever coding a recursive solution to anything.

  4. The performance sucks. Obviously.

In short, from my end of the telescope, the recursive algorithm is not the "naive" solution. It is an advanced concept, complicating the simple idea.

Now a days, being much older but little wiser, I admire the beauty of the recursive fibo and it's relation to the mathematical definition. Still, performance sucks but it is a way to test the call/return efficiency of ones language/processor.

1 Like
#21

I thought the recursive algorithm was a way to teach Fortran programmers about recursion.

2 Likes