random polynomial-time equivalence tester
testeq(a = b)
The function testeq tests for equivalence probabilistically. It returns false if the expressions are not equal (or not equal to 0) and true otherwise for the class of expressions that testeq recognizes. The result false is always correct; the result true may be incorrect with very low probability.
This function will succeed over expressions formed with rational constants, independent variables, and I, combined by arithmetic operations, exponentials, trigonometrics and a few others. It may also succeed with some expressions involving algebraic constants and functions and involving Pi as an argument of trigonometrics. If the expressions do not fall in this class, testeq returns FAIL. testeq may also return FAIL if it cannot find an appropriate modulus that works after seven trials.
a ≔ sin⁡x2−cos⁡x⁢tan⁡x⁢sin⁡x2+cos⁡x⁢tan⁡x2:
b ≔ 1⁢sin⁡2⁢x24−1⁢sin⁡2⁢x⁢cos⁡x2−2⁢cos⁡x2+1⁢sin⁡2⁢x⁢cos⁡x32+3⁢cos⁡x4−cos⁡x6:
Gonnet, Gaston. "Determining Equivalence of Expressions in Random Polynomial Time." Proceedings of the 16th ACM Symposium on the Theory of Computing. Washington DC. April 1984. pp. 334-341.
Download Help Document