Robert Paige and Shaye Koenig, "Finite Differencing of Computable Expressions", ACM Trans. on Programming Languages and Systems, vol. 4, no. 3 (July 1982), pp. 402-454.

Finite differencing replaces repeated computation of an expensive function f(i) with computation of incremental changes in f(i) from its previous value.

Finite differencing has several advantages:

1. it can be applied over a large spectrum of language levels
2. it can transform from a high-level but inefficient program into a lower-level, efficient implementation
3. it can be implemented systematically
4. it yields asymptotic speedup.

Components of the transformation:

1. Init: Introduce variable E = f(x1, ..., xn) and initialize the variable above the loop.
2. Differential:
   1. Whenever a variable xi used in f is modified within the loop, introduce statements to modify E so that it will remain available.
   2. Replace occurrences of f(x1, ..., xn) by E.
3. Clean: Remove dead code. This is where the payoff occurs: hopefully the dead code that is removed is more expensive than the incremental code that was introduced.

Example: Optimization of subscript expressions: Consider the following program fragment with an array reference inside a loop:

var x: array[1..100] of real;

for i := 1 to 100 do
   x[i] ...

The compiler will produce intermediate code such as the following.

     i := 1
L7:
     if ( i <= 100 )
        x[i*8 - 8]
        ...
        i := i + 1
        goto L7

We will assume that the subscript expression f(i) = i*8 - 8 is an expensive expression that we would like to replace. Introduce a new variable E = i*8 - 8 and add code to update E whenever i is updated so that this relationship always holds:

     i := 1
     E := 0
L7:
     if ( i <= 100 )
        x[E]
        ...
        i := i + 1
        E := E + 8
        goto L7

     E := 0
L7:
     if ( E <= 792 )
        x[E]
        ...
        E := E + 8
        goto L7