How does a computation engine or calculator give exact answers?

Question

I've always wondered how sites like Wolfram Alpha or tools like TI-89 calculators can give exact answers to complex problems. I.e. irrational numbers or exact solutions to calculus problems.

For example, take a simple problem of: $2\pi/4$. Wolfram Alpha gives an exact answer of $\pi/2$.

Having studied numerical analysis before, I know scientific tools like Matlab or Octave use approximations which is not what I'm looking for.

I'm interested in knowing what kind of techniques TI calculators or Wolfram Alpha use to give an exact answer. Granted my example was simple but you could ask Wolfram to solve a PDE and it will sometimes give an exact answer.

Answer 1

First off, I guess you need a specialized data structure to represent symbolic objects. Here's an example lifted straight from SymPy's documentation:

from sympy import *
x, y, z = symbols('x y z')
expr = x**2 + x*y
srepr(expr)

# Out: 
# "Add(Pow(Symbol('x'), Integer(2)), Mul(Symbol('x'), Symbol('y')))"

So, I guess that Add, Pow, Symbol, Integer, and Mul are classes defined by SymPy with methods indicating how to perform basic algebraic operations. All those classes have a diff method, for example, that indicates how they should be differentiated with respect to a symbol. The diff method for Pow encodes the power rule; the diff method for Mul encodes the product rule.

The whole expression can be visualized with a tree - again, from the SymPy documentation:

To differentiate the expression with respect to a symbol, we traverse the tree applying the appropriate diff method as we go along to build up a new expression tree for the derivative.

Note that Mathematica does something very similar:

expr = x^2 + x^y;
FullForm[expr]
TreeForm[expr]

(* Out: 
   Plus[Power[x,2],Power[x,y]]
*)