How to efficiently implement periodic function to reuse computed values

Question

Assume I have a function

f = Function[t, VeryDifficultComputation]

But I would like to exploit the fact that the function is periodic to "cache" computations done for the corresponding value of another period. So for example, if I know that the interval {0, 1} is repeated on each interval {n, n+1}, I would basically like the function to give my an answer immediately for any value once I manage to plot it on the interval {0, 1}. I want to use it in sound generation, so I really need to have values for lots of periods.

What would be a good approach to implement this in Mathematica?

Answer 1

There are two ways to do this. Memoization is simple and exact. Interpolation may be better if the function is smooth.

Consider the following:

Clear[memoizedSin]
memoizedSin[x_] := memoizedSin[x] = (Pause[0.01]; Sin[x])
Plot[memoizedSin[x], {x, 0, 2 Pi}] // AbsoluteTiming

This takes 4.85 seconds on my computer. Now evaluate the last line again:

Plot[memoizedSin[x], {x, 0, 2 Pi}] // AbsoluteTiming

This time it only took 0.03 seconds because of the memoization. However, now try this:

Plot[memoizedSin[x], {x, 0, Pi}] // AbsoluteTiming

It takes 2.93 seconds even though we are plotting from the same interval. The reason is that we now sample the function differently. This example highlights a problem with memoization, which is that it requires the input to be exactly the same in order to avoid unnecessary computations. Interpolation, on the other hand, can save time when the exactness of memoization is not needed, e.g. when the errors induced by interpolation are acceptable.

interp = Interpolation@Table[Pause[0.01]; {x, Sin[x]}, {x, 0, 2 Pi, 0.1}];
interpolatedSin[x_] := interp[Mod[x, 2 Pi]]
Plot[interpolatedSin[x], {x, 0, 4 Pi}] // AbsoluteTiming

The plotting itself took only 0.04 seconds because the cost of Pause had been subsumed in the creation of the interpolation function. Note also that in this last example I have shown how to create a periodic function. Even though I originally defined the interpolation on the interval $(0, 2\pi)$ I am now able to plot the function on an arbitrary interval.

As mmeent points out in a comment below, Interpolation has an option that makes the interpolation periodic, so that we can forgo Mod:

interpolatedSin = Interpolation[
   Table[Pause[0.01]; {x, Sin[x]}, {x, 0, 2 Pi, 0.1}] // Append[{2 Pi, Sin[2 Pi]}],
   PeriodicInterpolation -> True
   ];
Plot[interpolatedSin[x], {x, 0, 4 Pi}] // AbsoluteTiming

Note that I had to use Append in this example to make sure that the sequence ends with the same y value that it begins with, as is required by Interpolation when PeriodicInteroplation -> True is used.