Did you know that there's an algorithm for symbolic integration that always works?

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

by amichail • 17 years ago

50 16 17 years ago

en.wikipedia.org

amichail6• 17 years ago

The algorithm will find the answer if one exists or tell you that there is no answer possible.

I wonder why it's never mentioned in high school Calculus classes. Symbolic integration as presented there looks very magical -- not algorithmic at all. You might mistake it for an AI problem (which it was for a while).

lacker2• 17 years ago

Learning a complicated algorithm to deterministically answer a question doesn't really help you understand the subject better in your first year of calculus. I'd rather have classes focus on different ways of understanding the simple parts of the subject, like the different applications of integrating polynomials or simple trig functions. Or even simpler stuff, like ways to think about functions other than a graph of x versus y. Or other ways to intuitively understand why d(f(2x)) = 2f'(2x). Or the relation between integration and big-O notation.

An intuitive understand of integration by parts is more valuable for a math student than this algorithm. (Although I doubt most high school calculus students could explain integration by parts a year later.)

amichail6• 17 years ago

Symbolic integration has a "problem solving" feel to it in high school and teachers generally focus on this part -- making many students feel stupid in the process if they can't figure it out.

Why not just tell them there's an algorithm for it and allow them to use a program to do the symbolic integration whenever necessary while solving an applied problem?

cperciva• 17 years ago

Yes, I did know that the Risch algorithm existed; and I've implemented it (or at least most of it).

I wonder why it's never mentioned in high school Calculus classes.

Because there's no way in hell that you want to ever apply the Risch algorithm by hand. As the wikipedia page says, it takes more than 100 pages to describe the algorithm; even just using it to compute the integral of x + 1/x would probably take hours without a computer.

amichail6• 17 years ago

But rather than focus on symbolic integration done by hand in high school, why not focus on higher level problem solving involving symbolic integration done by computer?

amichail6• 17 years ago

Also see http://groups.csail.mit.edu/mac/users/gjs/6.945/readings/sim...

vonsydov• 17 years ago

Yeah lol.

cousin_it• 17 years ago

Hmm. The article says it's not really an algorithm, because one of the steps requires checking if an expression is equivalent to zero, a problem that isn't today known to be decidable. Anyone here knowledgeable enough to supply details?

Edit: found the details in amichail's link. Yes, it's true; the algorithm isn't complete as of today.

sketerpot• 17 years ago

Another disappointing limitation that nobody has mentioned yet: this only works for elementary functions with integrals that are elementary functions. If you try to get this thing to integrate exp(x^2) dx, it will (correctly) say that there is no elementary integral. But the integral exists, and it's quite possible to find an infinite series solution, or to define the solution in terms of the erf function.

So, this is cool but not all it's cracked up to be.

http://en.wikipedia.org/wiki/Elementary_function_(differenti...

amichail6• 17 years ago

You could define a new function to represent the answer where there would be none otherwise, but that's not particularly useful unless that function is important in numerous other contexts.

And btw, the algorithm has been extended to handle some non-elementary functions.

Did you know that there's an algorithm for symbolic integration that always works?

Related Stories