1.12.3 The Algorithms of Mathematica
The builtin functions of Mathematica implement a very large number of algorithms from computer science and mathematics. Some of these algorithms are fairly old, but the vast majority had to be created or at least modified specifically for Mathematica. Most of the more mathematical algorithms in Mathematica ultimately carry out operations which at least at some time in the past were performed by hand. In almost all cases, however, the algorithms use methods very different from those common in hand calculation.
Symbolic integration provides an example. In hand calculation, symbolic integration is typically done by a large number of tricks involving changes of variables and the like.
But in Mathematica symbolic integration is performed by a fairly small number of very systematic procedures. For indefinite integration, the idea of these procedures is to find the most general form of the integral, then to differentiate this and try to match up undetermined coefficients.
Often this procedure produces at an intermediate stage immensely complicated algebraic expressions, and sometimes very sophisticated kinds of mathematical functions. But the great advantage of the procedure is that it is completely systematic, and its operation requires no special cleverness of the kind that only a human could be expected to provide.
In having Mathematica do integrals, therefore, one can be confident that it will systematically get results, but one cannot expect that the way these results are derived will have much at all to do with the way they would be derived by hand.
The same is true with most of the mathematical algorithms in Mathematica. One striking feature is that even for operations that are simple to describe, the systematic algorithms to perform these operations in Mathematica involve fairly advanced mathematical or computational ideas.
Thus, for example, factoring a polynomial in is first done modulo a prime such as 17 by finding the null space of a matrix obtained by reducing high powers of modulo the prime and the original polynomial. Then factorization over the integers is achieved by "lifting" modulo successive powers of the prime using a collection of intricate theorems in algebra and analysis.
The use of powerful systematic algorithms is important in making the builtin functions in Mathematica able to handle difficult and general cases. But for easy cases that may be fairly common in practice it is often possible to use simpler and more efficient algorithms.
As a result, builtin functions in Mathematica often have large numbers of extra pieces that handle various kinds of special cases. These extra pieces can contribute greatly to the complexity of the internal code, often taking what would otherwise be a fivepage algorithm and making it hundreds of pages long.
Most of the algorithms in Mathematica, including all their special cases, were explicitly constructed by hand. But some algorithms were instead effectively created automatically by computer.
Many of the algorithms used for machineprecision numerical evaluation of mathematical functions are examples. The main parts of such algorithms are formulas which are as short as possible but which yield the best numerical approximations.
Most such formulas used in Mathematica were actually derived by Mathematica itself. Often many months of computation were required, but the result was a short formula that can be used to evaluate functions in an optimal way.
