#### 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.

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.