2
$\begingroup$

A standard way to speed up the creation of Fibonacci numbers is by memoization

Instead of:

fib1[0] = 0;
fib1[1] = 1;
fib1[n_] := fib1[n - 1] + fib1[n - 2];

One can do:

fib2[0] = 0;
fib2[1] = 1;
fib2[n_] := fib2[n] = fib2[n - 1] + fib2[n - 2];

I created a third way, like this:

frules = {fib3[1] -> 1, fib3[0] -> 0, 
   fib3[n_] :> fib3[n - 1] + fib3[n - 2]};

Now, if I compare the timings of the three strategies, the third one is much faster than the first one, but much slower than the second one. My question is: what is happening "under the hood" that creates this timing behaviour of the third strategy in comparison to the other two?

fib1[35] // Timing
fib2[35] // Timing
fib3[35] //. frules // Timing

{22.75, 9227465}

{0., 9227465}

{1.5625, 9227465}

$\endgroup$
  • 2
    $\begingroup$ My guess is that Mathematica scans the list of rules linearly until it finds one that applies, so the first algorithm is exponential time, the second linear time, the third is quadratic time (I know, it does not explain the full slowdown, but still...) $\endgroup$ – Igor Rivin Aug 19 '17 at 21:09
  • $\begingroup$ @IgorRivin Why is the third method quadratic? $\endgroup$ – GambitSquared Aug 20 '17 at 18:08
4
$\begingroup$

Memoization means almost optimal number of unique calculations.

The first guy is the worst: keeps repeating same calculation again and again and again and doesn't have the benefit of aggregating sums. (i.e. look at the output of Trace[fib1[6]] -- it's splitting the evaluation tree every level, recursing all the way down, so not summing until it sees actual number, meaning maximal number of repeated evaluations.).

The third has the benefit of addition regrouping. You can see this from something as simple as coding up your own version of //. using FixedPoint, which giving us the benefit of allowing a window of what happens on each level:

ClearAll[c]; Timing[FixedPoint[(# /. frules // Echo) &, fib3[6]]]

fib3[4]+fib3[5]

fib3[2]+2 fib3[3]+fib3[4]

fib3[0]+fib3[1]+fib3[2]+2 (fib3[1]+fib3[2])+fib3[3]

1+fib3[0]+2 fib3[1]+2 (1+fib3[0]+fib3[1])+fib3[2]

7+fib3[0]+fib3[1]

8

8

See how at level 2, since the sum happened before the rule is applied, there's already an improvement over naive w/ 2 fib3[3] only needing one replacement of fib3[3] instead of the two that happens in fib1[3] evaluations at this level. And this happens more and more as you progress in levels, which really adds up. This means huge gains relative to naive especially once we start w/ something that allows a nice eventual depth like fib3[35].

This also suggests an improvement over the original repeated rule application, which is an Expand that means each rule only has to apply once per level. This isn't going to beat memorizing all output so you only have to calculate a minimal number of times, and there's an expense with the expand, but it more than makes up for itself eventually against straight repeated rules. It achieves parity with //. for my laptop at around depth 10, and absolutely dominates by 35:

Timing[ FixedPoint[(# /. frules // Expand) &, fib3[35]]]

{0.002129, 9227465}

Timing[fib3[35] //. frules]

{1.48958, 9227465}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.