Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!sdd.hp.com!hp-pcd!hpcvra.cv.hp.com!rnews!hpcvbbs!akcs.Guest_
From: akcs.Guest_@hpcvbbs.UUCP (Joseph K. Horn)
Newsgroups: comp.sys.handhelds
Subject: HP 48 Improved ->Q
Keywords: hp 48 ->q fractions faster better
Message-ID: <27e87852:2491comp.sys.handhelds@hpcvbbs.UUCP>
Date: 21 Mar 91 09:40:09 GMT
Lines: 64

%%HP:T(3);
@ DEC2FRAC for the HP 48SX (obsoletes ->Q)
@ Improved Decimal-to-Fraction, by Joseph K. Horn.
@
@ Faster & more complete than HP 48SX (->Q function) and HP 32SII
@   (with maximum denominator set), both of which 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.
@ This new algorithm finds the very best solution, very quickly.
@ Algorithm: Continued Fractions by fast recursion formula, then 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'
@
@ Example: What fraction is closest to the number "e", but
@   with a denominator not bigger than 20?  It's 49/18.
@
@ The HP 48SX and the HP 32SII say it's 19/7.  They say that the next
@   better fraction is 87/32.  But there are two fractions between
@   these which are missed: 49/18 and 68/25.
@
@ Press 1 EXP 20 DEC2FRAC and see '49/18', the correct answer.
@
@ An example of speed increase is the golden ratio, (sqr(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.
@
@ Checksum = # 4F52h; Size on stack = 296.5 bytes.
@
\<< DUP2 @ Must be two arguments.  Exit now if max denominator < 2, or
  IF 1 > SWAP FP AND @ if decimal fraction is an integer.
  THEN \-> f c @ Store decimal fraction, and max denominator.
    \<< 0 1 f @ Calculate only denominators.  Do numerator only at end.
      WHILE OVER c < OVER AND @ Do until bigger than max denominator
      REPEAT INV DUP FP 4 ROLLD IP OVER * ROT + ROT @ This is the
      END DROP DUP2 c @ recursion formula continued fraction expansion.
      IF DUP2 > @ Is there a possible "missing" fraction?
      THEN - OVER / CEIL * - @ This is the new, fast "jump backwards".
      ELSE 3 DROPN @ (Sometimes there's no need to jump.)
      END DUP2 1 2 @ Take the new denominator & the previous one, and
      START DUP f * 0 RND SWAP / f - ABS SWAP @ turn into fractions.
      NEXT @ See which one's closest to the original decimal fraction.
      IF > @ Compare the two solutions, and
      THEN SWAP @ pick the better one.
      END DROP DUP f * 0 RND SWAP @ Calculate the numerator.
    \>> @ End of real work; now clean up the output.
    IF DUP ABS 1 > @ Is the denominator greater than 1?
    THEN # 5603Eh SYSEVAL @ If so, make output into 'A/B' form.
    ELSE DROP @ Otherwise, get rid of extraneous denominator,
    END @ and exit program.
  ELSE DROP @ If bad arguments, do nothing to "decimal fraction", but
  END @ get rid of "maximum denominator" and exit program.
\>>