Lookup tables, recurrences and complexity
Richard J. Fateman · 1989
The use of lookup tables can reduce the complexity of calculation of functions defined typically by mathematical recurrence relations. Although this technique has been adopted by several algebraic manipulation systems, it has not been examined critically in the literature. While the use of tabulation or “memoization” seems to be a particularly simple and worthwhile technique in some areas, there are some negative consequences. Furthermore, the expansion of this technique to other areas (other than recurrences) has not been subjected to analysis.