11
$\begingroup$

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

Edit: some links to continued fraction arithmetic

$\endgroup$
10
  • $\begingroup$ What's missing at the end of the slideshow? $\endgroup$
    – MJD
    Nov 30, 2012 at 3:08
  • $\begingroup$ @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$. $\endgroup$
    – Realz Slaw
    Nov 30, 2012 at 3:24
  • $\begingroup$ 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.) $\endgroup$
    – MJD
    Nov 30, 2012 at 3:37
  • $\begingroup$ @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 ;). $\endgroup$
    – Realz Slaw
    Nov 30, 2012 at 3:39
  • $\begingroup$ 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. $\endgroup$
    – MJD
    Nov 30, 2012 at 3:40

2 Answers 2

Reset to default
6
$\begingroup$

There are many advantages to representing numbers in their continued fraction form. Calculations can be performed, using Gosper's algorithm, with as much accuracy as you'd like.

Heckman's LFT approach is the same as evaluating with Wallis' fundamental recurrence Formula. The linear fractional transform representation can be easier to understand, but the results are identical. Since all the transforms are affine there's some extra overhead with the LFT approach.

Many common mathematical constants, like $ \phi = 1 + {{1}\over{1+{{1}\over{1+\ddots}}}}$, $\pi = {4\over{1+{1\over{3+{4\over{5+\ddots}}}}}} $,$e={2+{1\over{1+{1\over{2+}}}}}$ have exact representation as continued fractions. This means exact calculations (as much precision as you'd like) of many values can be performed. In fact any quadratic surd (solution to a quadratic equations $ax^2+bx+c=0$) will have a repeating continued fraction, and conversly any repeating continued fraction represents a quadratic surd. So any quadratic solution can be represented exactly.

I've been developing a computational package based on these algorithms for about the last 5 years. The same algorithms that allow mobius and tensor transforms of continued fractions also work for polynomials, allowing manipulation of complex functions. These Euler continued functions have far superior convergence properties in the complex plane.

Note: The disadvantage you mentioned need not be true. Remember with Gosper's algorithm you're 'emiting' values that reduce the size of the integers used in calculations (analogous to reductions in Euclids Algorithm). No such reduction in size occurs with straight fraction arithmetic.

$\endgroup$
2
$\begingroup$

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).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .