
Re: History of Computer Algebra, factoring, integratioin
Posted:
Nov 11, 2001 4:14 PM


Richard Fateman schrieb:
> Dr. JÃ¼rgen Barsuhn wrote: > > ............ > >>Whether any of the well known CAS implement the Risch algorithm > >>"completely" should be asked. Perhaps there is an implementation > >>by Bronstein (in Axiom?) > >> > > > > There was a posting in this newsgroup a few weeks ago that there is so far no > > "Rischcomplete" CAS >
Actually this posting was a year ago and it was written by Bronstein. I attach its text below:
*************************** Subject: Re: Integration algorithm Date: Fri, 24 Nov 2000 10:38:01 +0100 From: Manuel Bronstein <manuel.bronstein@sophia.inria.fr> Organization: INRIA CC: mywyb2@cam.ac.uk, bmanuel@sophia.inria.fr Newsgroups: comp.softsys.math.maple
MYWY Becker wrote: > > Does anyone know whether the integration algorithm in Maple is > Rischcomplete? That is, if Maple's answer is not an elementary > function, can you be sure that there doesn't exist an elementary answer? > In other words, has Maple implemented the *entire* Rischlike algorithm, > in particular the *entire* algebraic case?
It is not Rischcomplete, even in the purely transcendental case (recursion problems in the logarithmic case). It is not complete either in the purely algebraic case (see below), and certainly not in the mixed algebraictranscendental case.
Neither is Axiom (despite various rumors). The difference is that Axiom issues an error message when an unimplemented branch of the algorithm is hit, so an unevaluated integral in Axiom is a proof that the integral is not elementary.
Neither is Mathematica, despite all the hype and ads (source code is unavailable but "black box" experiments show Mma's integrator to be in the, ahem, "low" category).
For the sceptics, here is an elementary integral of an algebraic function, whose integral is a simple logarithm, missed by the Risch integrators of both Maple and Mma:
Mathematica 4.0: g = x / Sqrt[x^4 + 10 x^2  96 x  71] Integrate[g,x] f = Log[(x^6+15 x^480 x^3+27 x^2528 x+781) Sqrt[x^4+10 x^296 x71]  x^8  20 x^6 + 128 x^5  54 x^4 + 1408 x^3  3124 x^2  10001]/8 Simplify[D[f,x]  g]
Maple 5.5 and Maple 6: g := x / sqrt(x^4 + 10*x^2  96*x  71); int(g,x); int(convert(g,RootOf),x); f := log((x^6+15*x^480*x^3+27*x^2528*x+781) * sqrt(x^4+10*x^296*x71)  x^8  20*x^6 + 128*x^5  54*x^4 + 1408*x^3  3124*x^2  10001)/8; normal(diff(f,x)g);
For fairness, here is an easy one that Axiom cannot decide: integrate(sqrt atan x,x)
 Manuel Bronstein  Manuel.Bronstein@sophia.inria.fr  http://www.inria.fr/cafe/Manuel.Bronstein/

