Computer Algebra: How does the TI-89 do it?

I've always been amazed with the TI-$89$'s ability to deal with symbolic expressions so effortlessly. I've attempted to build several CASs in the past (mostly for fun, they are one of the most difficult and interesting programming challenge I'm aware of) and I've never been able to come close to achieving the level of the TI-$89$'s abilities.

Today, I'm working on a domain specific CAS to solve a particular problem. Given a system of equations describing a dynamic system, containing linear and non-linear algebraic equations, and linear differential and integral equations, find an expression for each unknown function $f(t)$ that describes $f(t + h)$ given $f(t)$. I need implicit integration methods, hence the CAS difficulties :). I'm approaching this with a CAS because I need to be able to run the system simulation really, really fast, and I don't know what the system equations are ahead of time to analyze and optimize them, such as finding closed form solutions for parts of the system, only using numerical solutions when absolutely necessary. Once the timestep expressions are found and simplified, I JIT compile them to native machine code to be executed on my input samples.

To solve this problem I really need some capabilities I've never been able to squeeze out of my previous CAS attempts. I've just been sitting here playing with my TI-$89$ and comparing it to Mathematica. The guys that did the TI-$89$ really did some amazing things.

Consider this almost trivial expression:

(x^2-1)/(x-1)


Of course, this simplifies to

x+1


Now, the TI-89 will do this 'natively', just plug in the first expression and it will come back with the second pretty much instantly. However, every CAS I've ever tried this with (Mathematica being the most reliable and reputable) will not simplify this expression without some convincing. For example, in Mathematica, you need to use Cancel[].

I don't think this is just a matter of Mathematica attempting to be more correct by avoiding changing the domain of the function. Entering:

((x + 1)*(x - 1))/(x - 1)


will happily simplify to the expected result without any extra nudges.

This is only a simple example. This trend continues to many other types of expressions and simplifications, especially trig simplifications.

In my own CAS development experience, I've found it nearly impossible to do what the TI-$89$ does, that is, automatically perform these simplifications without wrapping them in a 'hint' function. I've found that both in terms of computational cost, and in pure software engineering difficulty, this is basically impossible to do. Every CAS I've ever built has involved horrendous debugging of infinite recursion and similar bugs due to attempting to match the TI-$89$'s level of automation.

The fact that Mathematica, Sage, etc. also will not perform these simplifications without a 'hint' makes me feel a little better, but the question remains: How on earth did the TI engineers manage to do this with literally a tiny, tiny fraction of the computing power a desktop has? Are there shortcuts the TI-$89$ is taking that couldn't be scaled to the types of expressions Mathematica et al support or something?

For what its worth, this question is mainly asked out of curiosity that's been burning me ever since I tried to build my first CAS a long time ago.

-
Wild guess: someone among those engineers had decent Lisp exposure. – Kaz Apr 2 '13 at 7:23
Note that all you're asking the TI to do is to divide one polynomial by another. You need the CAS to recognize and handle the case that a polynomial is being divided by one of the same variable, and a lower rank, and then bring in the long division. – Kaz Apr 2 '13 at 7:26
@Kaz Yes, I understand how such an expression might be simplified (and that it isn't that difficult), that isn't the point. I was only using that as an example of where the TI-89 and Mathematica and such differ. As for lisp, yes, lisp is very helpful for solving problems like this, but I don't see how it fundamentally changes the question. Lisp isn't magic: assuming smart algorithms all around, the algorithmic complexity of any given operation in lisp or in another system should be the same. – dsharlet Apr 2 '13 at 7:32
The original version of Macsyma ran in MacLisp in 1 MB (256K 36 bit words on a PDP10). Now you can run a version (Maxima) on Androiod cell phones. Stoutemayer's Derive/muMath (bought by TI) were implemented in a tiny Lisp (muLisp) specially designed to fit well on calculators. – Math Gems Apr 2 '13 at 15:32
@MathGems Thanks for the info! That is new information to me. – dsharlet Apr 3 '13 at 0:02

The fact that the TI-89 simplifies $(x^2-1)/(x-1)$ to $x+1$ while Mathematica, Maple, and Maxima do not reflects nothing more than a design decision on the part of the creators of the software. Likely, this has everything to do with the intended audience and use.

TI products are largely intended to help students studying calculus or pre-calculus level mathematics and typically allows short input. For such users, that specific simplification probably makes some sense.

The designs of Mathematica, Maple, and Maxima are aimed at users with more mathematical experience who might enter much more complicated, programmatic input. In that context, perhaps they want that simplification but maybe not.

More generally, simplification takes time. Why waste time performing computations that the user might not want when the user could certainly specify what they want?

Today, of course, Wolfram Research has a product that gets a lot of student use: WolframAlpha. If you enter $(x^2-1)/(x-1)$ into WolframAlpha, you'll see $x+1$ listed as an alternate form so, clearly, Mathematica could take the expression to that point if the designers thought it was a good idea.

What does the TI-89 do with $(x^{10000}-1)/(x-1)$, incidentally? Mathematica wisely leaves it alone but quickly returns a condensed rendition of the expansion, if you ask for it.

-