2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ you can grab the previously existing values via something like Cases[ DownValues@fn, fn[x_?NumericQ,_] :> x, Infinity] $\endgroup$ – Jason B. Feb 6 '17 at 20:56
  • $\begingroup$ Tried already,but I'm having problems making heads and tails of those Hold, HoldPattern etc. $\endgroup$ – ercegovac Feb 6 '17 at 21:22
3
$\begingroup$

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} *)
$\endgroup$
  • $\begingroup$ This is exactly what I was hoping to get. $\endgroup$ – ercegovac Feb 7 '17 at 10:36
1
$\begingroup$

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$.

enter image description here

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ercegovac Feb 6 '17 at 21:41
  • $\begingroup$ 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) $\endgroup$ – Alex Meiburg Feb 7 '17 at 0:01
  • $\begingroup$ @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. $\endgroup$ – C. E. Feb 7 '17 at 0:11
  • 1
    $\begingroup$ Right right, just adding this in case someone else does plan to. :) $\endgroup$ – Alex Meiburg Feb 7 '17 at 0:12

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.