# Risch algorithm

Part of a series of articles about :
Calculus :
$\int _{a}^{b}f'(t)\,dt=f(b)-f(a)$ :
Fundamental theorem
Limits
Continuity
Rolle's theorem
Mean value theorem
Inverse function theorem :
Differential
Definitions
Derivative (generalizations)
Differential
infinitesimal
of a function
total
Concepts
Differentiation notation
Second derivative
Implicit differentiation
Logarithmic differentiation
Related rates
Taylor's theorem
Rules and identities
Sum
Product
Chain
Power
Quotient
L'Hôpital's rule
Inverse
General Leibniz
Faà di Bruno's formula
Reynolds :
Integral
Lists of integrals
Integral transform
Leibniz integral rule
Definitions
Antiderivative
Integral (improper)
Riemann integral
Lebesgue integration
Contour integration
Integral of inverse functions
Integration by
Parts
Discs
Cylindrical shells
Substitution (trigonometric, tangent half-angle, Euler)
Euler's formula
Partial fractions (Heaviside's method)
Changing order
Reduction formulae
Differentiating under the integral sign
Risch algorithm :
Series
Geometric (arithmetico-geometric)
Harmonic
Alternating
Power
Binomial
Taylor
Convergence tests
Summand limit (term test)
Ratio
Root
Integral
Direct comparison
Limit comparison
Alternating series
Cauchy condensation
Dirichlet
Abel :
Vector
Gradient
Divergence
Curl
Laplacian
Directional derivative
Identities
Theorems
Gradient
Green's
Stokes'
Divergence
generalized Stokes
Helmholtz decomposition :
Multivariable
Formalisms
Matrix
Tensor
Exterior
Geometric
Definitions
Partial derivative
Multiple integral
Line integral
Surface integral
Volume integral
Jacobian
Hessian :
Advanced
Calculus on Euclidean space
Generalized functions
Limit of distributions :
Specialized
Fractional
Malliavin
Stochastic
Variations :
Miscellanea
Precalculus
History
Glossary
List of topics
Integration Bee
Mathematical analysis
Nonstandard analysis :
vte :
In symbolic computation, the Risch algorithm is a method of indefinite integration used in some computer algebra systems to find antiderivatives. 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 into a problem in algebra. It is based on the form of the function being integrated and on methods for integrating rational functions, radicals, logarithms, and exponential functions. 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.
The complete description of the Risch algorithm takes over 100 pages. The Risch–Norman algorithm is a simpler, faster, but less powerful variant that was developed in 1976 by Arthur Norman.
Some significant progress has been made in computing the logarithmic part of a mixed transcendental-algebraic integral by Brian L. Miller.

## Description

The Risch algorithm is used to integrate elementary functions. These are functions obtained by composing exponentials, logarithms, radicals, trigonometric functions, and the four arithmetic operations (+ − × ÷). 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. The algorithm suggested by Laplace is usually described in calculus textbooks; as a computer program, it was finally implemented in the 1960s.
Liouville formulated the problem that is solved by the Risch algorithm. Liouville proved by analytical means that if there is an elementary solution g to the equation g′ = f then there exist constants α$_i$ and functions u$_i$ and v in the field generated by f such that the solution is of the form
    $g=v+\sum _{i<n}\alpha _{i}\ln(u_{i})$
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 f e$^g$, where f and g are differentiable functions, we have
    $\left(f\cdot e^{g}\right)^{\prime }=\left(f^{\prime }+f\cdot g^{\prime }\right)\cdot e^{g},\,$
so if e$^g$ were in the result of an indefinite integration, it should be expected to be inside the integral. Also, as
    $\left(f\cdot (\ln g)^{n}\right)^{\prime }=f^{\prime }\left(\ln g\right)^{n}+nf{\frac {g^{\prime }}{g}}\left(\ln g\right)^{n-1}$
then if (ln g)$^n$ 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 in 1993) has an elementary antiderivative, as Wolfram Mathematica since version 13 shows (however, Mathematica does not use the Risch algorithm to compute this integral):
    $f(x)={\frac {x}{\sqrt {x^{4}+10x^{2}-96x-71}}},$
namely:
    ${\begin{aligned}F(x)=-{\frac {1}{8}}\ln &\,{\Big(x^{6}+15x^{4}-80x^{3}+27x^{2}-528x+781){\sqrt {x^{4}+10x^{2}-96x-71}}{\Big .}\\&-{\Big .}(x^{8}+20x^{6}-128x^{5}+54x^{4}-1408x^{3}+3124x^{2}+10001){\Big )}+C.\end{aligned}}$
But if the constant term 71 is changed to 72, it is not possible to represent the antiderivative in terms of elementary functions, as FriCAS also shows. Some computer algebra systems may here return an antiderivative in terms of non-elementary functions (i.e. elliptic integrals), 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 $\int {\frac {x+A}{\sqrt {x^{4}+ax^{3}+bx^{2}+cx+d}}}\,dx$ were solved by Chebyshev (and in what cases it is elementary), but the strict proof for it was ultimately done by Zolotarev.
The following is a more complex example that involves both algebraic and transcendental functions:
    $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)}}.$
In fact, the antiderivative of this function has a fairly short form that can be found using substitution $u=x+{\sqrt {x+\ln x}}$ (SymPy can solve it while FriCAS fails with "implementation incomplete (constant residues)" error in Risch algorithm):
    $F(x)=2\left({\sqrt {x+\ln x}}+\ln \left(x+{\sqrt {x+\ln x}}\right)\right)+C.$
Some Davenport "theorems" 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.

## 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 systems. The first implementation was done by Joel Moses in Macsyma soon after the publication of Risch's paper.
The case of purely algebraic functions was partially solved and implemented in Reduce by James H. Davenport – for simplicity it could only deal with square roots and repeated square roots and not general radicals or other non-quadratic algebraic relations between variables.
The general case was solved and almost fully implemented in Scratchpad, a precursor of Axiom, by Manuel Bronstein, there is Axiom's fork FriCAS, with active Risch and other algorithm development on github. However, the implementation did not include some of the branches for special cases completely. Currently in 2025, there is no known full implementation of the Risch algorithm.

## Decidability

The Risch algorithm applied to general elementary functions is not an algorithm but a 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 it is not known whether an algorithm performing such a check exists (current computer algebra systems use heuristics); moreover, if one adds the 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. 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 x, then the problem of zero-equivalence is decidable, so the Risch algorithm is a complete algorithm. Examples of computable constant fields are ℚ and ℚ(y), i.e., rational numbers and rational functions in y with rational-number coefficients, respectively, where y is an indeterminate that does not depend on 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.