How to calculate indefinite integral programmatically

I remember solving a lot of indefinite integration problems. There are certain standard methods of solving them, but nevertheless there are problems which take a combination of approaches to arrive at a solution. But how can we achieve the solution programatically.

For instance look at the online integrator app of Ma开发者_运维技巧thematica. So how do we approach to write such a program which accepts a function as an argument and returns the indefinite integral of the function.

PS. The input function can be assumed to be continuous(i.e. is not for instance sin(x)/x).

---

You have Risch's algorithm which is subtly undecidable (since you must decide whether two expressions are equal, akin to the ubiquitous halting problem), and really long to implement.

If you're into complicated stuff, solving an ordinary differential equation is actually not harder (and computing an indefinite integral is equivalent to solving y' = f(x)). There exists a Galois differential theory which mimics Galois theory for polynomial equations (but with Lie groups of symmetries of solutions instead of finite groups of permutations of roots). Risch's algorithm is based on it.

---

The algorithm you are looking for is Risch' Algorithm:

http://en.wikipedia.org/wiki/Risch_algorithm

I believe it is a bit tricky to use. This book:

http://www.amazon.com/Algorithms-Computer-Algebra-Keith-Geddes/dp/0792392590

has description of it. A 100 page description.

---

You keep a set of basic forms you know the integrals of (polynomials, elementary trigonometric functions, etc.) and you use them on the form of the input. This is doable if you don't need much generality: it's very easy to write a program that integrates polynomials, for example.

If you want to do it in the most general case possible, you'll have to do much of the work that computer algebra systems do. It is a lifetime's work for some people, e.g. if you look at Risch's "algorithm" posted in other answers, or symbolic integration, you can see that there are entire multi-volume books ("Manuel Bronstein, Symbolic Integration Volume I: Springer") that have been written on the topic, and very few existing computer algebra systems implement it in maximum generality.

If you really want to code it yourself, you can look at the source code of Sage or the several projects listed among its components. Of course, it's easier to use one of these programs, or, if you're writing something bigger, use one of these as libraries.

---

These expert systems usually have a huge collection of techniques and simply try one after another.

I'm not sure about WolframMath, but in Maple there's a command that enables displaying all intermediate steps. If you do so, you get as output all the tried techniques.

Edit:

Transforming the input should not be the really tricky part - you need to write a parser and a lexer, that transforms the textual input into an internal representation.

---

Good luck. Mathematica is very complex piece of software, and symbolic manipulation is something that it does the best. If you are interested in the topic take a look at these books:

http://www.amazon.com/Computer-Algebra-Symbolic-Computation-Elementary/dp/1568811586/ref=sr_1_3?ie=UTF8&s=books&qid=1279039619&sr=8-3-spell

Also, going to the source wouldn't hurt either. These book actually explains the inner workings of mathematica

http://www.amazon.com/Mathematica-Book-Fourth-Stephen-Wolfram/dp/0521643147/ref=sr_1_7?ie=UTF8&s=books&qid=1279039687&sr=1-7