Notes on the Limitations of Computer Algebra Systems (revised 5/7/04)

by George Gesslein II

Introduction

Having written a general purpose CAS (Computer Algebra System), I feel qualified to write about them.

The first powerful CAS ever written is called Macsyma. Macsyma is a LISP program, started in the late 1960s, that is still being used to this day (see Maxima). LISP is well suited to do symbolic mathematical processing, while the C programming language is good at numeric math and logic. LISP is archaic and a better language is needed.

The C programming language became very popular in the 1980s, and Mathematica, Maple, and Mathomatic were born. Because it is difficult to do symbolic math in C, but easy to write other languages in C, Mathematica and Maple have their own programming language. Mathomatic was a struggle to code, because it is written entirely in C and has no programming capability. This is the reason for its main limitation: No logarithms or trigonometry. Logarithms will be added when I am feeling better.

Rule-Based Manipulations and Heuristics

All CASes use rule-based transformations and manipulations. Heuristics (the trial and error, or brute force approach) are used, too. A totally heuristic CAS would eventually succeed at simplifying any mathematical expression to its smallest possible size. It would do this by applying every combination of algebraic rules to every part of the expression in an intelligent way to produce the maximum simplification. A totally heuristic CAS is not practical as a general purpose algebra system, but would be nice to have, if you needed perfect simplification.

Mathomatic uses a little heuristics in its solve routine, and in its "smart divide" routine. Other than that, it intelligently applies the rules of algebra to arrive at the best answer without heuristics. This means the simplified result may not be the smallest possible, but it will be easy to read and probably the answer wanted.

Writing Your Own CAS

Even if you are thick-headed like me, writing your own CAS will give you first-hand experience with the beauty of mathematics and make you smarter. For every algebraic rule you implement, you will need its inverse, too.

Most CASes use dynamically allocated tree structures for mathematical expressions. Mathomatic uses a fixed size array with alternating elements of operand/operator. Each level of parentheses is indicated by a level number in each element (origin 1). This method of storage is OK for basic math, but won't work for more advanced math, where functions can have more than two parameters, and matrices are required.

You will need to decide on how to represent constants. The standard floating point arithmetic is OK, but it has problems representing fractions and the round-off error accumulates. Fractions (rational arithmetic) are very important in a CAS. The commercial CASes use their own numeric math library, which allows very large and long numbers and fractions.

Mathomatic has proved it is possible and efficient to do generalized polynomial operations. By generalized, we mean that the coefficients of any polynomial are not specially treated or stored in any way other than ordering. They are not separated out from the main variable of the polynomial. Maximum simplification of all expressions is not possible unless everything is generalized.

Good luck and have fun!


Copyright © 2004 George Gesslein II


Up to the Mathomatic Home Page