+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (50G) Fast Continued Fractions (/thread-4738.html)
(50G) Fast Continued Fractions - Joe Horn - 09-17-2015 04:37 PM
'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.