# 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] – Jason B. Feb 6 '17 at 20:56
• Tried already,but I'm having problems making heads and tails of those Hold, HoldPattern etc. – ercegovac Feb 6 '17 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. – ercegovac Feb 7 '17 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. – ercegovac Feb 6 '17 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) – Alex Meiburg Feb 7 '17 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. – C. E. Feb 7 '17 at 0:11
• Right right, just adding this in case someone else does plan to. :) – Alex Meiburg Feb 7 '17 at 0:12