sponsors gamedev.net search:

Memoized Fibonacci Memoization literally means "putting into memory". An alternative name for it is caching. Caching is familiar from the hardware world, where a cache is that small amount of fast but expensive memory where the CPU keeps recent data from the RAM (which is considerably slower than cache), thus avoiding some costly RAM accesses and saving execution time. In programming, Memoization plays a role similar to a hardware cache. It is a technique used to speed up computer programs by saving intermediary answers for later use, rather than recomputing them. If you look at the call tree for fib_rec(5), you can see that many (most!) of the calls may be avoided by saving their results in earlier calls. In fact, there's no real need to compute the Fibonacci number at any index more than once, so five fib_rec calls would do for fib_rec(5), and not 15 as it currently is. So what should we do in order to memoize the Fibonacci computation? First, we should set up some data structure to serve as a cache of computations. Then, when being asked to compute a Fibonacci number we should first consult the cache. If the result is in cache, it can be returned without any further computations. If it isn't in the cache - it means we haven't computed it yet, so we compute it and add it to the cache. Let's see how this is translated to code: long fib_memoized_aux(vector<long>& cache, long index) { if (cache[index] >= 0) return cache[index]; cache[index] = fib_memoized_aux(cache, index - 1) + fib_memoized_aux(cache, index - 2); return cache[index]; } long fib_memoized(long index) { vector<long> cache(index + 1, -1); cache[0] = 0; cache[1] = 1; return fib_memoized_aux(cache, index); } Here, fib_memoized acts exactly as the simple fib_rec - it takes an index as an argument and returns the Fibonacci number at this index. Internally, it first sets up a cache (for such a simple task a vector is enough - the ith vector cell holds the computed ith Fibonacci number, with -1 meaning a yet-uncomputed result), and uses fib_memoized_aux as a helper function for the computations. In fib_memoized_aux, you can see memoization in action, just as described above. What about performance, then? While up to about 30, fib_rec and fib_rec_memoized are comparable in execution time, afterwards the difference is staggering. For example, computing the 47th Fibonacci number takes ~47 seconds with fib_rec. With fib_rec_memoized it takes 0 (below resolution of system clock). There's no doubt that the difference gets bigger and bigger after that. There's another major speed-improvement here, which may not be immediately obvious. Imagine that during the runtime of our program, we need to calculate Fibonacci numbers not just once, but many times. While using the plain method we'd go through the computations again and again, using memoization we can just reuse the cache from call to call. Chances are that most of the computations will be answered in constant time - because the result will already be in the cache! The assiduous reader may implement a simple class for Fibonacci number calculation. This class will have the cache as a member, which will be initialized only once. The Fibonacci calculation method will use this cache and update it at times (when yet un-calculated results are requested). Alternative Fibonacci implementations Personally, I don't feel good about the Fibonacci calculation example. Though it's educationally sound, I find it somewhat contrived. This is because there are fast implementations for Fibonacci calculations that don't require memoization. For example, it's very easy to come up with a simple iterative solution. Since a Fibonacci number is simply a sum of the previous two, we can use a loop and keep track of just two numbers to generate any Fibonacci: long fib_iter(long index) { if (index < 2) return index; long cur = 1; long one_back = 0; for (long i = 2; i <= index; ++i) { long temp = cur; cur = cur + one_back; one_back = temp; } return cur; } This will calculate Fibonacci numbers as fast as the memoized implementation - in linear time. An even faster solution can utilize Binet's Fibonacci number formula: long fib_binet(long index) { double sqrt_5 = 2.2360679774997896964091736687313; return (long) floor((pow(1 + sqrt_5, index) - pow(1 - sqrt_5, index)) / (pow(2, index) * sqrt_5)); } Don't just sit there and gasp in horror :-) Calculation of Fibonacci numbers is a fascinating topic and you can learn alot by browsing the web a little - start by Googling for "Fibonacci numbers". I must note, just to be fair, that these fast non-recursive implementations lack the caching-between-calls property of memoization. That is, if we use memoization to save results between function calls (discussed in the last paragraph of the previous section); we can get most results at a cost of a trivial array look up - faster than the non-recursive implementations. But to be even more fair, huge Fibonacci numbers are rarely needed in practice, and even when they are, the iterative or the formula implementations can provide us with as big numbers as we'll even need in negligible time. So let's examine another problem, where there is no simple alternative to the recursive solution. Counting change

Contents   Recursion   Memoized Fibonacci   Counting change   Printable version   Discuss this article The Series   Part 1   Part 2   Part 3   Part 4   Part 5   Part 6   Part 7   Part 8