 (50g) Integer Ratio to Exact Repeating Decimal - Printable Version +- 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!