(50G) Fast Continued Fractions
09-17-2015, 04:37 PM (This post was last modified: 06-15-2017 01:41 PM by Gene.)
Post: #1
 Joe Horn Senior Member Posts: 1,687 Joined: Dec 2013
(50G) Fast Continued Fractions
'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.

<0|ɸ|0>
-Joe-
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)