From: Andreas "-I filter junkmail-" Neubacher Newsgroups: sci.math.symbolic Subject: Re: Theory symbolic integration. Date: 18 Oct 1998 08:19:51 GMT In article , Dima Pasechnik writes: DP> lescouhier@my-dejanews.com writes: DP> DP> > Does anybody know where to find some theory about algorithms for symbolic DP> > integration on the net ? In my diploma thesis titled "An Introduction to the Symbolic Integration of Elementary Functions" I dealt with the topic. You can find it in PostScript format at http://www.risc.uni-linz.ac.at/library/DataBase/search.cgi?refkey=10196&OF=5 Hope that helps, Andreas. _________o_________o_________________o___________________________o_________ |Andreas |EMAIL: andreas.|URL: http://www.geocities.| |NEUBACHER|neubacher@acm.org|com/CapeCanaveral/Lab/7133/| _________|_________|_________________|___________________________|_________ Random quote (Karel Capek) Das Höchste leistet der Mensch aus Verzweiflung, Verlassenheit, aus Einsamkeit, Betäubung. Weil ihm nichts genügt. ___________________________________________________________________________ ============================================================================== From: David Maurice Cooke Newsgroups: sci.math.symbolic Subject: Re: Theory symbolic integration. Date: 22 Oct 1998 11:36:11 -0700 lescouhier@my-dejanews.com writes: > > Hey there, > > Does anybody know where to find some theory about algorithms for symbolic > integration on the net ? I have the most powerful calculator on the face of > the earth : The HP48. I would like to take a shot at programming these > algorithms on it. > > Thanks. > You can look at the source code for Erable and Alg48, which both implement the Risch algorithm. Erable can be found at http://perso.wanadoo.fr/bernard.parisse/english.html and Alg48 can be found at http://www.cs.pitt.edu/~fiechter/hp48/ -- |>|\/|< ---------------------------------------------------------------------------- David M. Cooke dmcooke@sfu.ca ============================================================================== From: mheiskan@hut.fi (Mika Heiskanen) Newsgroups: sci.math.symbolic Subject: Re: Theory symbolic integration. Date: 05 Nov 1998 13:23:49 +0200 lescouhier@my-dejanews.com wrote: > Does anybody know where to find some theory about algorithms for symbolic > integration on the net ? I have the most powerful calculator on the face of > the earth : The HP48. I would like to take a shot at programming these > algorithms on it. to which David Maurice Cooke replies: >You can look at the source code for Erable and Alg48, which both >implement the Risch algorithm. This is incorrect. Erable has a heuristic front-end followed by a partial implementation of the Risch algorithm. ALG48 uses only heuristic methods, except for rational polynomials of course (partial Rothstein-Trager). By partial implementation I mean things like not implementing a RootOf notation (or algebra over general extensions), and not implementing one of the special cases in the Risch algorithm (can't remember which one it was, will have to ask the author). and Richard J. Fateman replied > Frankly, if someone wants to write a symbolic integration > program in an HP 48, the way to do it is to use some > hackish methods as for example described in Peter Norvig's > Paradigm's of AI programming. In my opinion Mr. Fateman's comments on 'hackish' algorithms is based on his perception of a calculator as a slow speed machine with a rudimentary programming language and not based on facts in any way. Erable and ALG48 use many sophisticated algorithms, including Buchberger for Grobner bases, Berlekamp for factorization, Risch for integration etc. Many of the lowest level subroutines are written in full assembly language. In fact, I even wrote the Grobner basis calculation in full assembly language, until I learned that it still couldn't beat the version with factorization during the algorithm for most of the systems of equations which have been used to test the various computer algebra systems in various journals. TI89 uses a partial implementation of the Derive computer algebra system, which besides a couple sophisticated algorithm does however use a lot of heuristic methods. In practise the TI89 will often give incomplete results for complex tests because of the use of non-deterministic algorithms. To give an example, the TI89 does not perform full factorization of a multivariate polynomial over the integers, unless it can find it by some heuristic methods. ALG48 does perform full factorization, but will of course have lower practical limitations than systems running on CPU's 100 times faster and with 100 times more memory. As for the original question, the references you were given in other articles are sufficient. Also, there is nothing wrong in using hackish algorithms if they get the job done. It is common practise to use a heuristic front-end for integration to get the results in the form the user would expect, and to get the results fast. However, I should warn you that you need very efficient polynomial arithmetic for your implementation to be of practical use. I know from personal experience that you cannot get fast results without a large investment in the speed of the basic polynomial arithmetic. -- --- --> Mika Heiskanen mheiskan@gamma.hut.fi http://www.hut.fi/~mheiskan ============================================================================== From: fateman@peoplesparc.cs.berkeley.edu (Richard J. Fateman) Newsgroups: sci.math.symbolic Subject: Re: Theory symbolic integration. Date: 5 Nov 1998 17:46:58 GMT In article , Mika Heiskanen wrote: > >and Richard J. Fateman replied > >> Frankly, if someone wants to write a symbolic integration >> program in an HP 48, the way to do it is to use some >> hackish methods as for example described in Peter Norvig's >> Paradigm's of AI programming. > >In my opinion Mr. Fateman's comments on 'hackish' algorithms is based >on his perception of a calculator as a slow speed machine with a >rudimentary programming language and not based on facts in any >way. Well, not exactly. I wrote that note before looking at the impressive work of Erable and ALG48, and had I been aware of it I certainly would have pointed to them. Can you put full-scale algorithms into a small machine? Sure. The DERIVE people have been doing this for many years. Note that significant algorithms used by researchers in the early days of computer algebra were written for machine --large for their time (1968!) that had less memory than you can buy on a Palm Pilot III. When I indicated hackish methods, I did not mean to say that that was ALL you could fit, but that you were most likely to be happy with such programs. Since a simple "derivative divides" integration program probably does 80-90% of freshman calculus textbook problems, and (especially the typical, partial) Risch integration algorithm does far less with much more code, and produces unreadable answers, you might be unhappy with it. In fact, Mika agrees with me on this.... >algorithms if they get the job done. It is common practise to use a >heuristic front-end for integration to get the results in the form the >user would expect, and to get the results fast. > >However, I should warn you that you need very efficient polynomial >arithmetic for your implementation to be of practical use. I know from >personal experience that you cannot get fast results without a large >investment in the speed of the basic polynomial arithmetic. I do not agree here: while this is certainly a good idea for factoring (etc). Heuristic integration does not depend so heavily on polynomial arithmetic. -- Richard J. Fateman fateman@cs.berkeley.edu http://http.cs.berkeley.edu/~fateman/ ============================================================================== From: fateman@peoplesparc.cs.berkeley.edu (Richard J. Fateman) Newsgroups: sci.math.symbolic Subject: Re: Theory symbolic integration. Date: 6 Nov 1998 15:45:18 GMT In article , Mika Heiskanen wrote: > > >I meant to say that there is nothing wrong in using heuristic algorithms >as a front-end to the Risch algorithm :) I don't disagree, but I suspect that the vast majority of integrals done by Macsyma are done by non-Risch methods. I also think that "heuristic" is being used as some kind of negative comment suggesting either non-deterministic or sometimes erroneous. In fact procedures like "derivative divides" are deterministic and either produce the right answer -- an antiderivative -- or say that they can't tell. This is almost precisely what the Risch "algorithm" does as implemented by most, perhaps all? systems. The program says (a) here is the antiderivative (b) (sometimes) I can prove the antiderivative doesn't exist in terms of elementary functions (c) (because of inadequate implementation or simplification [theoretically undecidable!] I can't tell. So we should probably be referring to implementations as Risch Heuristics. >> Can you put full-scale algorithms into a small machine? Sure. The >> DERIVE people have been doing this for many years. > >Hmm, can you actually confirm that they are indeed using full-scale >algorithms on PCs? The TI89 implementation seems to rely a lot on >heuristic algorithms. 1. I don't have any inside knowledge of Derive today, but you are right that MuMath, a predecessor to Derive, had partial implementations appropriate to its other limitations (e.g. 640kbytes!) But it does not take a lot of space to put in complete algorithms that do not scale up. The Kronecker polynomial factoring algorithm, unadorned with speedups, can is correct for polynomials of any degree and any number of variables. While it is complete, and can be written in 3 pages of Lisp, it can be very slow. It can be fast for low degree, one variable, small coefficients, and that was fine for MuMath. 2. "heuristic algorithms"? I don't know. But my colleague Prof. Kahan has numbers of examples where Derive gets the right answer (for example, to integration problems) where the 3M systems do not. Regards -- Richard J. Fateman fateman@cs.berkeley.edu http://http.cs.berkeley.edu/~fateman/ ============================================================================== [Some related threads: -- djr] ============================================================================== From: "Earl F. Glynn" Newsgroups: sci.math Subject: Re: Symbolic Integration (An algorithm) Date: 9 Oct 1998 04:02:08 GMT Christopher H. de Castro wrote in message <361d4380.0@stnws02.atl.mediaone.net>... >I am interested in finding a reference (or references) to such an >algorithm(s). Sedgewick makes reference to Mathematica (i.e. Wolfram et. >al.) but does not reference specific publications relating to these >algorithms (other that the Mathematica text). Thanks in advance. The "classic" paper on this is James R. Slagle's "A Heuristic Program That Solves Symbolic Integration Problems in Freshman Calculus: Symbolic Automatic Integrator (SAINT)." Report 5 G-0001, MIT Lincoln Laboratory, May 1961. Also, J. ACM 10:507-520, 1963. Also try: J. Moses, "Symbolic Integration: The Stormy Decade," C. ACM, Vol 14, No. 8, pp. 548-560, 1971. I worked on a LISP Symbolic Integration/Differentiation Program for a semester project in an AI class in the mid 80s at GWU. It was more complicated than I expected. The prof at the time didn't want to call this "AI" even though it had been called "AI" in the 70s. You might try AI and/or LISP books, too. efg _________________________________________ efg's Computer Lab: http://infomaster.net/external/efg Earl F. Glynn E-Mail: EarlGlynn@att.net Overland Park, KS USA ============================================================================== From: jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard) Newsgroups: sci.math Subject: Re: Symbolic Integration (An algorithm) Date: Fri, 09 Oct 1998 17:02:31 GMT "Earl F. Glynn" wrote, in part: [Above article quoted -- djr] There is a specific algorithm now that isn't heuristic. It was a recent development, and the major symbolic packages were converted to use it. I wish I could remember the reference. One page relating to Mathematica mentions a paper by R. H. Risch in 1969 without naming it. John Savard http://members.xoom.com/quadibloc/index.html ============================================================================== From: Marc Mertens Newsgroups: sci.math Subject: Re: Symbolic Integration (An algorithm) Date: Fri, 09 Oct 1998 20:42:54 +0200 "Christopher H. de Castro" wrote: > > I am interested in finding a reference (or references) to such an > algorithm(s). Sedgewick makes reference to Mathematica (i.e. Wolfram et. > al.) but does not reference specific publications relating to these > algorithms (other that the Mathematica text). Thanks in advance. > The algorithm they are refering to is the 'Risch Integration Algortithm' , some execellent books are 'Algorithms for computer algebra' from Ceddes,Czapor and Labahn and 'Symbolic Integration' from Manual Bronstein. Hopes this helps Marc Mertens mmertens@akam.be ============================================================================== From: sale1@llnl.gov (Ken Sale) Newsgroups: sci.math Subject: Re: Symbolic Integration (An algorithm) Date: Fri, 09 Oct 1998 12:24:25 -0700 In article <361d4380.0@stnws02.atl.mediaone.net>, "Christopher H. de Castro" wrote: > In reading Sedgewick's "Algorithms in C++," he makes the following > reference: > > "...The large number of rules available to be applied to a particular > function makes symbolic integration a difficult task. Indeed, it has only > recently been shown that there is an algorithm for this task: a procedure > that either returns the integral of any given function or says that the > answer cannot be expressed in terms of elementary functions." > > I am interested in finding a reference (or references) to such an > algorithm(s). Sedgewick makes reference to Mathematica (i.e. Wolfram et. > al.) but does not reference specific publications relating to these > algorithms (other that the Mathematica text). Thanks in advance. > > Chris de Castro > cdecastro@atl.mediaone.net The Risch Structure Theorem is in: Risch, R (1969), "The Problem of Integration in Finite Terms,", in Transactions of the American Mathematical Society v. 139, p 167. An overview of the implementation of the algorithm in Mathematica can be found in the notes for a tutorial given by Kelly Roach at a Mathematica conference (around 1992 I think). -- I do not represent LLNL or US DOE or UC ============================================================================== From: jwill-herzsprung@t-online.de (Jürgen Will) Newsgroups: sci.math.symbolic Subject: Re: implementation of the risch algorithm Date: 20 Dec 1998 22:30:26 +0100 Terry Bowman schreibt: > I am looking for some information on the risch algorithm. R.H.Risch: Trans.A.M.S. (1969) 139 R.H.Risch: Bull.A.M.S. (1970) 76 R.H.Risch: Proc.AMS (1976) 57 R.H.Risch: Am.J.Math. (1979) 101 M.F.Singer: J.Symbolic Comput. (1990) (10) 59-94 M.Karr: J.Assoc.Comp.Mach. 28 (1981) (2) 305-350 M.Karr: J.Symbolic Comput. (1985) (1) 303-315 J.C.Lafon: Computing, Suppl. 4 (1982) 71-77 Indefinite summation: see Gosper, Zeilberger, and Wilf.