# Continued fraction/Arithmetic

By popular demand, see Talk:Continued fraction#creating_a_continued_fraction and Talk:Continued fraction#Arithmetics.3F.3F, or be careful what you ask for.

G(matrix NG, Continued Fraction N1, Continued Fraction N2)

which will perform basic mathmatical operations on continued fractions.

Mathworld informs me:

Gosper has invented an algorithm for performing analytic addition, subtraction, multiplication, and division using continued fractions. It requires keeping track of eight integers which are conceptually arranged at the polyhedron vertices of a cube. Although this algorithm has not appeared in print, similar algorithms have been constructed by Vuillemin (1987) and Liardet and Stambul (1998).
Gosper's algorithm for computing the continued fraction for (ax+b)/(cx+d) from the continued fraction for x is described by Gosper (1972), Knuth (1998, Exercise 4.5.3.15, pp. 360 and 601), and Fowler (1999). (In line 9 of Knuth's solution, X_k<-|_A/C_| should be replaced by X_k<-min(|_A/C_|,|_(A+B)/(C+D)_|).) Gosper (1972) and Knuth (1981) also mention the bivariate case (axy+bx+cy+d)/(Axy+Bx+Cy+D).

My description follows part of Gosper reproduced on perl.plover.com. This document is text and unnumbered, you may wish to start by searching for "Addition, Multiplication, etc. of Two Continued Fractions" prior to reading the whole thing.

perl.plover.com also includes a series of slides as a class on continued fractions. The example [1;5,2] + 1/2 in G(matrix NG, Contined Fraction_N) is worked through in this class.

For these tasks continued fractions will be of the form:

${\displaystyle a_{0}+{\cfrac {1}{a_{1}+{\cfrac {1}{a_{2}+{\cfrac {1}{a_{3}+\ddots }}}}}}}$

so each may be described by the notation [${\displaystyle a_{0};a_{1},a_{2},...,a_{n}}$]

## Continued fraction/Arithmetic/Construct from rational number

During these tasks I shall use the function described in this task to create continued fractions from rational numbers.

## Matrix NG

Consider a matrix NG:

${\displaystyle {\begin{bmatrix}a_{12}&a_{1}&a_{2}&a\\b_{12}&b_{1}&b_{2}&b\end{bmatrix}}}$

and a function ${\displaystyle G(\mathrm {matrix} }$ ${\displaystyle {\mathit {NG}},\mathrm {Number} }$ ${\displaystyle N_{1},\mathrm {Number} }$ ${\displaystyle N_{2})}$ which returns:

${\displaystyle {\frac {a_{12}\times N_{1}\times N_{2}+a_{1}\times N_{1}+a_{2}\times N_{2}+a}{b_{12}\times N_{1}\times N_{2}+b_{1}\times N_{1}+a_{2}\times N_{2}+b}}}$

### Basic identities

${\displaystyle {\mathit {NG}}={\begin{bmatrix}0&1&1&0\\0&0&0&1\end{bmatrix}}}$

computes ${\displaystyle N_{1}+N_{2}}$

${\displaystyle {\mathit {NG}}={\begin{bmatrix}0&1&-1&0\\0&0&0&1\end{bmatrix}}}$

computes ${\displaystyle N_{1}-N_{2}}$

${\displaystyle {\mathit {NG}}={\begin{bmatrix}1&0&0&0\\0&0&0&1\end{bmatrix}}}$

computes ${\displaystyle N_{1}\times N_{2}}$

${\displaystyle {\mathit {NG}}={\begin{bmatrix}0&1&0&0\\0&0&1&0\end{bmatrix}}}$

computes ${\displaystyle N_{1}/N_{2}}$

### Compound operations

${\displaystyle {\mathit {NG}}={\begin{bmatrix}21&-15&28&-20\\0&0&0&1\end{bmatrix}}}$

calculates (${\displaystyle 3\times N_{1}+4)\times (7\times N_{2}-5)}$

Note that with ${\displaystyle N_{1}=22}$, ${\displaystyle N_{2}=7}$, and

${\displaystyle {\mathit {NG}}={\begin{bmatrix}0&1&0&0\\0&0&1&0\end{bmatrix}}}$

I could define the solution to be ${\displaystyle N_{1}=1}$, ${\displaystyle N_{2}=1}$ and

${\displaystyle {\mathit {NG}}={\begin{bmatrix}0&0&0&22\\0&0&0&7\end{bmatrix}}}$

So I can define arithmetic as operations on this matrix which make ${\displaystyle a_{12}}$, ${\displaystyle a_{1}}$, ${\displaystyle a_{2}}$, ${\displaystyle b_{12}}$, ${\displaystyle b_{1}}$, ${\displaystyle b_{2}}$ zero and read the answer from ${\displaystyle a}$ and ${\displaystyle b}$. This is more interesting when ${\displaystyle N_{1}}$ and ${\displaystyle N_{2}}$ are continued fractions, which is the subject of the following tasks.

## G(matrix NG, Contined Fraction N)

Here we perform basic mathematical operations on a single continued fraction.

## The bivarate solution G(matrix NG, Continued Fraction N1, Continued Fraction N2)

Here we perform basic mathematical operations on two continued fractions.

• Compare two continued fractions
• Sqrt of a continued fraction