+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (50g) Integer Ratio to Exact Repeating Decimal (/thread-9973.html)
(50g) Integer Ratio to Exact Repeating Decimal - Joe Horn - 01-20-2018 05:54 AM
This 50g program expresses any ratio of two integers as an exact decimal number, indicating which digits repeat and which digits do not repeat.
Examples:
Input: 5/12
Output: "0.41_6_" which means 0.416666666... with the 6 repeating forever. The underscores "_" indicate the repeating digit(s).
Input: 13/18
Output: "0.7_2_" which means 0.72222222...
Input: 71/17
Output: "4._1764705882352941_" (all 16 digits repeat forever)
Input: 22/7
Output: "3._142857_"
Input: 15/8
Output: "1.875" (the lack of underscores indicates that the decimal terminates, with no digits repeating forever)
N.B. The longer the repeating section, the longer it takes for the program to run. Example: 115/226 takes 13 seconds to return the answer, which includes a repeating section of 112 digits.
Code:
%%HP: T(3)A(R)F(.);
\<< FXND DUP FACTORS DUPDUP @ begin finding length of non-repeating section
IF 2 POS DUP @ how many factors of 2 does the denominator have?
THEN 1. + GET
ELSE NIP
END SWAP DUP
IF 5 POS DUP @ how many factors of 5 does the denominator have?
THEN 1. + GET
ELSE NIP @ MAX(factors of 2 and 5) = number of non-repeating digits
END MAX 0 \-> n d f r @ Numerator, Denominator, Fixed-length (non-repeating), Remainder
\<< n d IDIV2 SWAP "." + SWAP @ put integer part and decimal point into a string
IF f @ Is there any repeating part?
THEN 1. f @ if so, then crank out that many digits of n/d
START 10 * d IDIV2 UNROT + SWAP
NEXT
END @ if not, then fall directly into the repeating-section code
IF DUP @ Are there any repeating digits? (AKA is any remainder left?)
THEN DUP 'r' STO SWAP "_" + SWAP @ if so, the store the initial Remainder, print a "_", and ...
DO 10 * d IDIV2 UNROT + SWAP @ ... crank out digits using infinite division ...
UNTIL DUP r == @ ... until the initial remainder reappears ...
END @ then stop cranking out digits.
END DROP IF r THEN "_" + END @ if there were any repeating digits, print another "_"
\>>
\>>BYTES: 324.5 #3740h
EDIT: A step-by-step analysis of the algorithms used above can be found here: http://www.hpmuseum.org/forum/thread-9919-post-88913.html#pid88913 and an exploration of alternatives for the first 9 lines of code (between FXND and MAX) can be found here: http://www.hpmuseum.org/forum/thread-9955.html
EDIT 2: The variables used in the code above are:
n: Numerator of input
d: Denominator of input
f: length of Fixed (non-repeating) section of digits
r: the saved Remainder
RE: (50g) Integer Ratio to Exact Repeating Decimal - Gerald H - 01-20-2018 05:13 PM
Edited to remove DUP1PUTLAM_:
A very nice piece of programming, congratulations.
I've taken the liberty of writing a Sys version, in fact two.
The first uses the function ^Factors to find number of 2's & 5's, the second uses my Sys programme from this thread
http://www.hpmuseum.org/forum/thread-9955.html
which for all fractions I've tested proves faster.
Trust the programmes are of some interest.
Size: 305.5
CkSum: # C2A3h
Code:
::
CK1&Dispatch
BINT10
::
FPTR2 ^FXNDext
DUP
FPTR2 ^FACTORS
DUPDUP
ZINT 2
SWAP
FPTR2 ^ListPos
DUP
#0<>
ITE
::
#1+
NTHCOMPDROP
;
SWAPDROP
SWAPDUP
ZINT 5
SWAP
FPTR2 ^ListPos
DUP
#0<>
ITE
::
#1+
NTHCOMPDROP
;
SWAPDROP
COERCE2
#MAX
ZINT 0
'
NULLLAM
BINT4
NDUPN
DOBIND
4GETLAM
3GETLAM
FPTR2 ^ZDIVext
SWAP
FPTR2 ^Z>S
CHR_.
>T$
SWAP
2GETLAM
#0=?SKIP
::
2GETLAM
#1+_ONE_DO
ZINT 10
FPTR2 ^RMULText
3GETLAM
FPTR2 ^ZDIVext
3UNROLL
FPTR2 ^Z>S
&$SWAP
LOOP
;
DUP
ZINT 0
EQUALNOT
IT
::
DUP
1PUTLAM
SWAP
"_"
&$SWAP
BEGIN
ZINT 10
FPTR2 ^RMULText
3GETLAM
FPTR2 ^ZDIVext
3UNROLL
FPTR2 ^Z>S
&$SWAP
DUP
1GETLAM
EQUAL
UNTIL
;
DROP
1GETABND
ZINT 0
EQUAL
?SEMI
"_"
&$
;
;Size: 276.5
CkSum: # E5E6h
Code:
::
CK1&Dispatch
BINT10
::
FPTR2 ^FXNDext
DUP
FPTR2 ^ZTrialDiv2
BINT0
ROT
BEGIN
DUP
ZINT 5
FPTR2 ^ZDIVext
ZINT 0
EQUAL
WHILE
::
SWAPDROP
SWAP#1+SWAP
;
REPEAT
2DROP
#MAX
ZINT 0
'
NULLLAM
BINT4
NDUPN
DOBIND
4GETLAM
3GETLAM
FPTR2 ^ZDIVext
SWAP
FPTR2 ^Z>S
CHR_.
>T$
SWAP
2GETLAM
#0=?SKIP
::
2GETLAM
#1+_ONE_DO
ZINT 10
FPTR2 ^RMULText
3GETLAM
FPTR2 ^ZDIVext
3UNROLL
FPTR2 ^Z>S
&$SWAP
LOOP
;
DUP
ZINT 0
EQUALNOT
IT
::
DUP
1PUTLAM
SWAP
"_"
&$SWAP
BEGIN
ZINT 10
FPTR2 ^RMULText
3GETLAM
FPTR2 ^ZDIVext
3UNROLL
FPTR2 ^Z>S
&$SWAP
DUP
1GETLAM
EQUAL
UNTIL
;
DROP
1GETABND
ZINT 0
EQUAL
?SEMI
"_"
&$
;
;RE: (50g) Integer Ratio to Exact Repeating Decimal - Joe Horn - 01-20-2018 09:18 PM
"DUP1PUTLAM_" won't compile on a standard HP 50g. Can it be replaced with "DUP 1PUTLAM"?
RE: (50g) Integer Ratio to Exact Repeating Decimal - Gerald H - 01-20-2018 09:27 PM
Yes, DUP 1PUTLAM is the correct reading. Sorry, I intended to remove all ?_s. (Now done.)
RE: (50g) Integer Ratio to Exact Repeating Decimal - Joe Horn - 01-20-2018 11:05 PM
Thanks, Gerald! Your System RPL programs are much faster than my User RPL program, roughly 16 times faster when the repeating section is large! Good job!
Input: 1/503 (repeating section is 502 digits long)
My program: 60 seconds
Your 1st program: 3.61 seconds!
Your 2nd program: 3.56 seconds!