(50G) Fast Continued Fractions

[Joe Horn]

'R2CF' (Ratio to Continued Fraction): Convert Ratios of Two Integers to/from Continued Fractions.
An HP 50g System RPL program by Joe Horn.

Running 'R2CF' on a regular fraction (that is, an algebraic object that is a ratio of two integer-type objects) converts it to a continued fraction in list notation (a list of integers). 'R2CF' also converts continued fractions back to regular fractions. It's very fast.

Examples (in exact mode of course):

Input: '355/113'
Output: { 3 7 16 } because \(\frac{355}{113} = 3 + \cfrac{1}{7
+ \cfrac{1}{16} }\) which is written as { 3 7 16 } in continued fraction shorthand, with only the partial quotients in the list, not the numerators which are always 1.
The above example executes in 0.02 seconds.

Input: { 3 7 16 }
Output: '355/113'
The above example executes in 0.025 seconds.

The size of the input integers and lists is limited only by available memory.

Note: Most texts separate the partial quotients of a continued fraction's shorthand notation with commas, and some texts place a semicolon after the first one to indicate that it's the integer part of the original fraction. Therefore you will usually see 355/113 expressed as either {3, 7, 16} or {3; 7, 16}. This HP 50g program assumes that the first number in the list is always the integer part, so it'll be zero for fractions between 0 and 1. Therefore all punctuation may be omitted without ambiguity.

'R2CF' (Ratio to Continued Fraction)

Code:

%%HP: T(3);
"::
  0LastRomWrd!
  CK1NOLASTWD
  CK&DISPATCH1
  BINT5
  ::
    DUP
    INNERCOMP
    TRUE
    SWAP
    ZERO_DO
    SWAP
    TYPE
    # 2614
    EQUAL
    AND
    LOOP
    NOTcase
    SETTYPEERR
    INNERCOMP
    ZINT 1
    ZINT 0
    ROT
    ZERO_DO
    OVER
    4ROLL
    FPTR2 ^QMul
    FPTR2 ^QAdd
    SWAP
    LOOP
    FPTR2 ^NDXFext
  ;
  BINT9
  ::
    DUP
    INNERCOMP
    FPTR2 ^metafraction?
    OVER#2+UNROL
    NDROP
    NOTcase
    SETTYPEERR
    FPTR2 ^FXNDext
    DEPTH
    DUP
    #1+UNROLL
    BEGIN
    SWAPOVER
    FPTR2 ^ZDIVext
    ROTSWAP
    DUP
    ZINT 0
    EQUAL
    UNTIL
    2DROP
    DEPTH
    ROLL
    DEPTH
    SWAP#-
    #1+
    {}N
  ;
;"

BYTES: 188.0 #9465h

Note to hackers: If the above code looks familiar, it might be because you saw it before in the LongFloat library. I'm not copying Gjermund's code; to the contrary, I sent it (many years ago!) to him, suggesting that he replace his continued fraction routines (SF→CF and CF→SF) with my code because it was faster. He graciously did so.