DEC2FRAC for the HP 48SX (faster and more complete than ->Q)
Improved Decimal-to-Fraction, by Joseph K. Horn, 21 March 1991
(Not as short or fast as D2F, but this one's readable.)


THE PROBLEM: The HP 48SX (->Q function) and HP 32SII (with maximum denominator
  set) both miss many solutions, and slowly recalculate the summations for each
  term rather than using a fast recursion formula to get each term from the
  last two.


THE SOLUTION: This new algorithm finds the very best solution, very quickly.


ALGORITHM: Continued Fractions by fast recursion formula, then make a single
  calculated jump backwards to the best possible fraction before the specified
  maximum denominator.

Copyright (c) 1991 by Joseph K. Horn.  May be used freely in any application
  that has no documentation.  May be in a documented application if the above
  author is credited.


INPUT:

2: Decimal Number to be converted to a fraction
1: Maximum Allowed Denominator (a positive integer)


OUTPUT:

1: 'Numerator/Denominator'

Note: System flag -3 is cleared (to allow symbolic results).


EXAMPLE of completeness: What fraction is closest to the number "e", but with a
  denominator not bigger than 20?

The HP 48SX and the HP 32SII say it's 19/7.  They both say that the next better
  fraction is 87/32.  But there are two fractions between these which they
  miss: 49/18 and 68/25.

Press 1 EXP 20 DEC2FRAC and see '49/18', the correct answer.


EXAMPLE of speed improvement: the golden ratio, (û5+1)/2, which is
  approximately 514229/317811.  This is found by the HP 48SX ->Q function in
  3.23 seconds, and by DEC2FRAC in 1.29 seconds.  For the fastest possible
  program, see D2F on this disk, which finds it in 0.86 seconds.

------------

At the March 22nd meeting of the Orange/Los Angeles Counties Chapter of the
HP-48 users club, Harry Bertucelli objected to my contention that DEC2FRAC
finds ALL possible fractions.

Harry is a professional mathematician, and accepts nothing without a formal
proof.  So he withdrew to a corner of the room and into a deeper corner of his
mind, and in short order developed a complete proof that DEC2FRAC does in fact
find all possible fractions (up to the point where the HP 48 begins to
introduce round-off errors, of course).  It made his day to see (and prove the
validity of) a completely new algorithm in number theory.  It made my day to
know that the very first computer to run it was an HP 48SX.

------------

Well, darn it, this is only half true.  It may well be that the 48 has the
honors, but the algorithm IS NOT NEW.

Bummer.  I thought I'd discovered something new.  Turns out that I was 102
years late!!  In a book called _Textbook of Algebra_ by G.  Chrystal, 1st
edition in 1889, in Part II, Chapter 32, this improved continued fraction
algorithm is presented and proven.  Odd to tell, Chrystal speaks of it as if it
were ancient knowledge.  The original discoverer is not named, nor is the
algorithm.  Hmmm.  Thanks to Harry Bertucelli for exhuming this obscure
reference.  In any case, it seems to have lay dormant for many years; it is not
mentioned in modern books about number theory.  It's time for us to revitalize
it!

[See NEW2Q for HP's reaction to DEC2FRAC.  -jkh-]