What are the main considerations when designing a math system or library that can do symbolic computation on mobile devices?
I’ve written several times about math apps on mobile devices but, inspired by a blog post by Ismael Ghalimi, I want to comment a bit about how one might do symbolic computation on a small, probably mobile device.
What do I mean by symbolic computation? Some examples will probably make it clear. Unlike in a spreadsheet where you are concerned primarily with manipulating floating point numbers and text (e.g., 3.4 + 2.1 = 5.5), in symbolic computation you can also compute with expressions involving variables.
So in such a system you could compute that (x + 1)2 = x2 + 2x + 1 and the derivative of the result is 2x + 2. You can easily manipulate arbitrarily large integers and fractions of such numbers. There’s probably some capability for manipulating expressions involving trigonometric and other functions. You can both express sin2(z) + cos2(z) and the system will simplify it to 1. So you can manipulate and compute with basic expressions but also use structures like lists and mathematical vectors and matrices. With these you can then do linear algebra along with single and multivariable calculus.
I’ve oversimplified here and not mentioned all capabilities of such systems, but you should have an idea of how symbolic computation differs from what you can do in a spreadsheet. The two most successful commercial systems are Mathematica and Maple. Wolfram Research also provides Wolfram Alpha which allows you to use many of the computational capabilities of Mathematica via the web and on mobile devices.
Though Maple and Mathematica share similar functionality and have very sophisticated computational and graphical features, they are implemented very differently under the covers. I was involved with creating the Axiom system at IBM Research in the 1980s and 1990s, and it was built radically differently from the other two. In particular, it was ultimately built on Lisp which provided both bignum (large integers) and garbage college for the storage used. Yet another approach is that employed by the open source Sage application which collects together various implementations under one tent.
Since you have different ways of building such systems and representing the computational objects in them, what are the considerations for using symbolic capabilities on a mobile device?
- Space: (x + 1)2 expands to just three terms, but the expression (x + 1)200000 expands to 200,001 terms, which will take up quite a bit of space, probably well more than 1Mb. So small things can get big quickly once you start computing with them.
- Time: Expanding the above polynomial can be done in a few seconds, but factoring it could take many minutes or hours, depending on your heuristics and algorithms. What will your mobile user be doing while he or she waits for an answer? Similarly, taking the derivative of an expression is relatively straightforward, though simplification can be time consuming. Integration can take considerably more time, if you can do it at all.
- Formatting: These days users expect beautiful output. So while sin(x2 + 2x + 1) looks fine, older style output like sin(x^2 + 2*x + 1) is just ugly. If you are just computing with a symbolic expression as part of a larger action, you may never need to show fancily formatted math expressions. By the way, once you get very large expressions that need to span multiple lines or large two-dimensional ones, formatting becomes much harder. See TeX and LaTeX to learn about how to handle the complexity in its most general form. In practice, you’ll do something simpler.
- Client vs. Server: How much work is done on the device versus on a big server somewhere? You can compute faster on the server, but what’s the delay in communicating back and forth with it and sending data? What do you do if you have no or limited bandwidth? Personally, I think a hybrid scheme where some things are done locally and others can be offloaded to a server probably makes the most sense, but it does complicate processing.
- Library: Do you want this code to be wrapped up in a library that can be linked to multiple apps? If so, you need to design your interfaces very carefully. If the library will be used by different parts of the same app, make sure it is thread safe, so you don’t mess up one computation that’s going on when you request another.
- Portability: If you could use languages like Python, Lisp, or Scheme, you would get bignums and memory management for free. If you use C++, you’ll have to do those things yourself, perhaps by using open source libraries to help you. On iOS devices, it’s perfectly fine to use Objective-C for the interface components and C++ for your computational back-end. You could also use that C++ code on an Android or Windows 8 Mobile device. I suppose you could use a subset of a Lisp interpreter written in C++ and then build your math code on top of that.
- Legal: Apple has very specific rules about when you can download a script and run it on your iOS device. If you plan to download a file that contains a list of computations to be executed, make sure you are not running afoul of Apple’s terms and conditions.
- Extensibility: The big systems are all designed so users can add more capabilities to them. Depending on the system, the new things might run just as fast as what is built in, or somewhat slower if the expressions are interpreted. For mobile, I think this is mostly a core developer question: How do I construct the libraries at the center of the system so that I can easily add new mathematical objects with which to compute? The basic objects are probably integers, rational numbers, floating point numbers, polynomials, rational functions, general expressions that can include trig functions and integrals, lists, vectors, and matrices. How might you later add partial differential equations? I think you need a design that allows you to build new objects, register them in the system, and then compute with them as if they were there all along. This is more computer science than math, but you’ll quickly see the value in being able to extend the system.