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
If we change the test of i to a test of E, then code involving i becomes dead code that can be eliminated:
     E := 0
L7:
     if ( E <= 792 )
        x[E]
        ...
        E := E + 8
        goto L7
Now the code is simpler, and the expensive operation has been obtained at no runtime cost.