View source for Risch algorithm

{{Use mdy dates|date=April 2022}}
{{short description|Method for evaluating indefinite integrals}}
{{calculus|expanded=integral}}
In [[symbolic computation]], the '''Risch algorithm''' is a method of indefinite integration used in some [[computer algebra system]]s to find [[antiderivative]]s. It is named after the American mathematician [[Robert Henry Risch]], a specialist in computer algebra who developed it in 1968.

The [[algorithm]] transforms the problem of [[integration (calculus)|integration]] into a problem in [[differential algebra|algebra]]. It is based on the form of the function being integrated and on methods for integrating [[rational function]]s, [[Nth root|radical]]s, [[logarithm]]s, and [[exponential function]]s. Risch called it a [[decision procedure]], because it is a method for deciding whether a function has an [[elementary function]] as an indefinite integral, and if it does, for determining that indefinite integral. However, the algorithm does not always succeed in identifying whether or not the antiderivative of a given function in fact can be expressed in terms of elementary functions.{{Example needed|date=December 2021}}

The complete description of the Risch algorithm takes over 100 pages.<ref>{{harvnb|Geddes|Czapor|Labahn|1992}}.</ref> The '''Risch–Norman algorithm''' is a simpler, faster, but less powerful variant that was developed in 1976 by [[Arthur Norman (computer scientist)|Arthur Norman]].

Some significant progress has been made in computing the logarithmic part of a mixed transcendental-algebraic integral by Brian L. Miller.<ref>{{Cite web |last=Miller |first=Brian L. |date=May 2012 |title=On the integration of elementary functions: Computing the logarithmic part |url=https://ttu-ir.tdl.org/items/f7a0f000-885f-49f4-a066-77cb9f3fea6b |access-date=2023-12-10}}</ref>

==Description==
The Risch algorithm is used to integrate [[elementary function]]s. These are functions obtained by composing exponentials, logarithms, radicals, trigonometric functions, and the four arithmetic operations ({{nowrap|+ − × ÷}}). [[Pierre-Simon Laplace|Laplace]] solved this problem for the case of [[rational functions]], as he showed that the indefinite integral of a rational function is a rational function and a finite number of constant multiples of logarithms of rational functions {{citation needed|date=June 2021}}. The algorithm suggested by Laplace is usually described in calculus textbooks; as a computer program, it was finally implemented in the 1960s.{{Citation needed|date=November 2021}}

[[Joseph Liouville|Liouville]] formulated the problem that is solved by the Risch algorithm. Liouville proved by analytical means that if there is an elementary solution {{math|''g''}} to the equation {{math|1=''g''′ = ''f''}} then there exist constants {{math|''α<sub>i</sub>''}} and functions {{math|''u<sub>i</sub>''}} and {{math|''v''}} in the field generated by {{math|''f''}} such that the solution is of the form

:<math> g = v + \sum_{i<n} \alpha_i \ln (u_i) </math>

Risch developed a method that allows one to consider only a finite set of functions of Liouville's form.

The intuition for the Risch algorithm comes from the behavior of the exponential and logarithm functions under differentiation. For the function {{math|''f'' ''e<sup>g</sup>''}}, where {{math|''f''}} and {{math|''g''}} are [[differentiable function]]s, we have

: <math> \left(f \cdot e^g\right)^\prime = \left(f^\prime + f\cdot g^\prime\right) \cdot e^g, \, </math>

so if {{math|''e<sup>g</sup>''}} were in the result of an indefinite integration, it should be expected to be inside the integral. Also, as

: <math> \left(f \cdot(\ln g)^n\right)^\prime =  f^\prime \left(\ln g\right)^n + n f  \frac{g^\prime}{g} \left(\ln g\right)^{n - 1} </math>

then if {{math|(ln ''g'')<sup>''n''</sup>}} were in the result of an integration, then only a few powers of the logarithm should be expected.

==Problem examples==
Finding an elementary antiderivative is very sensitive to details. For instance, the following algebraic function (posted to sci.math.symbolic by [[Henri Cohen (number theorist)|Henri Cohen]] in 1993<ref>{{Cite web |last=Cohen |first=Henri |date=December 21, 1993 |title=A Christmas present for your favorite CAS |url=https://groups.google.com/g/sci.math.symbolic/c/BPOIUsVMuY0/m/2moCKQY_cz4J }}</ref>) has an elementary antiderivative, as [[Wolfram Mathematica]] since version 13 shows (however, Mathematica does not use the Risch algorithm to compute this integral):<ref>{{Cite web|title=Wolfram Cloud|url=https://www.wolframcloud.com/obj/d9af14f6-3b98-43c4-b996-11dedc9d9f10|access-date=December 11, 2021|website=Wolfram Cloud|language=en}}</ref><ref>This example was posted by Manuel Bronstein to the [[Usenet]] forum ''comp.soft-sys.math.maple'' on November 24, 2000.[https://groups.google.com/d/msg/comp.soft-sys.math.maple/5CcPIR9Ft-Y/xYfGiyJauuoJ]</ref>

: <math> f(x) = \frac{x}{\sqrt{x^4 + 10 x^2 - 96 x - 71}},</math>

namely:

: <math>\begin{align} F(x) = - \frac{1}{8}\ln &\,\Big( (x^6+15 x^4-80 x^3+27 x^2-528 x+781) \sqrt{ x^4+10 x^2-96 x-71} \Big. \\ & {} - \Big .(x^8 + 20 x^6 - 128 x^5 + 54 x^4 - 1408 x^3 + 3124 x^2 + 10001) \Big) + C. \end{align}</math>

But if the constant term 71 is changed to 72, it is not possible to represent the antiderivative in terms of elementary functions,<ref name=":0" /> as [[FriCAS]] also shows. Some [[computer algebra system]]s may here return an antiderivative in terms of ''non-elementary'' functions (i.e. [[elliptic integral]]s), which are outside the scope of the Risch algorithm. For example, Mathematica returns a result with the functions EllipticPi and EllipticF. Integrals in the form <math>\int \frac{x+A}{\sqrt{x^4+ax^3+bx^2+cx+d}}\, dx</math> were solved by [[Pafnuty Chebyshev|Chebyshev]] (and in what cases it is elementary),<ref>{{Cite book |last=Chebyshev |first=P. L. |url=http://archive.org/details/117744684_001 |title=Oeuvres de P.L. Tchebychef |date=1899–1907 |publisher=St. Petersbourg, Commissionaires de l'Academie imperiale des sciences |others=University of California Berkeley |pages=171–200 |language=French}}</ref> but the strict proof for it was ultimately done by [[Yegor Ivanovich Zolotarev|Zolotarev]].<ref name=":0">{{Cite journal|last=Zolotareff|first=G.|date=December 1, 1872|title=Sur la méthode d'intégration de M. Tchébychef|url=https://doi.org/10.1007/BF01442910|journal=Mathematische Annalen|language=fr|volume=5|issue=4|pages=560–580|doi=10.1007/BF01442910|s2cid=123629827 |issn=1432-1807}}</ref>

The following is a more complex example that involves both algebraic and [[transcendental function]]s:<ref>{{harvnb|Bronstein|1998}}.</ref>

: <math>f(x) = \frac{x^2+2x+1+ (3x+1)\sqrt{x+\ln x}}{x\,\sqrt{x+\ln x}\left(x+\sqrt{x+\ln x}\right)}.</math>

In fact, the antiderivative of this function has a fairly short form that can be found using substitution  <math>u = x + \sqrt{x + \ln x}</math> ([[SymPy]] can solve it while FriCAS fails with "implementation incomplete (constant residues)" error in Risch algorithm):

: <math>F(x) = 2 \left(\sqrt{x+\ln x} + \ln\left(x+\sqrt{x+\ln x}\right)\right) + C.</math>
Some Davenport "theorems"{{Definition needed|Davenport has not been mentioned to this point in the article, and his name only appears once later, and not in the context of theorems.|date=July 2022}} are still being clarified. For example in 2020 a counterexample to such a "theorem" was found, where it turns out that an elementary antiderivative exists after all.<ref>{{Cite journal |last1=Masser |first1=David |last2=Zannier |first2=Umberto |date=December 2020 |title=Torsion points, Pell's equation, and integration in elementary terms |url=https://www.intlpress.com/site/pub/pages/journals/items/acta/content/vols/0225/0002/a002/ |journal=Acta Mathematica |language=EN |volume=225 |issue=2 |pages=227–312 |doi=10.4310/ACTA.2020.v225.n2.a2 |s2cid=221405883 |issn=1871-2509|doi-access=free |hdl=11384/110046 |hdl-access=free }}</ref>

==Implementation==
Transforming Risch's theoretical algorithm into an algorithm that can be effectively executed by a computer was a complex task which took a long time.

The case of the purely transcendental functions (which do not involve roots of polynomials) is relatively easy and was implemented early in most [[computer algebra system]]s. The first implementation was done by [[Joel Moses]] in [[Macsyma]] soon after the publication of Risch's paper.<ref>{{harvnb|Moses|2012}}.</ref>

The case of purely algebraic functions was partially solved and implemented in [[Reduce (computer algebra system)|Reduce]] by [[James H. Davenport]] – for simplicity it could only deal with square roots and repeated square roots and not general [[Radical expression|radicals]] or other non-quadratic [[Algebraic equation|algebraic relations]] between variables.<ref>{{harvnb|Davenport|1981}}.</ref>

The general case was solved and almost fully implemented in Scratchpad, a precursor of [[Axiom (computer algebra system)|Axiom]], by Manuel Bronstein, there is Axiom's fork FriCAS, with active Risch and other algorithm development on github.<ref>{{Citation |title=fricas/fricas |date=2025-02-05 |url=https://github.com/fricas/fricas |access-date=2025-02-06 |publisher=fricas}}</ref><ref>{{harvnb|Bronstein|1990}}.</ref> However, the implementation did not include some of the branches for special cases completely.<ref>{{Cite web |date=2023-09-30 |title=MathAction RischImplementationStatus |url=https://wiki.fricas.org/RischImplementationStatus |access-date=2024-12-23 |archive-url=https://web.archive.org/web/20230930102649/https://wiki.fricas.org/RischImplementationStatus |archive-date=September 30, 2023 }}</ref><ref>{{Cite web |last=Bronstein |first=Manuel |date=September 5, 2003 |title=Manuel Bronstein on Axiom's Integration Capabilities |url=https://groups.google.com/g/sci.math.symbolic/c/YXlaU8WA2JI/m/1w1MxrSpm6IJ |access-date=2023-02-10 |website=groups.google.com}}</ref> Currently in 2025, there is no known full implementation of the Risch algorithm.<ref>{{Cite web |date=Oct 15, 2020 |title=integration - Does there exist a complete implementation of the Risch algorithm? |url=https://mathoverflow.net/questions/374089/does-there-exist-a-complete-implementation-of-the-risch-algorithm |access-date=2023-02-10 |website=MathOverflow |language=en}}</ref>

==Decidability==
The Risch algorithm applied to general elementary functions is not an algorithm but a [[RE (complexity)|semi-algorithm]] because it needs to check, as a part of its operation, if certain expressions are equivalent to zero ([[constant problem]]), in particular in the constant field. For expressions that involve only functions commonly taken to be [[elementary function|elementary]] it is not known whether an algorithm performing such a check exists (current [[computer algebra system]]s use heuristics); moreover, if one adds the [[absolute value|absolute value function]] to the list of elementary functions, then it is known that no such algorithm exists; see [[Richardson's theorem]].

This issue also arises in the [[polynomial division algorithm]]; this algorithm will fail if it cannot correctly determine whether coefficients vanish identically.<ref>{{Cite web| title= Mathematica 7 Documentation: PolynomialQuotient| url= http://reference.wolfram.com/mathematica/ref/PolynomialQuotient.html| work= Section: Possible Issues| access-date= July 17, 2010}}</ref> Virtually every non-trivial algorithm relating to polynomials uses the polynomial division algorithm, the Risch algorithm included.  If the constant field is [[computable]], i.e., for elements not dependent on {{math|''x''}}, then the problem of zero-equivalence is decidable, so the Risch algorithm is a complete algorithm. Examples of computable constant fields are {{math|&Qopf;}} and {{math|&Qopf;(''y'')}}, i.e., rational numbers and rational functions in {{mvar|''y''}} with rational-number coefficients, respectively, where {{math|''y''}} is an indeterminate that does not depend on {{math|''x''}}.

This is also an issue in the [[Gaussian elimination]] matrix algorithm (or any algorithm that can compute the [[nullspace]] of a matrix), which is also necessary for many parts of the Risch algorithm.  Gaussian elimination will produce incorrect results if it cannot correctly determine whether a pivot is identically zero{{Citation needed|date=January 2012}}.

==See also==
{{Portal|Computer programming|Mathematics}}
*[[Axiom (computer algebra system)]]
*[[Closed-form expression]]
*[[Incomplete gamma function]]
*[[Lists of integrals]]
*[[Liouville's theorem (differential algebra)]]
*[[Nonelementary integral]]
*[[Symbolic integration]]

==Notes==
{{reflist}}

==References==

*{{Cite journal
 | last = Bronstein
 | first = Manuel
 | title = Integration of elementary functions
 | journal = [[Journal of Symbolic Computation]]
 | volume = 9
 | issue = 2
 | year = 1990
 | pages = 117–173
 | doi = 10.1016/s0747-7171(08)80027-2
 | doi-access = 
 }}

*{{Cite journal |last=Bronstein |first=Manuel |title=Symbolic Integration Tutorial |year=1998 |url=http://www-sop.inria.fr/cafe/Manuel.Bronstein/publications/issac98.pdf |journal=ISSAC'98, Rostock (August 1998) and Differential Algebra Workshop, Rutgers}}

*{{Cite book
 | last = Bronstein
 | first = Manuel
 | title = Symbolic Integration I
 | publisher = Springer
 | year = 2005
 | isbn = 3-540-21493-3
 }}

*{{Cite book
 | last = Davenport
 | first = James H.
 | author-link = James H. Davenport
 | title = On the integration of algebraic functions
 | publisher = Springer
 | series = [[Lecture Notes in Computer Science]]
 | volume = 102
 | year = 1981
 | isbn =  978-3-540-10290-8
 }}

*{{Cite book
 | last1 = Geddes
 | first1 = Keith O.
 | author1-link = Keith Geddes
 | last2 = Czapor
 | first2 = Stephen R.
 | last3 = Labahn
 | first3 = George
 | title = Algorithms for computer algebra
 | publisher = Kluwer Academic Publishers
 | location = Boston, MA
 | year = 1992
 | pages = xxii+585
 | isbn = 0-7923-9259-0
 | doi = 10.1007/b102438
 | bibcode = 1992afca.book.....G
 | url = https://archive.org/details/algorithmsforcom0000gedd
 }}

*{{Cite journal
 | last = Moses
 | first = Joel
 | title = Macsyma: A personal history
 | journal = [[Journal of Symbolic Computation]]
 | volume = 47
 | issue = 2
 | year = 2012
 | pages = 123–130
 | doi = 10.1016/j.jsc.2010.08.018
 | doi-access = 
 }}

*{{Cite journal
 | last = Risch
 | first = R. H.
 | title = The problem of integration in finite terms
 | journal = [[Transactions of the American Mathematical Society]]
 | year = 1969
 | volume = 139
 | pages = 167–189
 | publisher = American Mathematical Society
 | doi = 10.2307/1995313
 | jstor = 1995313
 | doi-access = free
 }}

*{{Cite journal
 | last = Risch
 | first = R. H.
 | title = The solution of the problem of integration in finite terms
 | journal = [[Bulletin of the American Mathematical Society]]
 | year = 1970
 | volume = 76
 | issue = 3
 | pages = 605–608
 | doi = 10.1090/S0002-9904-1970-12454-5
 | doi-access = free
 }}

*{{Cite journal
 | last = Rosenlicht
 | first = Maxwell
 | title = Integration in finite terms
 | journal = [[American Mathematical Monthly]]
 | year = 1972
 | volume = 79
 | issue = 9
 | pages = 963–972
 | publisher = Mathematical Association of America
 | doi = 10.2307/2318066
 | jstor = 2318066
 }}

==External links==
*{{MathWorld
 | urlname = RischAlgorithm
 | title = Risch Algorithm
 | author = Bhatt, Bhuvanesh
}}

{{Integrals}}

{{DEFAULTSORT:Risch Algorithm}}
[[Category:Computer algebra]]
[[Category:Integral calculus]]
[[Category:Differential algebra]]