Numerical equality testing

Question

I am working on developing an online homework system.

One thing I would like to have is something which compares a student's answer (like $2\sin(x)\cos(x)$) with the intended answer (maybe $\sin(2x)$).

I would like to be able to numerically test equality between two expressions which are compositions of the following functions:

1. Variables a,b,c,d,..
2. Rational functions
3. Trig functions and inverses
4. Expontential function
5. Log

for example, I would need to be able to compare the equality of $\sin(a^2b)\log(x)$ with some other expression with a similar form.

I understand that this is impossible from a purely syntactic point of view: there is a theorem to this effect. So I would like a numerical algorithm which "approximately works". I do not mind if the algorithm occasionally returns a mistaken "true" but it should never return a mistaken "false".

At first, we thought we could just test a couple hundred points in the interval $[-10,10]$ at random, and see if the answers agree at these points to within some specified relative error tolerance (with a default of something like $\epsilon = 10^{-6}$).

This method fails for a function like $\sqrt{x^2-100}$ which does not contain $[-10,10]$ in its domain.

Finding the domain algorithmically (or even any interval in the domain) seems difficult.

We have had more luck (testing against a bank of examples) by evaluating at complex numbers in the unit disk. This too runs into problems for functions with branch cuts (which, for the expressions I am considering, all really stem from $\log$). For example, our system has trouble with $\log(a^2b)$ vs $2\log(a)+\log(b)$.

We are thinking about working with the actual riemann surface, so that we can resolve these domain issues.

I imagine that a lot of people need to test equality between expressions of this form, but I have not found any preexisting open source algorithms which do this reliably.

Does anyone have any pointers to existing open source algorithms, or literature about how to approach this problem?

Answer 1

There is a thread of work that derives from W.-T. Wu's work on geometry theorem proving, and this seminal paper by Schwartz,

Schwartz, Jacob T. "Fast probabilistic algorithms for verification of polynomial identities." Journal of the ACM (JACM) 27.4 (1980): 701-717. (ACM link. PDF download.)

(which now has garnered over 1000 citations). Gonnet extend Schwartz to include trigonometric & exponential functions:

Gonnet, Gaston H. "Determining equivalence of expressions in random polynomial time." Proceedings of the 16th ACM Symposium on Theory of Computing. ACM, 1984. (ACM link. PDF download.)

Maple has implemented these ideas into

• testeq: random polynomial-time equivalence tester

"This function will succeed over expressions formed with rational constants, independent variables, and $i$, combined by arithmetic operations, exponentials, trigonometrics and a few others....The result false is always correct; the result true may be incorrect with very low probability."

For example, Maple's function determines that these two expressions are equivalent:

---

---