Computational Divided Differencing and Divided-Difference Arithmetics

Tools for computational differentiation transform a program that computes a numerical function F(x) into a related program that computes F′(x) (the derivative of F). This paper describes how techniques similar to those used in computational-differentiation tools can be used to implement other program transformations—in particular, avariety of transformations for computational divided differencing. Wediscuss how computational divided-differencing techniques could lead to faster and more robust programs in scientific and graphics applications. We also describe how these ideas relate to the numerical-finite-differencing techniques that motivated Robert Paige’s work on finite differencing of set-valued expressions in SETL programs. Dedicated to the memory of Robert Paige, 1947-1999. 1