Lookup tables, recurrences and complexity

ABSTRACT

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. This paper examines some of the assumptions. A more detailed technical report [9] is under preparation.

REFERENCES

• 2: Michael Beeler , R. W Gosper , Rich Schroeppel, HAKMEM, Massachusetts Institute of Technology, Cambridge, MA, 1972
• 3: Bruce Char et al. On the Design and Performance of the Maple System. Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada, CS-84-13, 1989.
• 4: Richard Fateman. Macsyma's General Simplifier: Philosophy and Operation. In Lewis, V.E. (ed), Proceedings of the 1979 Macsyma Users Conference. Washington D.C., 1979. 563-582.
• 5: J. M. Greif, The SMP Pattern Matcher, Research Contributions from the European Conference on Computer Algebra-Volume 2, p.303-314, April 01-03, 1985
• 6: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 7: J. C. P. Miller and Brown, D. J. S. An algorithm for evaluation of remote terms in a linear recurrence sequence, Comp. J. 9 (1966), 188-190.
• 8: Michael B. Monagan, private communication.
• 9: Carl Glen Ponder, Evaluation of "performance enhancements" in algebraic manipulation systems, 1988
• 10: Stephen Wolfram, Mathematica: a system for doing mathematics by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

General Terms:
Algorithms, Theory