How does a system like Wolfram Alpha or Mathematica solve equations?

25
votes

I'm building a web-based programming language partially inspired by Prolog and Haskell (don't laugh).

It already has quite a bit of functionality, you can check out the prototype at http://www.lastcalc.com/. You can see the source here and read about the architecture here. Remember it's a prototype.

Currently LastCalc cannot simplify expressions or solve equations. Rather than hard-coding this in Java, I would like to enhance the fundamental language such that it can be extended to do these things using nothing but the language itself (as with Prolog). Unlike Prolog, LastCalc has a more powerful search algorithm, Prolog is "depth-first search with backtracking", LastCalc currently uses a heuristic best-first search.

Before delving into this I want to understand more about how other systems solve this problem, particularly Mathematica / Wolfram Alpha.

I assume the idea, at least in the general case, is that you give the system a bunch of rules for manipulation of equations (like a*(b+c) = a*b + a+c) specify the goal (eg. isolate variable x) and then let it loose.

So, my questions are:

  • Is my assumption correct?
  • What is the search strategy for applying rules? eg. depth first, breadth first, depth first with iterative deepening, some kind of best first?
  • If it is "best first", what heuristics are used to determine whether it is likely that a particular rule application has got us closer to our goal?

I'd also appreciate any other advice (except for "give up" - I regularly ignore that piece of advice and doing so has served me well ;).

2
algorithmwolfram-mathematicaartificial-intelligencealgebra
Please people, do not broad this as too close... er, the other way around. This is interesting and answerable - and anyway, go find some of those "gimme teh codez" or "why does "foo"[0] = 'b'; segfault?" questions, your CV would serve a much better purpose there. - user529758
Are you asking about solving equations, or parsing expressions? "solve 150sin(x)-gamma(x)=0" is one thing, "parse (((((x+1)-1)+1)-sin(x)-1))" is another thing, however the first may involve the second. - nanofarad
Good question. LastCalc is fairly weird in that everything it does, whether parsing, doing unit conversions, or (soon) simplifying expressions and solving equations, is just a series of transformations - the starting point being a list of tokens. However, parsing isn't a challenge, so please focus on solving, not parsing. - sanity
To the person who voted to close due to "too broad". I can see how it might appear to be very broad superficially, but actually I think this question is answerable, and actually I expect the answer to be fairly concise. Wolfram Alpha might be very sophisticated, but I suspect the core principles on which its equation manipulation works are relatively simple and explainable. - sanity
Reading you Question, I found this document math.wpi.edu/IQP/BVCalcHist/calctoc.html searching about it. Maybe it will help. There is an implementation of a CAS and it talks about simplification of equations. - Jean Waghetti

2 Answers

10
votes

I dealt with such questions myself some time ago. I then found this document about simplification of expressions. It is titled Rule-based Simplification of Expressions and shows some details about simplification in Mupad, which later became a part of Matlab.

According to this document, your assumption is correct. There is a set of rules for manipulation of expressions. A heuristic quality metric is is used as a target function for simplification.

2
votes

Wolfram alpha is developed by Mathematica

  • mathematica is stephen wolphram's brainchild. Mathematica 1.0 was released in 1988. mathematica is much like maple and they both rely heavily on older software libraries like LaPack.
  • The libraries that these programs are, based on, and often simply, legacy software. They've been around, and modified, for a very long time.

If you would like to know about the background programs running, sagemath is a free open source alternative; you could possible reverse engineer the solutions to your questions:

SageMath.org