Some(number) of ways to calculate a Fibonacci Number in Rust

I write a fibonacci fn several ways, exploring the Rust and timing in different versions

A Fibonacci spiral found in nature, in a nautilus shell.
A Fibonacci number divided by the previous one approaches Phi, the Golden Ratio. That’s an Internet hole that can last for hours, if you let it! However, don’t believe everything you read about Phi.

Solving Fibonacci Numbers is the start of Chapter 3 on Dynamic Programming (more on that below) in Erickson’s Algorithm book. I had started with Peasant Multiplication, then the merge sort, and most fun – the n Queens Problem. With Fibonacci Number calculating though, there are a couple of obvious ways to code this and some presented questions for me with Rust.

I became interested in comparing a couple of these ways – both in thinking about the Rust code and looking at the timing. Then my eyes popped out when I saw the difference in the release build times!

Recursive Backtracing

Pseudo code, Page 97 from Algorithm by Jeff Erickson
Clean, Simple Recursion

First is probably closest to the pseudo code for the classic solution for Fibonacci. Define what 0 and 1 return and solve for the given number, recursing all the way back to 2 (which adds the fixed answers for 0 and 1):

fn backtrace_fib(fib_num: u128) -> u128 {
    if fib_num == 0 || fib_num == 1 {
        return fib_num;
    }
    backtrace_fib(fib_num - 1) + backtrace_fib(fib_num - 2)
}

Backtracing With Memoization

Next, especially important if your function will be called multiple times, is to add memoization. That is, once you calculate an answer for a given input, remember than answer so you can quickly respond with it later, skipping the math.

I don’t like that, with the way I did this, I have to pass in my HashMap where I’m storing the answers. Is there any way to have some `static living private variable that only this function would see, but would last the whole run of the program?? There are other places I could store away data, like memcache and redis.

fn backtrace_memo_fib(memo: &mut HashMap<u128, u128>, fib_num: u128) -> u128 {
    match memo.get(&fib_num).map(|answer| answer.clone()) {
        Some(result) => result,
        None => {
            let result = match fib_num {
                0 | 1 => fib_num,
                n => backtrace_memo_fib(memo, n - 1) + backtrace_memo_fib(memo, n - 2),
            };
            memo.insert(fib_num, result.clone());
            result
        }
    }
}



Dynamic Programming

So, Jeff Erickson, author of the Algorithms book, explains another way solve for a Fibonacci Number involves using dynamic programming. But this IS your grandfathers “programming” (not ours).

The word ‘programming’ does not refer to writing code, but rather to the older sense of planning or scheduling, typically by filling in a table. For example, sports programs and theater programs are schedules of important events (with ads); television programming involves filling each available time slot with a show (and ads); degree programs are schedules of classes to be taken (with ads).

Erickson, Jeff (2018, December 29). Algorithms. pp. 100. Retrieved from Algorithms: http://algorithms.wtf

For this one, I just kept the memoization inside the function. We then purposely fill the HashMap on our way up, referencing already-calculated answers, and so never descend into levels of recursion.

Pseudo code, Page 99 from Algorithm by Jeff Erickson
fn dynamic_fib(fib_num: u128) -> u128 {
    let mut memo = HashMap::new();
    memo.insert(0, 0);
    memo.insert(1, 1);
    match fib_num {
        0 | 1 => {} // already set
        n => {
            for i in 2..=n {
                let result = *memo.get(&(i - 1)).unwrap() + *memo.get(&(i - 2)).unwrap();
                memo.insert(i, result);
            }
        }
    };
    *memo.get(&fib_num).unwrap()
}

Cached Backtracing Function

So, as I was trying to figure out how to store some data in a function for future calls (if that is even possible), I came across the cached crate. “cached provides implementations of several caching structures as well as a handy macro for defining memoized functions.” How interesting – just what I needed and the memoization is even hidden from ME. Ok, I’ll do the simple, recursive, backtracing function but cache the results.

#[cached(size = 200)]
fn cached_fib(fib_num: u128) -> u128 {
    if fib_num == 0 || fib_num == 1 {
        return fib_num;
    }
    cached_fib(fib_num - 1) + cached_fib(fib_num - 2)
}

Fibonacci Fight

So, I wrap all of those up into main() so I can start comparing them. That code is pretty boring, so check it out in the repo. Mostly I run each flavor of the algorithm, timing the result and print it all out. The first one looks like:

    let now = Instant::now();
    let _ = backtrace_fib(fib_num);
    let elapsed = now.elapsed();
    print_results(fib_num, "simple backtracing/recursion", elapsed);

I also added a test, just to be sure each is giving the correct answer.

#[test]
fn test_each_version() {
    assert_eq!(backtrace_fib(20), 6765);
    assert_eq!(backtrace_memo_fib(&mut HashMap::new(), 20), 6765);
    assert_eq!(dynamic_fib(20), 6765);
    assert_eq!(cached_fib(20), 6765);
}

Fibonacci Racing

And then some code to time each version, and call it a second and third time, so we can see the memoization at work.

Of course, your results will vary by CPU, but look at this run for Fibonacci Number 50 with the debug build (where the differences are huge). This is on an Amazon t2.medium EC2 server:

The first time solving will be the slowest

Solving fib:50 with simple backtracing/recursion took     287244288946 ns
Solving fib:50 with backtracing/recursion with memoization took 211289 ns
Solving fib:50 with dynamic programming with memoization took   167291 ns
Solving fib:50 with cached function took                        214175 ns

What about solving it a second or third time, anyone faster this time?

Solving fib:50 with simple backtracing/recursion took     287262389809 ns
Solving fib:50 with backtracing/recursion with memoization took 202481 ns
Solving fib:50 with dynamic programming with memoization took   162527 ns
Solving fib:50 with cached function took                          6285 ns

Solving fib:50 with simple backtracing/recursion took     287273113221 ns
Solving fib:50 with backtracing/recursion with memoization took 185609 ns
Solving fib:50 with dynamic programming with memoization took   158492 ns
Solving fib:50 with cached function took                          6496 ns

By the way, Fibonacci Number 50 is 12586269025 which (divided by Fib Num 49) approximates phi as 1.618033988749895

But wow, check out these numbers with a release build!!

The first time solving will be the slowest

Solving fib:50 with simple backtracing/recursion took              806 ns
Solving fib:50 with backtracing/recursion with memoization took  16128 ns
Solving fib:50 with dynamic programming with memoization took     8052 ns
Solving fib:50 with cached function took                         19495 ns

What about solving it a second or third time, anyone faster this time?

Solving fib:50 with simple backtracing/recursion took             596 ns
Solving fib:50 with backtracing/recursion with memoization took  8142 ns
Solving fib:50 with dynamic programming with memoization took    7576 ns
Solving fib:50 with cached function took                          724 ns

Solving fib:50 with simple backtracing/recursion took             596 ns
Solving fib:50 with backtracing/recursion with memoization took  7549 ns
Solving fib:50 with dynamic programming with memoization took    7327 ns
Solving fib:50 with cached function took                          746 ns

By the way, Fibonacci Number 50 is 12586269025 which (divided by Fib Num 49) approximates phi as 1.618033988749895

A Really Big Number

And it handles a Fibonacci Number of 186, though any higher and casting the answers as f64s to divide and get Phi breaks. The fastest “first” calculation for Fibonacci Number 186 was simple backtracing/recursion and took only 820 ns and it’s kinda big:

By the way, Fibonacci Number 186 is 332825110087067562321196029789634457848 which (divided by Fib Num 185) approximates phi as 1.6180339887498947

Update #1

unreliablebazooka on reddit points out my dynamic_fib is a poor use of a HashMap and offered a suggestion I now added as better_dynamic_fib. It uses a tuple (SO much easier and cleaner) and in the category of optimization, it only keeps the tuple around for the past 2 Fibonacci numbers in the chain, not the whole list. Much, much faster – the fasted first execution yet, in fact!

fn better_dynamic_fib(fib_num: u128) -> u128 {
    let mut memo = (0, 1);

    match fib_num {
        0 | 1 => fib_num,
        _ => {
            for _ in 2..=fib_num {
                memo = (memo.1, memo.0 + memo.1)
            }
            memo.1
        }
    }
}
First and additional runs:

Solving fib:20 with dynamic programming with memoization via tuple took 706 ns

Next Algorithm: Backtracking into the n Queens Problem

Where we place Queens on a chessboard far enough away from each other that they don’t fight – aka the n Queens Problem.

Chessboard showing a Queen... how would you function with multiple queens on the same board?.
Stalking her prey…

This next algorithm was really fun and a bit more challenging. The Algorithms book I’m going through went through several more examples of breaking a problem into a smaller, simpler problem and letting recursion CPU its way to a solution, like the merge sort we just looked at. Then I moved on to chapter 2 about “backtracking” into the n Queens Problem!

How Many Queens?

According to the book, the “n Queens Problem” is a prime example of using backtracking to solve a problem. Backtracking is another way to reduce a hard problem down into smaller chunks that are more easily solvable. In this case, showing the solution as it is worked out with a recursion tree model really explains well the approach used here. Go see page numbered 71 of the PDF to check it out. After just a couple of pages, Erickson moves on to the related topic of Game Trees, but this n Queens Problem seemed really fun to me.

I first wanted to try and show the solutions as text-based chessboards (plus allow for the boring array version showing one solution per line). It took me a little while to setup the Rust crate crossterm to help me out with this. I had only recently heard of crossterm while watching a YouTube video by David Pedersen as he codes up a simple Git helper with Rust. I didn’t go crazy with color or UTF-8 like I could have, but feel free.




Let’s Rust

Then came the matter of converting the algorithm pseudo code from the PDF into Rust code. This was slightly more difficult as Rust is very careful about array bounds checking and I had to be a little safer with my IF checks than the pseudo code warned about.

Since it is Creative Commons, I can include the pseudo-code presented in Jeff Erickson’s Algorithm book – but go check it out via his site!

Figure 2.2, Page 71 from Algorithm by Jeff Erickson

When you run the queens_problem binary, you pass along an argument of how big your chessboard square is. Optionally you can include a second param (of anything, the code doesn’t really care) which causes it to output chessboards rather than the array dumps.

main.rs for queens_problem

use crossterm::{
    style::{Color, Colors, Print, ResetColor, SetColors},
    ExecutableCommand,
};
use std::env;
use std::io::stdout;
const QUEEN: &str = "<W>";
const EMPTY: &str = "   ";
/// Adapted from reading "Algorithms" by Jeff Erickson
/// freely available on http://jeffe.cs.illinois.edu/teaching/algorithms/
pub fn main() {
    let args: Vec<String> = env::args().collect();
    // nothing fancy at all, just brute-force it
    if args.len() < 2 || args.len() > 3 {
        println!("Usage: {} n [show]", args[0]);
        println!("  n = size of chessboard");
        println!("  [show] to actually see each chessboard solution");
        return;
    }
    let boardsize = args[1].parse::<usize>().unwrap();
    let chessboard = vec![-1i8; boardsize];
    let showboard = args.len() == 3; // don't even care what it is
    place_queens(chessboard.clone(), 0, showboard);
}
fn show_chessboard(board: Vec<i8>, showboard: bool) {
    let mut light: bool = true;
    if showboard {
        for pos in board.to_vec() {
            for cell in 0..board.len() {
                match (pos == cell as i8, light) {
                    (true, true) => draw_square(Colors::new(Color::Black, Color::Grey), QUEEN),
                    (true, false) => draw_square(Colors::new(Color::Grey, Color::Black), QUEEN),
                    (false, true) => draw_square(Colors::new(Color::Black, Color::Grey), EMPTY),
                    (false, false) => draw_square(Colors::new(Color::Grey, Color::Black), EMPTY),
                };
                light = !light;
            }
            println!();
            if board.len() % 2 == 0 {
                // to checkerboard even-sized boards
                light = !light;
            }
        }
        println!("\n");
    } else {
        let adjusted: Vec<i8> = board.iter().map(|&p| p + 1).collect(); // lets remove the 0-based confusion
        println!("{:?}", adjusted);
    }
}
fn draw_square(color: Colors, chesspiece: &str) {
    let mut stdout = stdout();
    stdout.execute(SetColors(color)).unwrap();
    stdout.execute(Print(chesspiece)).unwrap();
    stdout.execute(ResetColor).unwrap();
}
/// n Queens Problem
/// Section2.1, page 69-71
fn place_queens(mut chessboard: Vec<i8>, row: usize, showboard: bool) {
    if row == chessboard.len() {
        show_chessboard(chessboard.to_vec(), showboard);
        return;
    }
    for column in 0..chessboard.len() {
        let mut legal = true;
        for cell in 0..row {
            let pos = cell as usize;
            if chessboard[pos] == (column as i8)
                || (column + row >= cell && chessboard[pos] == ((column + row - cell) as i8))
                || (column + cell >= row && chessboard[pos] == ((column + cell - row) as i8))
            {
                legal = false;
            }
        }
        if legal {
            chessboard[row] = column as i8;
            place_queens(chessboard.clone(), row + 1, showboard);
        }
    }
}

Just a Hint of Verification

As nerdy as they look, I used the array dumps to validate my code against what Wiki article on the 8 Queens Puzzle has as the number of valid solutions for different sized boards. I verified a 4×4 up to 14×14 board and matched the expected counts perfectly. Go check out the README for this repo in Github.

Merge Sort With Rust

Little cubes of letters to indicate alphabetical sorting with a mergesort
Quick, sort; no not with quicksort, with merge sort

Another algorithm to play with. Moving on in the Algorithms book I mentioned in the last post to section 1.4 we come across the merge sort. Another fun one to play with in Rust and to learn vectors just a little better. So let’s code up a quick merge sort with Rust!

Yes, I’m That Old

My AP computer class back around the mid 1980s was in Pascal. I later learned that Pascal was never meant to be used in production – it was a purely a teaching language – even to the extent it could be taught on paper and never even compiled. How terrible it would be not to see your first programs run!

Either way, we worked on terminals and Pascal worked out just fine for me. That language led me easily to C and, though I never used C professionally, that made for an easy transition to Perl (which I have) and to Rust! It turned out, the prior few years of AP tests had been bad enough across all the high schools, they decided to omit three sections of Pascal, unless you optionally wanted to learn them and take an extra AP test, which I did. These three subjects were: recursion (the algorithms both last time and this time use recursion), linked list (that broke my brain for a little while – I was glad later on that it happened in school because it made C so much easier to learn), and sorting (without any simple, built-ins).

Merging with Rust

I am sure I learned the simple merge sort back then, 35 years ago. Heck, that means it was only 40 years old when I learned it! The book only spends a couple of pages on it – it is just another example of a recursive algorithm. It was fun in Rust though, I learned some vector methods I wasn’t aware of like the various forms of split_at and concat. Again I made a couple of very simple tests just to help show it works.




Since it is Creative Commons, I can include the pseudo-code presented in Jeff Erickson’s Algorithm book – but go check it out via his site!

Figure 1.6, Page 27 from Algorithm by Jeff Erickson
“Merge, everybody merge!” – Bryan Regan, https://www.youtube.com/watch?v=KPrSHrIvWI4

So, here is the code I came up with:

main.rs for merge sort

use std::env;

#[test]
fn check_mergesort() {
    let letters = vec!["s", "a", "m", "p", "l", "e"];
    let shouldbe = vec!["a", "e", "l", "m", "p", "s"];
    let sorted = mergesort(letters);
    assert_eq!(sorted, shouldbe);

    let words = vec![
        "now", "is", "the", "time", "for", "all", "good", "men", "to", "come", "to", "the", "aid",
        "of", "their", "country",
    ];
    let shouldbe = vec![
        "aid", "all", "come", "country", "for", "good", "is", "men", "now", "of", "the", "the",
        "their", "time", "to", "to",
    ];
    let sorted = mergesort(words);
    assert_eq!(sorted, shouldbe);
}

/// Adapted from reading "Algorithms" by Jeff Erickson
/// freely available on http://jeffe.cs.illinois.edu/teaching/algorithms/
pub fn main() {
    let args: Vec<String> = env::args().collect();

    if args.len() < 2 {
        println!(
            "Usage: {} word word [word...] (two or more words to sort)",
            args[0]
        );
        return;
    }

    let words = args.iter().skip(1).map(AsRef::as_ref).collect();
    println!("Arrived: {:?}", words);

    let sorted = mergesort(words);
    println!("Sorted: {:?}", sorted);
}

/// Mergesort
/// Section 1.4, page 27
pub fn mergesort(words: Vec<&str>) -> Vec<&str> {
    if words.len() < 2 {
        return words;
    }

    let midpoint = (words.len() + 1) / 2;
    let (left, right) = words.split_at(midpoint);

    let left = mergesort(left.to_vec());
    let right = mergesort(right.to_vec());

    let halfsort = [left, right].concat();
    let sorted = merge(halfsort, midpoint);

    return sorted;
}

pub fn merge(words: Vec<&str>, midpoint: usize) -> Vec<&str> {
    let size = words.len();
    let mut left_index = 0;
    let mut right_index = midpoint;
    let mut sorted: Vec<&str> = Vec::new();

    for _ in 0..size {
        if right_index >= size {
            sorted.push(&words[left_index]);
            left_index += 1;
        } else if left_index >= midpoint {
            sorted.push(&words[right_index]);
            right_index += 1;
        } else if words[left_index] < words[right_index] {
            sorted.push(&words[left_index]);
            left_index += 1;
        } else {
            sorted.push(&words[right_index]);
            right_index += 1;
        }
    }
    return sorted;
}

There is not really much to say about it though – unless you have questions or suggestions. Check it out in the github repo.