16.7: Memorized Fibonacci

Last updated
Save as PDF

Page ID: 46426

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

As a small application of the techniques we have seen, consider the Fibonacci function (\( \mathit{fib}(n) = \mathit{fib}(n - 1) + \mathit{fib}(n - 2) \text{ with } \mathit{fib}(0) = 0, \mathit{fib}(1) = 1 \)). We will study two versions of it: a recursive version and a memorized version. Memoizing consists in introducing a cache to avoid redundant computation.

Consider the following definition, close to the mathematical definition:

Integer»fibSlow
    self assert: self >= 0.
    (self <= 1) ifTrue: [ ^ self].
    ^ (self - 1) fibSlow + (self - 2) fibSlow

The method fibSlow is relatively inefficient. Each recursion implies a duplication of the computation. The same result is computed twice, by each branch of the recursion.

A more efficient (but also slightly more complicated) version is obtained by using a cache that keeps intermediary computed values. The advantage is to not duplicate computations since each value is computed once. This classical way of optimizing program is called memoizing.

Integer»fib
    ^ self fibWithCache: (Array new: self)

Integer»fibLookup: cache
    | res |
    res := cache at: (self + 1).
    ^ res ifNil: [ cache at: (self + 1) put: (self fibWithCache: cache ) ]

Integer»fibWithCache: cache
    (self <= 1) ifTrue: [ ^ self].
    ^ ((self - 1) fibLookup: cache) + ((self - 2) fibLookup: cache)

As an exercise, profile 35 fibSlow and 35 fib to be convinced of the gain of memoizing.