Symbolic math and advanced algebra

Numerical Recipes books online for C, Fortran 77, Fortran 90 have a look here the online books at the bottom of the page.

EDIT: They also have sample source code aswell

Thanks for the info but Numerical Recipes (which is a good book) handles mostly numerical algorithms, which are useless for my case.
Thanks anyway.

There's a big difference between symbolic algebra and symbolic calculus. Differentiation and some very simple differential equations aren't too terribly complex, but it will take some work to implement them. When it comes to integration, though, you're in for a world of hurt. For example, the symbolic integration engine at integrals.com has "about 500 pages of Mathematica code and 600 pages of C code." Of course if you want the output to look nice you need typesetting; Mathematica's is 2000 pages of code. Of course one person probably isn't out to rival Mathematica, but that should give you some awareness of the huge scope of what you're attempting. Robust symbol manipulators are hard enough to write; calculus, particularly integral calculus, is 94% pure insanity.

I don't want to be discouraging here; in fact if you are really up for writing such an app, more power to you. Just be aware of what you're getting in to and that you may need some extra muscle before the end.

Maybe you should tell us what your goal is. Is it only an exercise, or is it to be used in conjunction with another more important app? If the latter, there are probably libraries available...

If you're doing it as an exercise, I strongly advise you to pick a high-level language. And look up Greenspun's tenth rule;)

Finally, if I were to do a symbolic integrator for fun, I would probably try something wholly original, rather than picking an algorithm that already has thousands of programmers working on it. How about trying to do the integral numerically, and then fit a combination of functions based on its behavior at 0 and infinity? Or integrating the Taylor series, and trying to match them based on a catalogue of already computed series?

Granted, these will probably lead you nowhere, but I'm sure that you have crazy ideas of your own;)

Good luck!

Cédric

Expression Templates
Object Oriented Numerics
Function objects and higher-order programming
Boost.Lambda

Well, Wolfram was nice enough to put up a site with how mathematica does integrals, found here. Good luck with them, you will definitely need it because to do things with generality is crazy.

And a little note, you might want to make your software support not just pi and e, but also the euler gamma and Catalan's constant because they are often found in definite integrals and can allow you to give analytic results.

Take a look at Haskell too.

ApochPiQ: Yeah I know what I'm getting into (that's why I have prepared my anti-integral armor ;) ). Yeah I realized after posting that I was talking about calculus not algebra. I'm not trying to make a competitive application to one of the giants in the field, actually it's an academic project, a framework with all of the nitty gritty implemented so that it can be upgraded latter (through constant "evolution"). Other thing is that I'm not working alone, there's a small team on the job. Like I said I have the base layout, but I want to get more input so I can see what other people can share with me in the field.
Cedric: If I were working alone then I would probably make use of some functional language, but since that is not the case I'm stuck with C/C++ and other standard combinations.

For the first phase the integrator must be able to handle a smaller set of common integrals for example: pure trygonometric, polynomial factorised, natural functions (don't know if I'm using the right term here), in other words solve integrals from all of types of base functions. Now that you know what I want to do at the current moment I hope you'll give me some more advice ;). So to restate, I don't want a huge generalised integrator, just to robustly handle a small subset of common integrals (not table integrals).

Assuming you've converted the equation into some kind of token stream, it should be fairly easy to use pattern recognition to locate your basic elementary integrals. When you get to integration by parts and more complicated substitutions you'll have some major challenges, but for the basics a pattern system should work nicely. For example you can look for the pattern "constant * (variable ^ power) + [...]" and apply the rules for polynomial integration, and so on. In fact a basic regular expression system like the one outlined in this series should do a great job with this.

ApochPiQ:
Now thanks for reminding of regular expressions, and here I was trying to remember of the best pattern matching algo for the job. People tend to forget the most obvious and easiest solutions.

Like you said though pattern matching will help with the most basic (the ones that don't need a lot of transformations), but it will miss a good deal of simple ones. For instance take this example:

int( (3cos x + 2sin x)/(3sin x+2cos x) ). When you try to solve it by hand you will divide the expression by cos x from where it's a simple case to solve, while pattern matching would choke here. Obviously additional mathematical methods are needed to handlea handfull more cases beyond the simplest lookup integrals. All you math gurus, researchers, etc. here's a chance to help a fellow ;).

Well, for your example, first consider that you can split it into two simpler integrals, where the integrands are (3 cos x)/(2 cos x + 3 sin x) and (2 sin x)/(2 cos x + 3 sin x). You should be able to recognize this pattern easily; it is the general pattern (a + b + [...])/c which decomposes into a/c + b/c + [...]. Now look at the first integrand (3 cos x)/(2 cos x + 3 sin x). The basic pattern here is Aa/(Ba + Cb) where capital letters are constant coefficients and lower case letters are non-constant expressions. Your pattern recognition system can find this pattern as well, and reduce it further to (A/(B + C(b/a)) by dividing both the top and bottom of the expression by a.

In this case, b/a = c. Specifically, sin x / cos x = tan x. Your algebraic simplification logic should recognize that the ability to reduce the fraction to tan x makes it simpler than the original fraction. One way to accomplish this is to assign each expression a score. The higher the score, the more complexity. The simplification logic will only make a simplification if the complexity score of the resulting expression is lower than the orginal expression. That should help for trigonometric functions, but in cases like (3 log x)/(4 log x + pi sin x) you won't end up with ugly results like 3 / (4 + pi (sin x / log x)), because it isn't any more simple than the original expression.

Something you might consider is taking a basic calculus text for an integration strategy (I highly recommend Stewart's Calculus and Early Transcendentals). Usually these strategies will cover basic simplifications and transformations you can make to help get an easier integration. Looking at some of those guidelines should give you some inspiration for what kind of logic to put into your system.

Instead of using regular expressions for pattern matching, after tokenization, would be best to use a context-free grammar parser to create an expression tree. Then you can use basic rules on this tree. For example, if the root operation is +, you can try to integrate both terms separately and return the sum of the results. If it's *, check whether one term is the derivative of the other. If no rules seem to work, rearrange the tree using various rules (try factoring something out, etc). Of course, this approach won't work in all possible cases, but it's a start.

Hello

What mean a context-free grammar parser ?

ApochPiQ you obviously have an eye for capturing patterns in between steps. It must be that I take standard transformations too much as a routine so I overlooked the mid-steps (as was the case with the mentioned example). Actually I have done a reference list of about few hundred integrals categorized by function groups, methods, rules and now we will take that list and categorize the mid-steps for all of them.

In the meanwhile I've been researching finite field methods which seem applicable for simpler expressions with usage of Horowitz reduction. But a decent heuristic still must be in place.

I still haven't decided for the choice of scripting/expression language. I can implement a specific one for the application, but if one already exists with specific features I'm open for suggestions, since it would save at least some time.

What can I say... I had some very pedantic professors; I got in the habit of detailing every minute step to keep them happy [wink]

I think your best approach would be a hybrid of several categorization methods. Matei's suggestion of an expression tree is a good one; a tree-based representation of the expression would probably be the easiest to parse and check for patterns. I'm not too terribly versed in complex expression parsing, but I've played with some basic algebraic symbol manipulators in the past, and I used a sort of binary tree structure where individual constants and variables formed leaves, and operations formed nodes. The final tree was sorted from root to leaf in order of increasing operator precedence, so it was easy to evaluate with a simple recursive function. I imagine you can feed such a tree into some pattern recognition systems and get good results.

You will probably need at least a rudimentary form of stateful processing in the pattern logic. In some cases certain operations (expanding tan x to sin x/cos x, for example) make good sense, while in others they do not. This needs to be accounted for in some way.

As for a scripting language, I'm not aware of one which is particularly well-suited to this kind of logic, but then again I'm really not big on scripting in the first place. You'll definitely want a way to separate the more complex expression processing logic from the lower-level application code to save on recompiling; you may have the best luck just writing a minimal system yourself. As long as you make the syntax very simple it isn't that difficult to write a script interpreter, and you may find that it comes in handy to be able to define your own operations and functions for dealing with all this logic.

I almost wish I had some extra time, this would be a fun project to play with I think.

I would be honored by your presence on this project. If you ever change your mind you know who to ask ;).