Fraction Math - Answer to exercise

KBK: This exercise asked for a proof that the [quotient_rep] procedure in Fraction Math terminates after at most 41 iterations of the inner loop, and that at least one argument results in behavior that bad.


In case you hadn't noticed, [quotient_rep] operates by computing successive convergents to its parameter expressed as a regular continued fraction:

                                          1
                                         ------------------
  num = [ a_1, a_2, a_3, ... ] = a_1 +           1
                                          a_2 + -----------
                                                        1
                                                 a_3 + ----
                                                       .
                                                        .
                                                         .

The slowest convergence is when all the a_i's are 1, which gives

               1 + sqrt( 5 )
  num = phi = --------------
                    2

In this case the p_i values in the loop take on the Fibonacci numbers; the 42nd of these exceeds the default value of MAXINT. []