Symbolic computation in the small: Math on mobile

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.
This entry was posted in Mathematics and tagged , , , , , , , , , , , , , , . Bookmark the permalink.

5 Responses to Symbolic computation in the small: Math on mobile

  1. Great summary of the problem at hand! Thanks.

  2. Scott Morrison says:

    Interesting topic, Bob.

    If I were to create a mobile symbolic computation system I would definitely start with an existing system running on a server. Open source Axiom would be an excellent choice. Porting Axiom to a mobile platform, while possible, would be a ton of work. But running it on a Linux server would be trivial. I’d then slap a REST API around it to make it accessible from any mobile or web application.

    I wouldn’t want to write a new system from scratch. Creating symbolic computation systems from scratch is hard :-)

    Limited bandwidth might be a problem with large data, but I wouldn’t worry about it too much. Mobile data connections are getting faster all the time, and really the data isn’t all that big compared to, say, streaming a video. Also the REST API could batch data in pages since you couldn’t see all of a large expression at once.

    For output, using LaTeX is a great option. There would be some nice opportunities for a multi-touch interface for showing large expressions. I’m sure there are great areas for innovation here.

    The most interesting area of research for me would be to leverage multi-touch input for writing math expressions. It would be great to just write out expressions in a natural math notation with your finger. It’s a hard problem, but not impossible.

    Mobile devices have quite capable GPUs these days, so adding some nice 3d visualization capabilities would be fun too.

    Are you thinking about starting a new project?

  3. Bob Sutor says:

    Hey Scott, no new project, though I did do some basic exploratory work several years ago looking at C++ implementations. Ismael pinged me on the topic, so I wrote down some thoughts.

    That said, the big systems are getting rather old now, though they’ve been significantly and iteratively improved. I do wonder about where the next big software in the area is going to come from. I also think about how we might have done Axiom differently if we had Python, or at least used Java or its virtual machine.

  4. Stephen Watt says:

    [Reposting. Previous submission converted three conference links to "nofollow".]

    Hi Bob, This is a nice discussion piece.

    A closely related topic is that of doing computer algebra on constrained devices, a topic on which Elena Smirnova and I have run a few conferences under the banner “Compact Computer Algebra”. See CCA 2008, CCA 2009, CCA 2010, CCA 2012.

    Elena did an extended period as a postdoc with us at ORCCA, before heading to Texas Instruments, so the question of computer algebra on handheld devices has been a natural one. This is not exactly the same as doing symbolic computation on your phone, but there is a lot of common ground. Other areas where you might want to do “compact computer algebra” might be smart line-breaking in a word processor, editing gestures in handwriting entry, etc.

    For the telephone, have you tried Maxima ported by Yasuaki Honda? It is now in Google Play Maxima on Google Play.

    It is great that this port exists, but there is obvioiusly a lot that one would do differently if doing math ab initio on a small touch screen device. I wouldn’t worry too much about a client-service architecture for computational power — we won’t be doing giant problems on phones.

    The main reason I would imagine for a service oriented architecture is instead to enhance collaboration, and this I find compelling.

    Stephen

  5. John Dougan says:

    It doesn’t have everything you’d want, but you might want to look at MathStudio (at http://www.mathstudio.net/ , formerly called SpaceTime) for some ideas. It is cross-platform (mac, ios, windows and android. I have no relation to the developers other than being a happy customer.

Comments are closed.