Determining the Equivalence of Algebraic Expressions by Hash Coding
William A. Martin · Journal of the ACM · 1971
Let S be the set of rational exponential expressions with complex rational coefficients, single level exponentiation, and no division or element i in the exponents.Let p be a prime integer of the form 4q ~ 1, where q is also prime.The expressions in S can be matched for algebraic equivalence by substituting random integer values for the variables, evaluating the exponents mod (p -1), and evaluating the rational expressions rood p.When this is done equivalent expressions will evaluate to the same result; while, in typical situations, two expressions selected at random will evaluate to the same result with probability about 1/q.Thus, if p is taken close to the word size of a 36-bit machine, the probability of matching equivalent expressions is 1 and the probability of random match is about 10 -9.The problems of extending this scheme to allow division in the exponents and preserve the relation e ~" ----1 are studied.No solutions to these problems were found, but a scheme which handles some cases by special case checks is presented.This scheme was implemented in a program for algebraic simplification.