Memoization and finding already calculated DownValue

Question

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.

Answer 1

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} *)

Answer 2

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