\documentstyle[11pt,reduce]{article}
\title{{\bf Rational Approximations Package for REDUCE}}
\author{Lisa Temme\\Wolfram Koepf\\ e-mail: {\tt koepf@zib.de}}
\date{August 1995 : ZIB Berlin}
\begin{document}
\maketitle

\section{Periodic Decimal Representation}

The division of one integer by another often results in
a period in the decimal part. The {\tt rational2periodic}
function in this package can recognise and represent
such an answer in a periodic representation. The inverse
function, {\tt periodic2rational}, can also convert a
periodic representation back to a rational number.\\


\begin{tabbing}
{\bf \underline{Periodic Representation of a Rational Number}}\\ \\


{\bf SYNTAX:} \hspace{3mm} 
     \= {\tt rational2periodic(n);}\\ \\

{\bf INPUT:}  
     \> {\tt n} \hspace{3mm} is a rational number\\ \\

{\bf RESULT:}
     \> {\tt periodic(\{a,b\} , \{c1,...,cn\})} \\ \\
     \> where  {\tt a/b} is the non-periodic part\\
     \> and {\tt c1,...,cn} are the digits of the periodic part.\\ \\


{\bf EXAMPLE:}
    \> $59/70$ written as $0.8\overline{428571}$\\
    \>  {\tt 1: rational2periodic(59/70);}\\ \\
    \> {\tt periodic(\{8,10\},\{4,2,8,5,7,1\})}\\ \\


{\bf \underline{Rational Number of a Periodic Representation}}\\ \\


{\bf SYNTAX:}
     \> {\tt periodic2rational(periodic(\{a,b\},\{c1,...,cn\}))}\\
     \> {\tt periodic2rational(\{a,b\},\{c1,...,cn\})}\\ \\


{\bf INPUT:}
     \> \hspace{15mm} {\tt a} \hspace{3mm}\= is an integer\\
     \> \hspace{15mm} {\tt b}             \> is $1$, $-1$ or an 
                                             integer multiple of $10$\\
     \> {\tt c1,...,cn}               \> is a list of positive digits\\ \\

{\bf RESULT:}
     \> A rational number.\\ \\

{\bf EXAMPLE:}
    \> $0.8\overline{428571}$ written as $59/70$ \\
    \> {\tt 2: periodic2rational(periodic(\{8,10\},\{4,2,8,5,7,1\}));}
\\ \\
    \> \hspace{1mm} {\tt 59}\\
    \> {\tt ----}\\
    \> \hspace{1mm} {\tt 70}\\ \\
    \> {\tt 3: periodic2rational(\{8,10\},\{4,2,8,5,7,1\});}
\\ \\
    \> \hspace{1mm} {\tt 59}\\
    \> {\tt ----}\\
    \> \hspace{1mm} {\tt 70}
\end{tabbing}

Note that if {\tt a} is zero, {\tt b} will indicate how many places
after the decimal point that the period occurs. Note also that if the answer
is negative then this will be indicated by the sign of {\tt a} (unless
{\tt a} is zero in which case it is indicated by the sign of {\tt b}).
\\ \\


{\bf ERROR MESSAGE}\\

{\tt ***** operator to be used in off rounded mode}\\

The periodicity of a function can only be recognised in
the {\tt off rounded} mode. This is also true for the inverse
procedure.\\ \\





{\large\bf EXAMPLES}\\
\begin{verbatim}
4: rational2periodic(1/3);

periodic({0,1},{3})

5: periodic2rational(ws);

 1
---
 3

6: periodic2rational({0,1},{3});

 1
---
 3

7: rational2periodic(-1/6);

periodic({-1,10},{6})

8: periodic2rational(ws);

  - 1
------
  6

9: rational2periodic(6/17);

periodic({0,1},{3,5,2,9,4,1,1,7,6,4,7,0,5,8,8,2})

10: periodic2rational(ws);

 6
----
 17

11: rational2periodic(352673/3124);

periodic({11289,100},{1,4,8,5,2,7,5,2,8,8,0,9,2,1,8,9,5,0,0,6,
                      4,0,2,0,4,8,6,5,5,5,6,9,7,8,2,3,3,0,3,4,
                      5,7,1,0,6,2,7,4,0,0,7,6,8,2,4,5,8,3,8,6,
                      6,8,3,7,3,8,7,9,6,4})

12: periodic2rational(ws);

 352673
--------
  3124

\end{verbatim}
%\newpage
\section{Continued Fractions}


A continued fraction (see ~\cite{PA} \S 4.2) has the general form
{\Large
\[b_0 + \frac{a_1}{b_1 +
         \frac{a_2}{b_2+
          \frac{a_3}{b_3 + \ldots
        }}}
\;.\]
}

A more compact way of writing this is as
\[b_0 + \frac{a_1|}{|b_1} + \frac{a_2|}{|b_2} + \frac{a_3|}{|b_3} + \ldots\,.\]
\\

This is represented in {\small REDUCE} as
\[{\tt
   contfrac({\sl Rational\hspace{2mm} approximant},
                \{b0, \{a1,b1\}, \{a2,b2\},.....\})
}\]

\begin{tabbing}
\\
{\bf SYNTAX:} \hspace{5mm} 
\= {\tt cfrac(number);}\\
\> {\tt cfrac(number,length);}\\
\> {\tt cfrac(f, var);}\\
\> {\tt cfrac(f, var, length);}\\ \\

{\bf INPUT:}
\> {\tt number} \hspace{3mm} \= is any real number\\
\> {\tt f}                   \> is a function\\
\> {\tt var}                 \> is the function variable\\
%\> {\tt length}              \> is the upper bound of the number\\ 
%\>                           \> of \{ai,bi\} returned (optional)\\ \\
\end{tabbing}

{\bf Optional Argument: {\tt length}}\\

The {\tt length} argument is optional. 
For an NON-RATIONAL function input the {\tt length} argument specifies
the number of ordered pairs, $\{a_i,b_i\}$, to be 
returned. It's default value is five.
For a RATIONAL function input the
{\tt length} argument can only truncate the answer, it cannot
return additional pairs even if the precision is increased.
The default value is the complete continued fraction of the
rational input. For a NUMBER input the default value is 
dependent on the precision of the session, and the
{\tt length} argument will only take effect if it has a smaller
value than that of the number of ordered pairs which the default
value would return.\\ \\



%\newpage
\large{{\bf EXAMPLES}}\\ \\
\begin{verbatim}
13: cfrac(23.696);

          2962
contfrac(------,{23,{1,1},{1,2},{1,3},{1,2},{1,5}})
          125


14: cfrac(23.696,3);

          237
contfrac(-----,{23,{1,1},{1,2},{1,3}})
          10

15: cfrac pi;


          1146408
contfrac(---------,
          364913

         {3,{1,7},{1,15},{1,1},{1,292},{1,1},{1,1},{1,1},{1,2},{1,1}})

16: cfrac(pi,3);

          355
contfrac(-----,{3,{1,7},{1,15},{1,1}})
          113

17: cfrac(pi*e*sqrt(2),4);

          10978
contfrac(-------,{12,{1,12},{1,1},{1,68},{1,1}})
           909

18: cfrac((x+2/3)^2/(6*x-5),x,1);

             2
          9*x  + 12*x + 4    6*x + 13      24*x - 20
contfrac(-----------------,{----------,{1,-----------}})
             54*x - 45          36             9

19: cfrac((x+2/3)^2/(6*x-5),x,10);

             2
          9*x  + 12*x + 4    6*x + 13      24*x - 20
contfrac(-----------------,{----------,{1,-----------}})
             54*x - 45          36             9


20: cfrac(e^x,x);



           3      2
          x  + 9*x  + 36*x + 60
contfrac(-----------------------,{1,{x,1},{ - x,2},{x,3},{ - x,2},{x,5}})
               2
            3*x  - 24*x + 60

21: cfrac(x^2/(x-1)*e^x,x);

           6      4    2
          x  + 3*x  + x
contfrac(----------------,{0,
             4    2
          3*x  - x  - 1

                 2            2       2       2       2
            { - x ,1}, { - 2*x ,1}, {x ,1}, {x ,1}, {x ,1}})

22: cfrac(x^2/(x-1)*e^x,x,2);

             2
             x              2           2
contfrac(----------,{0,{ - x ,1},{ - 2*x ,1}})
             2
          2*x  - 1

\end{verbatim}

%\newpage
\section{Pad\'{e} Approximation}


The Pad\'{e} approximant represents a function by the ratio of two 
polynomials. The coefficients of the powers occuring in the polynomials 
are determined by the coefficients in the Taylor series
expansion of the function (see ~\cite{PA}). Given a power series
\[ f(x) = c_0 + c_1 (x-h) + c_2 (x-h)^2 \ldots \]
and the degree of numerator, $n$, and of the denominator, $d$,
the {\tt pade} function finds the unique coefficients 
$a_i,\, b_i$ in the Pad\'{e} approximant 
\[ \frac{a_0+a_1 x+ \cdots + a_n x^n}{b_0+b_1 x+ \cdots + b_d x^d} \; .\]
\\ \\

\begin{tabbing}
{\bf SYNTAX:} \hspace{5mm}\= {\tt pade(f, x, h, n, d);}\\ \\

{\bf INPUT:}
\> {\tt f} \hspace{3mm} \= is the funtion to be approximated\\
\> {\tt x}             \> is the function variable\\
\> {\tt h}             \> is the point at which the approximation is\\ 
\>                     \> evaluated\\
\> {\tt n}             \> is the (specified) degree of the numerator\\
\> {\tt d}             \> is the (specified) degree of the denominator\\ \\


{\bf RESULT:} 
\> Pad\a'{e} Approximant, ie. a rational function.\\ \\
\end{tabbing}


{\bf ERROR MESSAGES}\\

{\tt ***** not yet implemented}\\

The Taylor series expansion for the function, f, has not yet
been implemented in the {\small REDUCE} Taylor Package.\\ \\


{\tt ***** no Pade Approximation exists}\\

A Pad\'{e} Approximant of this function does not exist.\\ \\

\newpage
{\tt ***** Pade Approximation of this order does not exist}\\

A Pad\'{e} Approximant of this order (ie. the specified
numerator and denominator orders) does not exist but one
of a different order may exist.\\ \\


\large{{\bf EXAMPLES}}

\begin{verbatim}

23: pade(sin(x),x,0,3,3);

          2
 x*( - 7*x  + 60)
------------------
       2
   3*(x  + 20)

24: pade(tanh(x),x,0,5,5);

     4        2
 x*(x  + 105*x  + 945)
-----------------------
      4       2
 15*(x  + 28*x  + 63)

25: pade(atan(x),x,0,5,5);

        4        2
 x*(64*x  + 735*x  + 945)
--------------------------
         4       2
 15*(15*x  + 70*x  + 63)

26: pade(exp(1/x),x,0,5,5);

***** no Pade Approximation exists

27: pade(factorial(x),x,1,3,3);

***** not yet implemented

28: pade(asech(x),x,0,3,3);

            2                        2                 2
- 3*log(x)*x  + 8*log(x) + 3*log(2)*x  - 8*log(2) + 2*x
--------------------------------------------------------
                          2
                       3*x  - 8

29: taylor(ws-asech(x),x,0,10);

               11  
log(x)*(0 + O(x  ))

     13    6     43    8    1611    10      11
 + (-----*x  + ------*x  + -------*x   + O(x  ))
     768        2048        81920

30: pade(sin(x)/x^2,x,0,10,0);

***** Pade Approximation of this order does not exist

31:  pade(sin(x)/x^2,x,0,10,2);

     10        8         6           4            2
( - x   + 110*x  - 7920*x  + 332640*x  - 6652800*x

  + 39916800)/(39916800*x)

32: pade(exp(x),x,0,10,10);



  10        9         8           7            6
(x   + 110*x  + 5940*x  + 205920*x  + 5045040*x

              5               4                3
  + 90810720*x  + 1210809600*x  + 11762150400*x

                 2
  + 79394515200*x  + 335221286400*x + 670442572800)/

      10        9         8           7            6
    (x   - 110*x  + 5940*x  - 205920*x  + 5045040*x

                     5               4
         - 90810720*x  + 1210809600*x 

                        3               2
         - 11762150400*x + 79394515200*x  

         - 335221286400*x + 670442572800)

33: pade(sin(sqrt(x)),x,0,3,3);
        
(sqrt(x)*
            3            2
  (56447*x  - 4851504*x  + 132113520*x - 885487680))\

              3         2
    (7*(179*x  - 7200*x  - 2209680*x - 126498240))
\end{verbatim}


\begin{thebibliography}{9}
\bibitem{PA} Baker(Jr.), George A. and Graves-Morris, Peter:\\
{\it Pad\'{e} Approximants, Part I: Basic Theory},
(Encyclopedia of mathematics and its applications, Vol 13,
Section: Mathematics of physics),
Addison-Wesley Publishing Company, Reading, Massachusetts, 1981.
\end{thebibliography}

\end{document}
