# Faster arithmetic with finite continued fractions

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.

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

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

### Question

Edit: some links to continued fraction arithmetic

-
What's missing at the end of the slideshow? –  MJD Nov 30 '12 at 3:08
@MJD I think I wanted a written out example of the $\left\langle \frac {a \space b \space c \space d}{e \space f \space g \space h} \right\rangle$ like he had for $\left\langle \frac {a \space b}{c \space d} \right\rangle$. –  Realz Slaw Nov 30 '12 at 3:24
Try working one out yourself. It's very similar to the $\left\langle{a \> b \atop c \> d}\right\rangle$ case. If you get stuck, you can send me mail. (I'm the author of the slides.) –  MJD Nov 30 '12 at 3:37
@MJD oh wow, you are the author, I am honored you commented. I actually have a followup to this question, about how the mass absorption/emmision works in Heckmann's paper. Perhaps you can make a slideshow on that next ;). –  Realz Slaw Nov 30 '12 at 3:39
Or you could trace the operation of the C code, which implements the $\left\langle{a\>b\>c\>d\atop e\>f\>g\>h}\right\rangle$ algorithm. –  MJD Nov 30 '12 at 3:40