Transcendental Functions on Continued Fractions
Michael J. Collins · 2024
Read Transcendental Functions on Continued Fractions by Michael J. Collins (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-19929.txt.
Introduction
Michael Collins, writing alone, fixes arithmetic on continued fractions in a 2024 paper. Gosper's algorithm computes with these infinite fraction patterns and returns one as the answer. A direct build, though, loops forever on some inputs.
Collins presents a modified version and proves it dodges every infinite loop. He then marries fraction arithmetic to the spigot algorithm, which drips out digits one at a time. The pair can produce continued fraction forms of exponential, logarithmic, and trigonometric functions applied to fractions. All of it is implemented in Haskell. The work turns a classic but touchy algorithm into a dependable tool for exact computation.
Catalog record
| CREATOR | Michael J. Collins |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 43 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-19929
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Transcendental Functions on Continued Fractions Michael J. Collins Abstract Gosper developed an algorithm for performing arithmetic operations on continued fractions (CFs), getting a CF as the result. Straightforward implementation of the algorithm leads to infinite loops on some inputs. Here we present a modified version of the arithmetic algorithm and prove that it avoids all difficulties with infinite loops. We then combine CF arithmetic with the “spigot” algorithm to compute the CF expansions of exponential, logarithmic, and trigonometric functions of CFs. We have implemented these algorithms in Haskell. 1 Introduction A simple continued fraction 1 1 1 https://en.wikipedia.org/wiki/Simple_continued_fraction is a (possibly infinite) expression of the form a_{0}+\cfrac{1}{a_{1}+\cfrac{1}{a_{2}+\cfrac{1}{a_{3}+\cdots}}} where the terms a_{i} are integers. It can be written more compactly as [a_{0},a_{1},\cdots] 2 2 2 Many authors write this as [a_{0};a_{1},\cdots] . Here we consider only regular simple continued fractions, which means a_{i}\geq 1 when i>0 . The properties of continued fractions, and the motivations for studying them, are very well-known [ 12 ] , so here we only remind the reader of some notation we will use: • A quadratic irrational has a periodic CF expansion. We denote the periodic part by putting it in parentheses, i.e [1,(2,3)]=[1,2,3,2,3,2,3,\cdots] . • A rational number has a finite CF expansion [a_{0},a_{1},\cdots a_{k}] . It will be convenient to consider a finite CF as ending with an infinite term a_{k+1}=\infty , equating \frac{1}{\infty} with zero. Gosper (in an appendix to the famous HAKMEM report [ 1 ] ) developed an algorithm for performing arithmetic on two CFs, getting a CF as the result; the point of course is that we can do this entirely within the CF representation, making no use of floating-point operations. Straightforward implementation of the algorithm leads to infinite loops on some inputs 3 3 3 https://srossd.com/blog/2020/gosper-1/ (section 3.1 ). Here we present a modified version of the arithmetic algorithm, and prove that these modifications avoid infinite loops in the following sense: given any \varepsilon>0 , if the correct result is z=[z_{0},z_{1},\cdots] , our algorithm will eventually produce a finite CF [z_{0},\cdots z_{k-1},z^{\prime}_{k}] with proof that |z-[z_{0},\cdots z_{k-1},z^{\prime}_{k}]|<\varepsilon\ . We then extend the arithmetic algorithm with the techniques of the spigot algorithm for the digits of \pi [ 3 , 11 ] , to compute CF representations of e^{x},\log(x) , \cos(x) , and \arcsin(x) , where x is given as a CF. Of course, since we can do arithmetic, we could compute any n^{th} degree Taylor approximation of such functions to any degree of accuracy, but we go further; we develop an iterative algorithm that continually generates terms of the CF, using only as much of the series (and as many terms of x ) as are required to determine the next output term. We have implemented these algorithms in Haskell 4 4 4 https://github.com/mjcollins10/ContinuedFractions . 2 Arithmetic on One CF Before we describe how to add or multiply two CFs, we consider the simpler problem of operations combining a single CF with a rational number p/q . It is not in fact necessary to handle this as a special case, but considering this case separately allows us to present the core idea of the algorithm in a straightforward way. A few examples reveal there is no evident general pattern for transforming the CF terms of irrational x into the terms of px/q or x+p/q , even in the apparently simplest cases: \displaystyle\sqrt{7} \displaystyle= \displaystyle[2,(1,1,1,4)] \displaystyle\sqrt{7}/2 \displaystyle= \displaystyle[1,(3,10,3,2)] \displaystyle\sqrt{11} \displaystyle= \displaystyle[3,(3,6)] \displaystyle\sqrt{11}/2 \displaystyle= \displaystyle[1,(1,1,1,12,1,1,1,2)] \displaystyle\pi \displaystyle= \displaystyle[3,7,15,1,292,1,1,1,2,1,3,\cdots] \displaystyle\pi+1/2 \displaystyle= \displaystyle[3,1,1,1,3,1,3,4,73,6,3,3,2,1,3\cdots] As a motivating example for the general algorithm, we compute [y_{0},y_{1},y_{2}\cdots]=\frac{\pi}{2}=1.5707963267948966\cdots\ . Let \pi=[\pi_{0},\pi_{1},\cdots] (in general we use x_{i} for the i^{\mbox{th}} CF term of a real number x ). It will be convenient to have notation for the “tail” of a continued fraction, so let r_{i}=[\pi_{i+1},\pi_{i+2},\cdots]\ . Note that all r_{i}\geq 1 , and r_{i}=\pi_{i+1}+1/r_{i+1} . The fact that \pi_{0}=\lfloor\pi\rfloor=3 is enough to determine y_{0}=\lfloor\pi/2\rfloor=1 ; more precisely y=\frac{\pi}{2}=\frac{3+1/r_{0}}{2}=\frac{3r_{0}+1}{2r_{0}}=1+\frac{r_{0}+1}{2r_{0}}=1+\frac{1}{[y_{1},y_{2},\cdots]}\ . Now we have to get y_{1} from [y_{1},y_{2},\cdots]=\frac{2r_{0}}{r_{0}+1}\ . The mere fact that r_{0}>1 is enough to tell us that \lfloor\frac{2r_{0}}{r_{0}+1}\rfloor=1 , so we obtain y_{1}=1 and continue [y_{1},y_{2},\cdots]=1+\frac{r_{0}-1}{r_{0}+1}=y_{1}+\frac{1}{[y_{2},y_{3}\cdots]} [y_{2},\cdots]=\frac{r_{0}+1}{r_{0}-1}\ . Now the floor of \frac{r_{0}+1}{r_{0}-1} ranges from one to infinity as r_{0} ranges from one to infinity, so we need to make use of \pi_{1}=7 ; we substitute r_{0}=7+1/r_{1} to get [y_{2},\cdots]=\frac{8+1/r_{1}}{6+1/r_{1}}=\frac{8r_{1}+1}{6r_{1}+1}=1+\frac{2r_{1}}{6r_{1}+1}=1+\frac{1}{[y_{3},\cdots]}\ . Thus y_{2}=1 . We also get y_{3}=3 from [y_{3},\cdots]=\frac{6r_{1}+1}{2r_{1}}=3+\frac{1}{2r_{1}}=3+\frac{1}{[y_{4},\cdots]}\ . Going further will require substituting r_{1}=15+1/r_{2} into [y_{4},\cdots]=2r_{1} . It is now clear that we will generate terms of y by repeatedly determining the integer part (i.e. floor) of expressions of the form \frac{px+q}{rx+s} (1) where x>1 , the coefficients are integral, and the continued fraction expansion of x is known. Functions of this form are called homographic . We will identify a homographic function with the matrix M=\left(\begin{smallmatrix}p&q\\ r&s\end{smallmatrix}\right) and may write ( 1 ) as M(x) . We can assume without loss of generality that the determinant ad-bc is nonzero, and \gcd(a,b,c,d)=1 . If -s/r\leq 1 then the denominator cannot be zero, and M(x) is between the min and max of \{p/r,(p+q)/(r+s)\} ; if \left\lfloor\frac{p}{r}\right\rfloor=\left\lfloor\frac{p+q}{r+s}\right\rfloor then this common value is \lfloor M(x)\rfloor ; we say that M is unambiguous . We always have M([x_{i},x_{i+1},\cdots])=[y_{j},y_{j+1},\cdots] (2) where [x_{i},x_{i+1},\cdots] is the unread part of the input and [y_{0},\cdots y_{j-1}] is the output prefix already computed. We define two transformations on M which preserve ( 2 ). When M is ambiguous, we do not yet have enough information to determine y_{j} , and must \emph{ingest} the next term of x . If this term is x_{i}=k we make the substitution x\leftarrow k+1/x , leading to the definition \mbox{ingest}(k,\left(\begin{smallmatrix}p&q\\ r&s\end{smallmatrix}\right))=\begin{pmatrix}q+kp&p\\ s+kr&r\end{pmatrix}\ . When M is unambiguous with k=\left\lfloor\frac{p}{r}\right\rfloor , we can produce the next output term y_{j}=k ; the rest of the output, [y_{j+1},y_{j+2},\cdots] , is the continued fraction expansion of \frac{1}{\frac{px+q}{rx+s}-k}=\frac{rx+s}{(p-kr)x+(q-ks)} so we define \mbox{produce}(k,\left(\begin{smallmatrix}p&q\\ r&s\end{smallmatrix}\right))=\begin{pmatrix}r&s\\ p-kr&q-ks\end{pmatrix}\ . Note that these two transformations do not change the absolute value of the determinant of M . If we started with rational x , we will eventually reach x_{i}=\infty ; ingesting infinity returns the limit {\left(\begin{smallmatrix}0&p\\ 0&r\end{smallmatrix}\right)} . This is the constant function at the rational number p/r , so there will never be any need to ingest the (nonexistent) subsequent terms of x . If we proceed as in the examples above, we will compute the CF representation of p/r as the last part of the finite expansion of y , ending with a production that subtracts the final term y_{k} from the expression \frac{y_{k}}{1} ; this leads to M=\left(\begin{smallmatrix}0&1\\ 0&0\end{smallmatrix}\right) , which we may read as infinity. {input x=[x_{0},x_{1},\cdots] } {input M=\left(\begin{smallmatrix}p&q\\ r&s\end{smallmatrix}\right) } {output y : CF expansion of M(x) } i\leftarrow 0 {index of the next term of x we will read} j\leftarrow 0 {index of the next term of y we will generate} M\leftarrow\mbox{ingest}(x_{0},M) {updating M updates variables p,q,r,s } i\leftarrow 1 while M\neq\left(\begin{smallmatrix}0&1\\ 0&0\end{smallmatrix}\right) do while M is ambiguous do M\leftarrow\mbox{ingest}(x_{i},M) i\leftarrow i+1 end while y_{j}\leftarrow\left\lfloor\frac{p}{r}\right\rfloor M\leftarrow\mbox{produce}(y_{j},M) j\leftarrow j+1 end while Figure 1: Algorithm for arithmetic on a CF and a rational number So now we have an algorithm for producing the CF expansion [y_{0},y_{1},\cdots] of \frac{px+q}{rx+s} , assuming the expansion of x is known. To compute x/k we would start with