** Finite Differencing**

* Finite differencing*[Paige, R.
and Koenig, S., ``Finite
Differencing of Computable Expressions'', * ACM Transactions on Programming
Languages and Systems*, vol. 4, no. 3 (July 1982), pp. 402-454]
is a general technique for optimizing expensive computations *f(i)* that
occur in a loop:

- Maintain local variables that hold previous values of the
expensive computation
*f(i)*and perhaps some auxiliary values. - Incrementally compute a new value
*f(i + δ)*using:- the previous value
*f(i)* - a
*difference*from*f(i)*.

- the previous value

Example: * f(i) = i ^{2} *

i | 0 | 1 | 2 | 3 | 4 | 5 | |||||

i ^{2} | 0 | 1 | 4 | 9 | 16 | 25 | |||||

first difference: | 1 | 3 | 5 | 7 | 9 | ||||||

second difference: | 2 | 2 | 2 | 2 | |||||||