Hashing LEMMAs on time complexities with applications to formula manipulation

ABSTRACT

In this paper, time complexities of operation on “sets” and “ordered n-tuples” based on a hashing table search technique are presented as “Hashing LEMMAs” and are applied to formula manipulation. Unique normal forms for multivariate symbolic formulas resulting in O(1) time complexity for identity checks are presented. The logarithmic factor log2N, characteristic to sorting algorithms, is shown to all disappear from time complexities of polynomial manipulations. Actual implementation of the hashing technique is outlined and actual timing data are presented in the appendix.

REFERENCES

• 1: Stephen C. Johnson, Sparse polynomial arithmetic, ACM SIGSAM Bulletin, v.8 n.3, p.63-71, August 1974 [doi>10.1145/1086837.1086847]
• 2: Ellis Horowitz, A Sorting Algorithm for Polynomial Multiplication, Journal of the ACM (JACM), v.22 n.4, p.450-462, Oct. 1975 [doi>10.1145/321906.321908]
• 3: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 4: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 5: M. Sassa and E. Goto, A Hashing Method for Fast Set Operations, submitted for publication.
• 6: T. Gunji, Tech. Rep. 76-03, ISD (Information Science Department, the University of Tokyo), 1976.
• 7: J. McCarthy, Page 151 of Symbol Manipulation Languages and Technique, D. Bobrow, ed., North-Holland, 1971.
• 8: Y. Kanada, Tech. Rep. 75-01, ISD, 1975.
• 9: F. Motoyoshi, Tech. Rep. 76-05, ISD, 1976.
• 10: M. Terashima, Tech. Rep. 75-03, ISD, 1975.
• 11: A.C. Hearn, REDUCE2 User's Manual, 2nd. ed., Salt Lake City, Utah., 1973.

INDEX TERMS

Primary Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.3 Languages and Systems

General Terms:
Algorithms, Measurement, Theory