Algorithm Fight Club: Fibonacci 3 Ways

Today we have a triple threat match over one of the oldest sequences of numbers in the world, the Fibonacci sequence. Which technique will conqueror this ancient integer sequence? Let’s go to the Tale of the Tape.

Tale of the Tape
Recursive Dynamic Programming Template Meta-Programming
Time
2^n n 1
Space
n n 1

Wait what? Fight’s over before it started, but what exactly is this Template Meta-Programming and why isn’t it used to solve every problem? Before we answer that, let’s start with the competition.

Our recursive approach is very simple, create a recursive function that calls n-1 and n-2 until it hits a base case. Unfortunately basic recursion loses out to the fact that the same calculations are done in branching. Think about f(6), it is the sum of f(4) and f(5). f(4) = f(3) + f(2) and f(5) = f(4) + f(3). See the problem already? In just one iteration, we already have to calculate f(3) and f(4) twice. This is a no go.

Our second approach takes care of that issue. The dynamic programming approach will store previously computed terms like f(3) and f(4), therefore avoiding re-computing them again. For a Fibonacci sequence, this is done with an iterative loop building from 1 to n. This is a great solution but it can be beat.

Enter the dark horse, Template Meta-Programming. Now these stats come with some caveats. First, this is generally only available in C++ (though other languages can rig similar techniques). Second, the calculations happen at compile time not run time, thus giving an O(1) run-time complexity. Third, this is not done dynamically and so a max n must be decided on before compilation.

On a very high level, Template Meta-Programming uses C++ templates to building compile time data structures or complete functions. What this means is that you can pre-solve all the solutions of an algorithm if you know the max input. In our Fibonacci showdown, the Template Meta-Programming approach will build all the solutions for inputs up to a chosen n, thus having it available at run-time.

TL;DR Use dynamic programming because compile time table building is cheating

Leave a Reply

Your email address will not be published. Required fields are marked *