Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Memoization is a technique for improving performance by having a function remember its previous arguments. For example,

f[x_]:=f[x]=mySlowFunction[x]

will be slow on its first evaluation for a given x, but will be vastly faster on subsequent calls for that x, whereas repeated calls to mySlowFunction[x] will always be slow.

My case is that I would like to discretize the parameter space to increase performance at the expense of accuracy. Any Real value of x should be evaluated only at the rounded value, which itself should be memoized. Compare these toy examples:

Clear[f];
f[x_] := f[x] = Total[Table[x, {100000}]]

Clear[g];
g[x_Real] := g[Round[x]];
g[x_Integer] := g[x] = Total[Table[x, {100000}]]

Timing[f[0]][[1]]
  (* 0.002007 *)

Timing[f[0.1]][[1]]
  (* 0.001523 *)

Timing[g[0]][[1]]
  (* 0.002059 *)

Timing[g[0.1]][[1]]
  (* 0.000013 *)

The 2nd call to g[x] is much faster than the first call, even though the actual input (0.1) has not been memoized itself. The second call is less accurate, and I can live with that.

But I would like to Round[] to arbitrary precision. For example, I could try

g[x_Real] := g[Round[x,0.01]];

The g[x_Integer] pattern of the 2nd definition would fail in this case. I tried the naive

h[x_Real] := h[Round[x,0.01]] = Total[Table[x, {100000}]]

which does not produce the desired effect.

How could one memoize a function's inputs, such that subsequent calls to the function at values near the (rounded) memoized inputs are replaced by calls at those memoized inputs?

For the curious, I am tracing particles under the influence of a force. That force can be calculated to high precision at arbitrary locations, but this is slow. I'd like to cache the force at discrete locations, so that particles within some distance of a previously-calculated value use the cached value.

share|improve this question
    
So this is multidimensional, i.e. you have f[x,y,z] and not just f[x], right? For the 1D case I had some easy ideas for good precision (interpolation), but the multidimensional one is more complex. –  Szabolcs Jan 31 '12 at 23:27
    
It's a 2D case, but I'm interested in the 1D as well. Might be able to extend it. –  JxB Jan 31 '12 at 23:29
1  
BTW you can always use a pattern like f[x_ /; Round[x, prec] == x] := f[x] = slowf[x]; f[x_] := f[Round[x, prec]]. The variable prec gives you the precision. –  Szabolcs Jan 31 '12 at 23:30
1  
I'd go for the Interpolation[] approach –  acl Jan 31 '12 at 23:58
1  
Memoization is a type of caching, so I removed the tag in favor of the more general one. –  rcollyer Feb 1 '12 at 2:06
show 2 more comments

3 Answers 3

up vote 13 down vote accepted

Since Dan's already taken my initial solution, here's another approach that additionally allows you to specify the precision:

f[x_, tol_] := f[Round[x, tol]]
f[x_] := f[x] = Total[Table[x, {100000}]]
share|improve this answer
    
Interesting variation of what I just posted (before seeing this). +1 –  Mr.Wizard Feb 1 '12 at 0:05
add comment

This variant should do what you want.

g[x_Real] := h[Round[x,0.01]];
h[x_] := h[x] = Total[Table[x, {100000}]]

Your Interpolation idea might give better accuracy though, if the function inquestion is sufficiently well behaved on your grid.

share|improve this answer
add comment

You can introduce a second symbol as Daniel shows, but I am stingy with symbols and prefer this:

g[x_?NumericQ] := g[{Round[x, 0.01]}];
m : g[{x_}] := m = Total[Table[x, {100000}]]

You could use any head for this, even a string:

g[x_?NumericQ] := g[ "rounded"[ Round[x, 0.01] ] ];
m : g["rounded"[x_]] := m = Total[Table[x, {100000}]]

Delving into the realm of overkill, you could even use Option syntax:

Options[g] = {Rounded -> False};
g[x_?NumericQ] := g[Round[x, 0.01], Rounded -> True];
m : g[x_, OptionsPattern[]] :=
  (m = Total[Table[x, {100000}]]) /; OptionValue[Rounded]
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.