Skip to main content
Mathematica

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Mar 30, 2022 at 21:40