Continued fraction/Arithmetic: Difference between revisions
m
→The bivarate solution G(matrix NG, Continued Fraction N1, Continued Fraction N2)
No edit summary |
|||
| (11 intermediate revisions by 3 users not shown) | |||
Line 4:
:G(matrix NG, Continued Fraction N<sub>1</sub>, Continued Fraction N<sub>2</sub>)
which will perform basic mathmatical operations on continued fractions.
[http://mathworld.wolfram.com/ContinuedFraction.html 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 [http://perl.plover.com/yak/cftalk/INFO/gosper.txt 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.
[http://perl.plover.com/classes/cftalk/TALK/slide001.html perl.plover.com] also includes a series of slides as a class on continued fractions. The example [1;5,2] + 1/2 in [[Continued fraction/Arithmetic/G(matrix NG, Contined Fraction N) | G(matrix NG, Contined Fraction_N)]] is worked through in this class.
For these tasks continued fractions will be of the form:
Line 9 ⟶ 18:
so each may be described by the notation [<math>a_0 ; a_1, a_2, ..., a_n</math>]
==[[Continued fraction
During these tasks I
==Matrix NG==
Consider a matrix NG:
: <math>\begin{bmatrix}
\end{bmatrix}
</math>
and a function <math>G(\mathrm{matrix}</math> <math>\mathit{NG}, \mathrm{Number
which returns:
: <math>\frac{
===Basic identities===
: <math>\mathit{NG} = \begin{bmatrix}
0 & 1 & 1 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}</math
computes <math>N_1 + N_2</math>
:<math>\mathit{NG} = \begin{bmatrix}
0 & 1 & -1 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}</math
: <math>\mathit{NG} = \begin{bmatrix}▼
1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}</math
: <math>\mathit{NG} = \begin{bmatrix}
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0
\end{bmatrix}</math
===Compound operations===
: <math>\mathit{NG} = \begin{bmatrix}
21 & -15 & 28 & -20 \\
0 & 0 & 0 & 1
\end{bmatrix}</math>
calculates (<math>3\times N_1 + 4) \times (7\times N_2 - 5)</math>
:Note that with N<sub>1</sub> = 22, N<sub>2</sub> = 7, and NG = :▼
▲: <math>\begin{bmatrix}
: <math>\mathit{NG} = \begin{bmatrix}
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0
\end{bmatrix}</math>
: <math>\mathit{NG} = \begin{bmatrix}
0 & 0 & 0 & 22 \\
0 & 0 & 0 & 7
\end{bmatrix}</math>
Here we perform basic mathematical operations on a single continued fraction.
Here we perform basic mathematical operations on two continued fractions.
* Compare two continued fractions
* Sqrt of a continued fraction
| |||