1.4.9 The Limits of Mathematica
In just one Mathematica command, you can easily specify a calculation that is far too complicated for any computer to do. For example, you could ask for Expand[(1+x)^(10^100)]. The result of this calculation would have terms—more than the total number of particles in the universe.
You should have no trouble working out Expand[(1+x)^100] on any computer that can run Mathematica. But as you increase the exponent of (1+x), the results you get will eventually become too big for your computer's memory to hold. Exactly at what point this happens depends not only on the total amount of memory your computer has, but often also on such details as what other jobs happen to be running on your computer when you try to do your calculation.
If your computer does run out of memory in the middle of a calculation, most versions of Mathematica have no choice but to stop immediately. As a result, it is important to plan your calculations so that they never need more memory than your computer has.
Even if the result of an algebraic calculation is quite simple, the intermediate expressions that you generate in the course of the calculation can be very complicated. This means that even if the final result is small, the intermediate parts of a calculation can be too big for your computer to handle. If this happens, you can usually break your calculation into pieces, and succeed in doing each piece on its own. You should know that the internal scheme which Mathematica uses for memory management is such that once part of a calculation is finished, the memory used to store intermediate expressions that arose is immediately made available for new expressions.
Memory space is the most common limiting factor in Mathematica calculations. Time can also, however, be a limiting factor. You will usually be prepared to wait a second, or even a minute, for the result of a calculation. But you will less often be prepared to wait an hour or a day, and you will almost never be able to wait a year.
The internal code of Mathematica uses highly efficient and optimized algorithms. But there are some tasks for which the best known algorithms always eventually take a large amount of time. A typical issue is that the time required by the algorithm may increase almost exponentially with the size of the input. A classic case is integer factorization—where the best known algorithms require times that grow almost exponentially with the number of digits. In practice, you will find that FactorInteger[k] will give a result almost immediately when k has fewer than about 40 digits. But if k has 60 digits, FactorInteger[k] can start taking an unmanageably long time.
In some cases, there is progressive improvement in the algorithms that are known, so that successive versions of Mathematica can perform particular computations progressively faster. But ideas from the theory of computation strongly suggest that many computations will always in effect require an irreducible amount of computational work—so that no fast algorithm for them will ever be found.
Whether or not the only algorithms involve exponentially increasing amounts of time, there will always come a point where a computation is too large or timeconsuming to do on your particular computer system. As you work with Mathematica, you should develop some feeling for the limits on the kinds of calculations you can do in your particular application area.
Some operations that typically take a few seconds on a 2003 vintage PC.
