An ]ntrgduction to tha Rlech Integration Algorithm

bg
Joel Hoses
Laboratorg .for Computer Science
Hanachuestts I n s t i t u t e of Technologg
Cambridge, Massachusetts 02139

Abstract" [ f one wished an algorithm which transformed

the integrand (input) to the integral (output), t h i n
one gould have to account for the exi.stanca of mang
d i f f e r e n t functions in the integral that did not
Riech's decision appear In the Intagrand. As a matter of fact there
procedure for determining the need'not be such a great variance batMssn the
I n t e g r a b i l i t g in closed form of functions In the integral and.the intsgrand - the
the elsmentarg functions of the s i t u a t i o n Is due to notational devices t r a d i t i o n a l l g
calculus is presented via aaplo.ge ~ bg mathematicians. Thus sin (x) and col (~)
examples. The exponential and • r e . r e l a t e d bg eln2(x) + coe2(x) - 1 and arcsin (x)
logarithmic cases of the and ~/l'--x'2-are related b~__r
algorithms had been implemented
f o r the MACSYMAsgetem several arcetn(x)=?~l.og ( i x ~ l - x Z ) . As Me s h a l l see one
gears ago. The implementation of needs to grant the existence of nag logs in the
the algebraic case of the i n t e g r a l , but no'other new functions! T h e underlglng
algorithm le the subject of c o n s t r a i n t is t h a t the integrand and integral be
expressed In terms of a4gebraicall W independent
current research.
f u n c t l o n s , t h a t is functions ghich do not have a
n o n t r i v l a l polgnomial r e l a t l o n s h i p among them. The
Algorithms for i n d e f i n i t e integration have, u t i l i t y of dealing ~ i t h algebraicallg independent
of course, been of interest to mathematicians for functions was noted bg R l t t when he developed the
three centuries. The state of the art in the mid f i e l d of d i f f e r e n t i a l algebra. Modern approaches to
ISGa'e, as evidenced bg calculus texts, shows that i n d e f i n i t e integration therefore use the
mathematicians believed the problem to require representational devices of d i f f e r e n t i a l •lgabr•~
h e u r i s t i c s (such as Integration-bg-parte) and to be
one which possessed no general algorithm, In fact, In d i f f e r e n t i a l algebra .the rat.iqnal
the famous mathematician Hardg Indicated in 1985 that functions in x, R(x), ghlch are quotients of
the I n d e f i n i t e integration, problem for a sUbset of polgnomials in x, form a f i e l d (one can add,
the elementarg functions ( i . e . the question of subtract, multiplg and divide rational functions and
Mhether the closed.form integral existed or not) s t i l l obtain rational functions), mhlch Is closed
could not be decided bg an algorithm. This Is under d i f f e r e n t i a t i o n (one can d i f f e r e n t i a t e •
s u r p r i s i n g because there was l i t t l e i n k l i n g in 1985 r a t i o n a l function and s t i l l obtain a r a t i o n a l
that ang problems were unsolvable bg algorithms. f u n c t i o n ) . The d i f f e r e n t i a l f i e l d R(x, i x ) , mhlch
Hardg appears to have been the f i r s t to conjecture contains rational functions in.e x whose c o e f f i c i e n t s
such a p o s e i b i l i t g . The irong in Hardg'e conjecture are polgnomials or rational functions in x, Is an
is that he was proved mrong in 1978:bgRobert Rlsch e x t e n s i o n f i e l d of R(x}. Note that e2x £ R(x,e x)
[1,2,3] who obtained an algor.ithm for determining
Hhether the integral of an elementarg function e x i s t s since e2X= (aX)2. In fact, one should .not deal
' i n closed form and for finding the integral Mhen I t with • 2x as a separate function. On the other hand,
so existed.
• x2 ~ R ( x , e ~) ( t h i s requires proof, mhlch me shall
One view as to mhg mathematicians considered not.deal mlth here). ThulR(x,aX, ex2) is •
the i n d e f i n i t e Integration problem to be d i f f i c u l t n o n t r ! v l a l extension of R(x,eX), Likewise:log x
can be obtained bg considering the following
integrals= R(x, eX, ex2) and log (x+l) + R(x,eX,aX2,1og x), but
log (x2+x) £ R(x'eX,eX2,1og x, log (x+l)) l i n e s
/ s i n x dx = - cos x
log (x2+x) - log x + log (x+l),+ 2knl, We Could, i f
meso wished, consider sin x to,be a nag function
1
(rather thaner:_ej~L ~- e-Ix/21), but then col x mould
f - - - dx - log x
X
have to be Vt-sln ~ x, etc. This Is not • good idea
computationallg. Hence trigOnometric functions M i l l
be considered in t h e i r complex exponential forn.
1
/- .... dx ,, arcs In x
-x2

425
 Given these concepts we can represent in the i n t e g r a l except for constant m u l t i p l e s of new
logs,
x2 log (log (x) + ex)
In terms of the f i e l d ideas above, i f f { x ] £
e2x - log (x+l} F(x] - R(x, h l ( x ) , . . . . hklX]}, and f f ( x ) dx - g ( x )
where g(x) is an elementary function also, then
as a member of L l o u v i l l s ' s theorem becomes
R(x, l o g ( x ) , s x, log (log (x)+eX], log ( x + l ) )
g(x) . Yo(x] + ~ c i log V I(x~

or as a member of the isomorphic f i e l d where VB(X}, V l l x ] £ F ( x ) ,

R(x, l o g ( x ~ l ) , l o ~ ( x ] , eX, l o g ( I o g ( x ) + e x ) ] . Note t h a t and c i are constants.
the elementarg functions of the calculus can now, in
g e n e r a l , be shown to be elements of some extension
f i e l d of the r a t i o n a l functions, ghere each e x t e n s i o n In other words, the integral of a f u n c t i o n in a f i e l d
is e i t h e r a new Iogarithm|c~sxponential or a l g e b r a i c of elementarg functions is a member of the f i e l d p l u s
function. constant m u l t i p l e s of logs of elements of the f i e l d .

Now that Me have somenotion of f i e l d s of L I o u v l l l s ' s theorem in i t s modern f o r m u l a t i o n

f u n c t i o n s and t h e i r extensions, we can ask the leads to an algorithm for f i n d i n g VO, V I which is
f o l l o w i n g question= f a i r l g simple (and not too d i f f i c u l t to implement on
a computer) in cases which involve onlg logs and
I f f ( x ) E R ( x , h l ( x ) . . . . . hk(X]}, an e x t e n s i o n e x p o n e n t i a l s ( i . e , no a l g e b r a i c f u n c t i o n s ] . The
f i e l d of the r a t i o n a l s where the h i ( x ) are log, a l g e b r a i c case which inherentlg deals w i t h f u n c t i o n s
which are not a l g e b r a i c a l l g independent is being
e x p o n e n t i a l , and a l g e b r a i c functions, and i f f ( x ) has worked on now and requires more complex machinery
an i n t e g r a l g(x) which is an elementary f u n c t i o n . than we are going to consider here. The log and
then what kind of extensions are required to o b t a i n
exponential cases w i l l be demonstrated here l a r g e l g
an e x t e n s i o n f i e l d which w i l l contain g ( x ] . The v i a examples.
answer that onlg new logarithmic extensions are
r e q u i r e d is a coneequencsof L l o u v i l l e ' s theorem, Our f i r s t e x a m p l e is a very easg problem and
o r i g i n a l l g proved in the 1830=s. To see the
is u s u a l l g tackled in the calculus using i n t e g r a t i o n
u n d e r l g l n g ideas in L i o u v i l l e ' e theorem in i t s
bg parts. Although we appear to spend much time on
c u r r e n t f o r m u l a t i o n we shall have to consider
t h i s problem, t h i s w i l l be rewarding since s i m i l a r ,
d i f f e r e n t i a t i o n p r o p e r t i e s of a l g e b r a t c a l l g
but much more d i f f i c u l t , problems g i l l be tackled
independent functions.
w i t h verg l i t t l e a d d i t i o n a l work.
Consider
Our f i r s t example is
d J~ log x dx
[g(x)e h ( x ] ] . g/e h + gh/e h _ (g/+gh,)e h
dx C l e a r l y log x E R(x, log(x]) The intsgrand is a
polwnomial in log (x) of degree 1. i f Me r e c a l l the
d i f f e r e n t i a t i o n of logs s a r i i e r , the d e r i v a t i v e of a
i f g(x] and eh(x) are a l g e b r a i c a l l g independent.
po~er of a log drops o f f at most 1. Hence the
Thus the d e r i v a t i v e of a m u l t i p l e of an e x p o n e n t i a l ,
i n t e g r a l , were i t to be elementarg,'would be of
when tke m u l t i p l e is independent of ~he e x p o n e n t i a l , degree 2 in l o g ( x ) a t most. Thus
is a m u l t i p l e of the same exponential, In other
words, i f Ne integrated a m u l t i p l e of an e x p o n e n t i a l ,
J" log(x) dx
Me Mould expect to see the exponential in the
i n t e g r a l , should the i n t e g r a l e x i s t in closed form.
= B2(x) Iog2(x] + 81(x) log x + B~(x)
Similarlg + ~ c i log Vi(x}
d B8, B1, B2 E R(x]
- - [g(x) Iognh(x)] Yl E R(x, log x]
dx c i - constants
gh'logn-l(x)
.g" Iognh + . . . . . . . . . . Note that the B i do not involve log x. Therefore
h them are in the smaller f i e l d R(x).

D i f f e r e n t i a t i n g the above f o r m a l l g and

The above would contain no logs I f g" = 0 ( i . e , g is c o l l e c t i n g c o e f f i c i e n t s of powers of l o g ( x ) , ue
a constant) and n - 1, but w i l l contain l o g s obtain
otherwise, assuming g(x) and log h(x) are
a l g e b r a i c a l l g independent. Thus one would expect no 2B2
new logarithms in the i n t e g r a l except i f the log x - B2f Iog2x + ( - - - + B I " ) log x
IKtsgrand contained a term which leads to a constant X
m u l t i p l e of a new log, In fact, when we c o n s i d e r a l l
the r e l e v a n t cases (including a l l a l g e b r a i c f u n c t i o n s •
B1 Vi "
such as square r o o t s ) , we f i n d that under c o n d i t i o n s
of a l g e b r a i c independence no new f u n c t i o n need appear + ( - - + Be') + c i - - -
x Vi

426
 Since the B i ' s are independent of log x, the which gets us close to the form we saw e a r l i e r .
c o e f f i c i e n t s of Iog2x, log x must be equal on both I n t e g r a t i n g again w e g e t
sides o f the equation,
-x + constant - b I log x + BB
T h e l c o s f f i c i e n t s of Iog2x o n b o t h sides of
the equation y i e l d + Z c i log Y I

I £ b I and a l l the c i are zerO, then B8 -

8 - B2"
- x + constant and we are done. Hence

Here B2 l e a constant, say b2, The c d e f f l c l e n t of J~ log x dx - x log x - x + constant

log x y i e l d s the f o l l o w i n g equation
Our second example le more d i f f i c u l t .
B2
1 • --. + BI". j log x
X
. . . . . dx
x+l
S u b s t i t u t i n g prior r e s u l t s
b2 The a n a l y s i s iis s i m i l a r and y i e l d s
/,log x
1 - ' + B1"
X . . . . . dx I B2(x) Iog2(x) + Bl(x} l o g ( x )
x+l

Now we seem to be faced with an anomaly. We s t a r t e d + B s ( x ) + Z c i Iog V i I x )

w i t h a s i n g l e i n t e g r a t i o n problem and noH have an
apparently mope complex d i f f e r e n t i a l equation. The B I E R(x)
s i t u a t i o n is not hopeless however. We can i n t e g r a t e V I £ R(x, log x), c i - constants
both sides using recursion for the l e f t - h a n d - s i d e and
use the f o l l o w i n g r e s u l t s foP each term on the
right-hand-side. The equations for the c o e f f i c i e n t s of powers of log x
aPe s i m i l a r , at f i r s t .
J'Bl"dX - B1 + constant,
8 l B2"
b2
f - - dx - b2 log x + c o n s t a n t , then B2 , b2, a c o n s t a n t
X
1 B2
The l a t t e r i n t e g r a l Is knogn because i t arose ...... + BI "
d i r e c t l y from d i f f e r e n t i a t i n g f o g x . Thus, we.get x+l x

x + constant - b 2 log x + B 1 I n t e g r a t i n g , ~e obtain

log (x+l) + constant - b 2 log x + B 2

Me are not Out of the goods yet since Me now have
o n l y one equation with two v a r i a b l e s b2, B1 . But
Now we must f i n d a constant b2 and a r a t i o n a l
here we can apply the constraints b2 " constant, B[ -
f u n c t i o n B1 such that the equatlon is s a t i s f i e d .
r a t i o n a l f u n c t i o n in x. Can there be a s o l u t i o n to
the l i n e a r equation above under these c o n s t r a i n t s ? This is impossible since log x and log (x+l) are
The answer is yes, i f b2 = 8, for then B1 • x + b l , a l g e b r a i c a l l y independent over the r a t i o n a l
SaM, and Ne are in good shape again. f u n c t i o n s . Hence the Integral can not be expressed
in terms of elementarg functions. In f a c t . the
S u b s t i t u t i n g these r e s u l t s i n t o the i n t e g r a l i e a d l l o g a r i t h m w h l c h Is a special ( I . e .
c o e f f i c i e n t of (log x)Swa get non-elementary) function. The proof of i t s
n o n i n t e g r a b i l i t g i n closed form is u s u a l l y f a i r l y
B1 Vl'" complex and s p e c i a l i z e d , a l t h o u g h q u i t e easy hera,

8 = - - + B 8" + ~ ci - - - Let us turn our a t t e n t i o n to e x p o n e n t i a l s

x Vi where the s i t u a t i o n le somewhat d i f f e r e n t .

x+bI Vi S Consider the Meil-kfl0wn i n t e g r a l

8 ..... + Be" + Z c I -- J~e x2 dx
x Vi
or
This function is in R(x,eX2). I t is a
bI Vi " polynomial in ex2 of degree 1. 0ue to the
d i f f e r e n t i a t i o n p r o p e r t i e s of exponentials, the
-1 - - - + B8" + ~ c i - - degree of the i n t e g r a l , i f i t e x i s t s as an elementary
x Vi f u n c t i o n , remains the same.

427
 I n fact, J' [x log (Iogx+eX2)]" dx

• . Sz(x). , Z cl log v I
The example above takes 8.9 seconds on the POP 1B/SO
B1 ~ Rlx) at fl.[.T.

Yl ~ R(x,eXZ), Cl " constants The algebraic case Of the Risch algorithm is,
ae we've already noted, much more complex than the
other cases. Excellent progress on Implementing t h i s
D i f f e r e n t i a t i n g , Me get case is being made byBarry Trager of M.[.T. [G]. in
p a r t i c u l a r , he canalready integrate algebraic
V I" functions whose integral Is purely algebraic such as
Sx3+2
• x2, (B1, + 2XBl)eX2+ Z c I - - -
f dx
VI

Hence our f i r s t equation ie

A survey of this and other approaches to the
1 - B1" + 2xB1 implementation of symbolic integration algorithee le
to be found In [5].

This looks exceedingly complex again. Note

that B1 l e a rational function. I f i t had a
non-constant denominator, the' degree of that References,
denominator would Increase in B1" and coutd not be
cancel led by the other terms. Hence B1 l e a
polynomial in x. Let I t s degree be n. Hence the 1. Rlech, R. H., "The Problem of Integration in
F i n i t e Terms", TPansactlons AMS 139 (May 1969),
degree of BI" = n - I ; degree of 2xB1 - n+t, and the
162-189.
degree of 1 - B . Since leading terms must cancel,_ ~ ,
~,,n+l. This i e a contradiction, since n>B. So J ex"Jx 2. Rlsch, R. H.. "On the Integration of Elementary
cannot be expressed in terms of elementar'g Functions which are b u i l t up using algebraic
functlone, as ie Mell known. operations," Rap. SP-2881-882, Systems
Development Corporation, Santa Monica, C a l i f .
Now consider ,r xeX2 dx. June 1868.
Our analysis proceeds as above. Me find, 3. RI ech, R. H., "Solution of the problem of
homever, that n+1-1. Hence n=O and B1 !e a constant. Integration i n f i n i t e terms," B u l l e t i n N1S (May
Substituting this information into 1978), G8S-688.

x - B1 • + 2xB1, 4. MACSYMAReference Manual, Version 8. Laboratory

for Computer Science. MIT, Cambridge, Ma~e.,
November 1975.
Me get B1 • I I 2 . Thus the integral le 112 • x2.
S. Moses, J , , "Symboi lc [ntegratlonz the Stormy
The problem / x2 ex2 le similar again. Here Decade," Communications ACM 14,8 (August 1971),
n - l . So B1 • ax+b. Substituting this i n t o the 548-5G8.
d i f f e r e n t i a l equation, ae find the following
relations 6. Trager, B., "Symbolic Integration of a class of
algebraic functions," M.S. Thesis, Dept. of
2a-1 Elec. Eng. and Camp. S c l . , M.].T. May, 1976.
b-B
a•B
Acknowledgement
Hence a contradiction. Thus the integral cannot be
f u l l y expressed in terms of elementary functions. This research was supported by the United
Yet i f you use the results of the integration one at States EnerggRessarch and Development Administration
a time we reduce the complexity of the non-integrable under contract E(11-1)-3878.
part. In p a r t i c u l a r , the integral becomes

1 1
- xex2 - - f sx2 dx
2 2

The l a t t e r t e r m Is now seen to be an e r r o r function.

•In fact, extensions of the Rlech procedure to handle
c l a s s e s of error functions as well as logarithms and
exponentials now exist in the MACSYI1Asystem [4,5].
This Implementation of the Rlsch algorithm can
quickly handle a l l the casesnoted .above ae Hell as
m o r e complex ones such as

428