next up previous
Next: Modular mappings Up: Heuristic Algorithms Previous: Further improvements

Heuristic equivalence testing and Signature Functions

The problem of equivalence testing is determining whether two expressions (different in appearance) are indeed mathematically the same. This is equivalent to testing whether an expression is identically zero. For example, is


x10-1+(1-x5)(x5+1) = 0 ?

As with other heuristic algorithms, we solve this problem over a simpler domain. The answer to our problem is just true or false, then it is not necessary (or possible) to do any lifting. In other words, there is too little information in this binary result to be able to lift it from the simplified domain to the original domain. The absence of lifting makes this type of heuristic very appealing. As we will see later, every time that we obtain the value false it is correct, and when we obtain the value true, it could be incorrect (and we should FAIL). Instead of failing, and hence failing with all the results that are identical, we will compute the probability of failing for random parameters and produce a probabilistic result. Since this probability can be tuned, we can make it small enough for any practical purposes.

From now on we will concentrate exclusively on testing whether an expression is zero. To test whether a=b, we test a-b=0.



 
next up previous
Next: Modular mappings Up: Heuristic Algorithms Previous: Further improvements
Gaston Gonnet
1999-07-04