Faster arithmetic with finite continued fractions

Question

I was curious about different representations of rational numbers and came across the finite continued fraction (see wp:Finite_continued_fractions ).

Note: I will refer to traditional rational representation with two integers as fractional representation and to reduced fractions ($gcd(n,d)=1$, where $n$ is the numerator, and $d$ is the denominator) of this sort as reduced fractional representation.

Bellow I will make some comparisons between continued fractions and the other representations.

Advantages

• Linear time ordering, for example x<y (vs. $O(M(|n|+|d|))$ for fractional representation representation).

Disadvantages

• Arithmetic using Gosper's algorithms for continued fraction arithmetic seems to grow at a much worse rate than the fractional representation.

Question

• In reading Big Integers and Complexity Issues in Exact Real Arithmetic (view), Heckmann describes Linear Fractional Transformations (LFTs). They look very similar to Gosper's algorithms for arithmetic on continued fractions. Are they the same? How are they different?

Edit: some links to continued fraction arithmetic

• Pretty good (slideshow) but missing some examples at the end, also source codes in C
• http://perl.plover.com/yak/cftalk/INFO/gosper.txt By Bill Gosper.
• http://www.inwap.com/pdp10/hbaker/hakmem/cf.html
• Example of cf arithmetic with visualizations: http://paul-mccarthy.us/Cfrac/CF_Arithmetic.htm

Answer 1

From Möbius transformation:

Möbius transformations are named in honor of August Ferdinand Möbius; they are also variously named homographies, homographic transformations, linear fractional transformations, bilinear transformations, or fractional linear transformations.

So yes, they are the same (Gosper discusses homographic transformations IIRC).