# Memoization and finding already calculated DownValue

The problem of plotting an expensive function discussed in this question caught my attention. As an exercies I tried to solve it using memoization as follows

ClearAll[fn]
fn[0, a_] = 1;
fn[xEnd_, a_] :=
fn[xEnd, a] =
Module[{xPrev},(* Find the last known xPrev such that xPrev<xEnd *) ;
fn[xPrev, a] + NIntegrate[t^(a t), {t, xPrev, xEnd}]]


In the comment (* Find the last known xPrev such that xPrev<xEnd *), I need to add code to find a point xPrev such that xPrev<xEnd and fn[xPrev,a] is is already calculated. Basically, search within existing downvalues to see the highest xPrev satisfying the given condition that is already solved. Afterwards, I just calculate the portion of the integral from xPrev until the xEnd.

My question is: What is the best way to find this particular DownValue from within the fn? Is this in general a good practice?

Please do not focus specifically on the quoted problem. I just used it as a reference to describe the problem.

• you can grab the previously existing values via something like Cases[ DownValues@fn, fn[x_?NumericQ,_] :> x, Infinity] Commented Feb 6, 2017 at 20:56
• Tried already,but I'm having problems making heads and tails of those Hold, HoldPattern etc. Commented Feb 6, 2017 at 21:22

This is just a silly example to show how you can use Cases to grab the previously input values of a function and apply some test to them. Here the function is simply going to return a list of the largest previously input x that's smaller than the current x, and the sum of the two input values

ClearAll[fn]
fn[x_,a_]:= fn[x,a]= Module[{xprev},
xprev =Max @ Cases[
DownValues[fn],
HoldPattern[fn[xx_?(NumericQ[#]&&#<x&),_]]:>xx,
Infinity];
{xprev,x+a}
]

fn[1, a]
fn[2, a]
fn[75, a]
fn[36, a]
fn[-10, a]
fn[125, a]
(* {-∞, 1 + a} *)
(* {1, 2 + a} *)
(* {2, 75 + a} *)
(* {2, 36 + a} *)
(* {-∞, -10 + a} *)
(* {75, 125 + a} *)

• This is exactly what I was hoping to get. Commented Feb 7, 2017 at 10:36

One way to use memoization for computing integrals is to split the integral into many segments and evaluate them separately. So if you want to integrate from 1 to 10 for example, then you can integrate from 1 to 2, 2 to 3, 3 to 4 and so on. You can save each segment so that if you later want to integrate from 1 to 4 this can be done instantaneously using stored values.

This is what the implementation could look like:

fn[start_, a_] := fn[start, a] = NIntegrate[t^(a t), {t, start, start + 1}]

steps[start_, end_] := Range[Floor[start], Floor[end - 1]]

fn[start_, end_, a_] := Module[{first, last, intermediate},
first = NIntegrate[t^(a t), {t, Floor[start], start}];
last = NIntegrate[t^(a t), {t, Floor[end], end}];
intermediate = fn[#, a] & /@ steps[start, end];
Total[intermediate] - first + last
]


steps is a function which computes the segments.

steps[11.5, 17.4]


{11, 12, 13, 14, 15, 16}

fn[start_, end_, a_] takes care of fractional parts separately. Let's try it:

fn[1.4, 3.7, 1]


57.8109

NIntegrate[t^( t), {t, 1.4, 3.7}]


57.8109

Let's look at what values I have stored. At this point, I've evaluated other integrals as well, at least up to $t = 10$ from $t = 1$.

• nice trick. However, I would still like to know a way to search in DownValues for the last solution and than just add incrementally from that solution until the end of the region of interest. I posted this question more because of curiosity and it is not an actual problem that I'm facing now. So please do not take me wrong. Commented Feb 6, 2017 at 21:41
• This is not, generally, how you want to memoize integrals. Store the integrals from 1 to 2, from 1 to 3, from 1 to 4... . Then you can find the integral from a to b by (integral from 1 to b) - (integral from 1 to a). Turns it from O(n) into O(1) Commented Feb 7, 2017 at 0:01
• @AlexMeiburg I was just creating a toy example to show something that is more idiomatic than what OP is suggesting. I'm not proposing that anyone should use this. Commented Feb 7, 2017 at 0:11
• Right right, just adding this in case someone else does plan to. :) Commented Feb 7, 2017 at 0:12