0
$\begingroup$

My question is bolded within the text below.

Memoization speeds up a recursion that needs to recall a prior rule other than the last one calculated. For instance, on my machine, the following take 0.0003 s and 7 s, respectively, each on fresh kernels (the first code block is with memoization, and the second is without):

fMem1[1] = 1; fMem1[2] = 1;(* run on fresh kernel *)
fMem1[x_] := fMem1[x] = fMem1[x - 1]^2 - fMem1[x - 2] + 1;
t = AbsoluteTime[];
fMem1[33];
AbsoluteTime[] - t

f1[1] = 1; f1[2] = 1;(*run on fresh kernel*)
f1[x_] := f1[x - 1]^2 - f1[x - 2] + 1;
t = AbsoluteTime[];
f1[33];
AbsoluteTime[] - t

This makes sense since, to calculate f(n), Mathematica needs both f(n-1) and f(n-2). Yet, in the absence of memoization, all that is stored is the previously-calculated rule for f(n), which is now f(n-1). All those before it have been overwritten which, in this case, means Mathematica has to repeatedly recalculate f(n-2).

Conversely, and consistent with the above, when the recursion requires only a single call to the previously-calculated rule, memoization provides no speed benefit (unless, of course, you need to rerun the recursion on the existing kernel, in which case memoization's rule caching will obviate the need to recalculate prior rules). For instance, the times for both of these are 3 s:

fMem2[1] = 1;(* run on fresh kernel *)
fMem2[x_] := fMem2[x] = 2*fMem2[x - 2]^3+1;
t = AbsoluteTime[];
fMem2[37];
AbsoluteTime[] - t

f2[1] = 1; (* run on fresh kernel *)
f2[x_] := 2*f2[x - 2]^3+1;
t = AbsoluteTime[];
f2[37];
AbsoluteTime[] - t

Why, then, does memoization provide a speed-up when the recursion only requires the previously-calculated rule, but that rule is called more than once (i.e., is present in more than one term)? It's as if the cached rule for the previous f(n) (which, here, is now f(n-1)) is overwritten after the first time it is used in an expression. Here the version with memoization takes 0.0003 s; that without takes 34 s:

fMem3[1] = 1;(* run on fresh kernel *)
fMem3[x_] := fMem3[x] = fMem3[x - 1]^2 - fMem3[x - 1] + 1;
t = AbsoluteTime[];
fMem3[25];
AbsoluteTime[] - t

f3[1] = 1;(* run on fresh kernel *)
f3[x_] := f3[x - 1]^2 - f3[x - 1] + 1;
t = AbsoluteTime[];
f3[25];
AbsoluteTime[] - t
Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ f3[x_] := f3[x - 1]^2 - f3[x - 1] + 1 requires two calls to f3[x - 1], which require four calls to f3[x - 2], etc. exponentially. This is because f3[x_] is defined with a delayed assignment and might have side-effects, so cannot be auto-cached by the kernel. If you define counter = 0; f3[x_] := (counter++; f3[x - 1]^2 - f3[x - 1] + 1); then after calling f3[25] we have counter equal to $16777215=2^{24}-1$, showing the exponential calling pattern. $\endgroup$
    – Roman
    Mar 29, 2022 at 10:17
  • $\begingroup$ In short, without memoization the values get recomputed. If they are defined recursively that can be slow, in particular if there is more than one recomputation per step. (@Roman and @DanielHuber explain this quite well, I'm just summarizing.) $\endgroup$
    – Daniel Lichtblau
    Mar 29, 2022 at 15:08
  • $\begingroup$ I feel this explained in this old Q&A: mathematica.stackexchange.com/questions/2639/… $\endgroup$
    – Michael E2
    Mar 29, 2022 at 17:04
  • $\begingroup$ @Roman As you know, I'm trying to understand why I see a timing benefit when memoization is added to a recursion like f[x_]:= f[x-1] +f[x-1]+1, but not with f[x_]:= f[x-1]+1. It sounds like you're saying that memoization speeds up the recursion in both cases, because prior values are never cached in its absence. Thus withf[x_]:= f[x-1] +1, a call is required to f[x-1], which in turn requires a call to f[x-2], and so on. With memoization, by contrast, such recalculation would not be needed. $\endgroup$
    – theorist
    Mar 30, 2022 at 3:56
  • $\begingroup$ However, because in this case the number of calls does not grow exponentially the way it would with f[x_]:= f[x-1]+f[x-1] +1, the advantage of memoization is far less, which is why I don't see the timing difference. Do I have that right? If so, it seems that, if f[x] were a temporally expensive calculation, then I should see a timing difference even with just one call. i.e., even in the absence of an exponential growth in the number of required calculations.Integrate[1 /( Sinh[z] ), {z, 1, 10}] is relatively expensive, so I compared $\endgroup$
    – theorist
    Mar 30, 2022 at 4:07

2 Answers 2

Reset to default
1
$\begingroup$

Memoization helps as soon as you need a value more than once.

In your example:

fMem2[1] = 1;(* run on fresh kernel *)
fMem2[x_] := fMem2[x] = 2*fMem2[x - 2]^3+1;

every value of fMem2 is only calculated once. Therefore, no speed up from memoization. However, if you run this example again, there will be a hugh speed up.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Daniel, thanks for your post, but I'm not asking why memoization allows for a huge speed-up when MMA repeats a calculation in an existing kernel. Indeed, as I state in my OP, "(unless, of course, you need to rerun the recursion on the existing kernel, in which case memoization's rule caching will obviate the need to recalculate prior rules)". Rather, I'm asking why, on a fresh kernel, I see a timing benefit when memoization is added to a recursion like f[x_]:= f[x-1] +f[x-1]+1, but not with f[x_]:= +f[x-1]+1. For more details, see my reply to Roman. $\endgroup$
    – theorist
    Mar 30, 2022 at 3:57
  • $\begingroup$ As I already said, in the first case you calculate f[x-1] twice and memoization helps, but in the second case onle once and memoization does not help. $\endgroup$
    – Daniel Huber
    Mar 30, 2022 at 14:10
  • $\begingroup$ I'm confused because I thought Daniel L. and Roman (who agree with your description) were saying that values always have to be recomputed (i.e., calculated more than once) without memoization, because they "cannot be auto-cached by the kernel." Hence it sounded like they were saying that, without memoization, the difference between, say, f[x_]:=2*f[x-1] +1 and f[x_]:=f[x-1]+f[x-1]+1 is that, in the latter case, the number that need to be recomputed grows far faster (exponentially) with x (i.e., that recomputation is needed in both cases, and the difference is a matter of degree). $\endgroup$
    – theorist
    Mar 30, 2022 at 17:54
  • $\begingroup$ Wrong, in the second case without memoization you need do calculate f[x-1] twice what takes double the time, not exponentially. $\endgroup$
    – Daniel Huber
    Mar 30, 2022 at 19:16
  • $\begingroup$ So you disagree with Roman's comment that "f3[x_] := f3[x - 1]^2 - f3[x - 1] + 1 requires two calls to f3[x - 1], which require four calls to f3[x - 2], etc. exponentially."? Note that I wasn't referring to the time it takes just to recompute the prior values, but the time it takes to compute the entire recursion, and how that varies with x in the absence of memoization. And if it's double for x-1, four-fold for x-2, eight-fold for x-3, that's 2^x, and thus exponential. $\endgroup$
    – theorist
    Mar 30, 2022 at 21:40
1
$\begingroup$

As a clarifying addition. It is not obvious for Mathematica that identical calls to the same function from the same expression should always result in the same outcome. To clarify this statement consider the following function definition:

f[x_] := RandomReal[x] - RandomReal[x]

If one would assume that both calls to RandomReal would produce the same output this should always give zero, but it outputs a random number between -x and x.

This means that when evaluating the definition

f3[x_] := f3[x - 1]^2 - f3[x - 1] + 1;

Mathematica cannot assume both calls to f3[x-1] produce the same output. Instead each call starts its own iterative procedure to determine f3[x - 1]. (Which then quickly snowballs out of control.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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