How to manipulate mathematical symbols?

Question

This is more of an "educational" question. :)

Although, I probably would like to do something like this eventually.

So, let's say I got an equation. Could be any kind of equation, as long as it's not ridiculous and also a human who was good at math, could solve it.

Let's say... 0 = (x-1)(x+2)

or... y = (x^2), y = 1/x

Or sine functions, etc. Basically, doing math like we did in school.

the question is, how would I write a computer program to solve this? I know it's possible, because programs like Mathematica, Maple, etc, have been doing this for decades! But I can't find any good documentation on how to make even a simple equation solver.

I don't expect answers that tell me "this is exactly how you do it" because of course such a thing is an entire large program, not just a code snippet.

But just a general overview, or links to some good documents? That would be great! Thanks :)

Especially the kind of data structures and algorithms needed.

Failing that, I'll just have to figure out HOW I SOLVE EQUATIONS, and encode that. But that takes literally months to get right (I've done this sort of thing before, formalising my own thinking process into code, it works but it's slow).

Answer 1

In addition to the useful answers by other people: This link seems interesting: http://en.wikipedia.org/wiki/Pattern_matching also, the "abstract tree syntax" seems interesting. Basically, it is about doing "pattern matching" on a syntax tree! Sort of like regex but for code.

I've actually written my own "abstract tree syntax" already :) So I'm already a little way down the path to a symbolic manipulator.

Answer 2

Wolfram Alpha would be the benchmark that is most easily available to you.

Your inputs are strings, so the first step is to write a lexer/parser to break those strings into tokens and put them into an abstract syntax tree (AST).

You don't say what language you want to implement this in, but I'd recommend looking at ANTLR. It's a parser generator that can help you create the AST. You'll have to come up with a grammar for your equations.

Once you have the AST, your solver will walk the tree and associate more specific operations with symbols like "+", "-", etc. The more operators you can handle, the more powerful and all-encompassing your solver will be.

But there are a lot of complexities that you'll have to either deal with or exclude:

1. Not all equations have solutions.
2. Not all equations have closed-form solutions.
3. Not all equations are linear.
4. Lots of interesting problems consist of many coupled equations (think linear algebra).
5. You many need to know a lot about numerical methods for those times when closed form fails you.

I'd recommend that you start with simple arithmetic and polynomials and work your way up. Stephen Wolfram didn't write Mathematica in a day.

Answer 3

Have a look at some papers on symbolic manipulation.

Peter Norvig's PAIP book covers a very simple system for symbolic manipulation and solving of equations, so that'd be worth a read. It introduces the basics of an AI program called MacSyma which eventually formed the basis of Mathematica.

Answer 4

The basic technique is to represent the structure of the mathematical equation in the computer program. This is a very similar idea to what compilers do, but compilers mostly transform their inputs into a machine readable format, but Computer Algebra Systems mostly produce output of the same format as their inputs, but transformed in some interesting way. In either case, the immediate output is an abstract syntax tree. The next step will be to apply some pattern matching techniques (similar to how regular expressions work) as well as some mechanical transformations to rewrite the tree in some useful way.

If you want to see how this might actually be done, SymPy is a python symbolic math library that's both open source and happens to focus on mainly the symbol manipulation aspects of the topic.