[boost] Rational comparison w/ continued fractions

From: Daryle Walker (darylew_at_[hidden])
Date: 2005-12-16 22:10:50

I interrupted some thread about how Wave processed numbers it read.  I
mentioned using bignums someday.  The thread drifted to bignum
representations, including "exact reals."  One of the exact-real library web
sites mentioned continued fractions, which lead me to the HAKMEM paper.  You
can find out more at <http://en.wikipedia.org/wiki/HACKMEM>.

I was thinking of creating a continued fraction class for us, but then I saw
a note about how continued fraction comparison is easier than regular
fraction comparison.  More importantly, c.f. comparison is just list entry
checking, no arithmetic operations.  Conversion from r.f. to c.f. involves
only division and remainders.  These facts combine to make a r.f. comparison
that doesn't need multiplications, and therefore avoids overflow.

Continued fractions have a form like:

    p0 + q0 / (p1 + q1 / (p2 + q2 / ... ))

where all the p's and q's are integers.  We usually simplify the
representation by factoring out all the q's to 1's:

    r0 + 1 / (r1 + 1 / (r2 + 1 / ... ))

(The p's change values, except for p0, because of the re-factoring.)  We can
type out these simplified fractions easily with "[r0; r1, r2, ...]".

Rational and irrational numbers map to finite- and infinite-length fraction
lists, respectively.  Irrational numbers have a unique representation;
rational numbers are unique to two forms, where the minor form reduces the
last number by 1 and appends a 1 to the list.

    [x0; x1, x2, ..., xn]  ==  [x0; x1, x2, ..., (xn - 1), 1]

Continued fractions are typically difficult to manipulate, but two
operations are very easy.

1.  Reciprocal
    [0; x1, x2, x3, ...]  <->  [x1; x2, x3, ...]

2.  Comparison of two values (as represented by their lists)
    a.  Make sure to normalize the fraction
        1.  Convert away from the trailing-1 minor form (if rational)
        2.  Remove any interior zeros with
            [... x, 0, y, ...]  <->  [... (x + y) ...]
            But note that if x == -y, you'll create another zero and
            you'll have to do another round.
        3.  Keep the sign consistent, make sure every integer in the
            series is non-negative or non-positive.  (Keeping the
            previous rule in mind, only the first list entry can be a
            zero.)  I don't know how to correct lists that violate this.

        I don't think that normal conversion from a numerator &
        denominator pair will cause these problems; a conversion
        will create a list that's already normalized.  The conversion
        involves applying Euclid's GCD algorithm, which needs the
        "%" operator, which is iffy for negative values, so it would
        be better to take the absolute values, track the signs
        separately, and flip the result as appropriate.  (Lists with
        these problems could occur if the list is generated from a
        rule formula.)

    b.  (I'm assuming that you're using absolute values.)  If every
        element of the two numbers' lists are equal, then the numbers
        are equal.  Otherwise stop at the pair of list entries that
        are different, using infinity as the place-holder if one list
        is shorter than another.  For that list index K, if K mod 2 is
        the same as the index for the first (i.e. the whole number
        part) entry's mod-2, then the less/greater-than status of the
        two entries is the same as the lists' status, else the statuses
        are reversed.

Example 1:  7/6 (i.e. 1+1/6) vs. 1/2
    7/6: [1; 6]
    1/2: [0; 2]
    Difference at first entry
    1 > 0 with odd# entry; so 7/6 > 1/2

Example 2:  1/4 vs. 1/3
    1/4: [0; 4]
    1/3: [0; 3]
    Difference at second entry
    4 > 3 with even# entry; so 1/4 < 1/3

Example 3:
    47/21: [2; 4, 5]
    9/4:   [2; 4]
    Difference at third entry
    5 < Inf with odd# entry; so 47/21 < 9/4

Normal decimal fractions have even faster comparisons, but forming enough
digits is harder, especially if they repeat.

I'll try to come up with an actual improved member function for
boost::rational in few days.

-- 
Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT hotmail DOT com