(50g) Integer Ratio to Exact Repeating Decimal
01-20-2018, 05:54 AM (This post was last modified: 01-20-2018 03:20 PM by Joe Horn.)
Post: #1
 Joe Horn Senior Member Posts: 1,687 Joined: Dec 2013
(50g) Integer Ratio to Exact Repeating Decimal
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-991...l#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

<0|ɸ|0>
-Joe-
01-20-2018, 05:13 PM (This post was last modified: 01-20-2018 09:46 PM by Gerald H.)
Post: #2
 Gerald H Senior Member Posts: 1,452 Joined: May 2014
RE: (50g) Integer Ratio to Exact Repeating Decimal
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

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 "_" &$   ; ;
01-20-2018, 09:18 PM
Post: #3
 Joe Horn Senior Member Posts: 1,687 Joined: Dec 2013
RE: (50g) Integer Ratio to Exact Repeating Decimal
"DUP1PUTLAM_" won't compile on a standard HP 50g. Can it be replaced with "DUP 1PUTLAM"?

<0|ɸ|0>
-Joe-
01-20-2018, 09:27 PM (This post was last modified: 01-20-2018 09:38 PM by Gerald H.)
Post: #4
 Gerald H Senior Member Posts: 1,452 Joined: May 2014
RE: (50g) Integer Ratio to Exact Repeating Decimal
Yes, DUP 1PUTLAM is the correct reading. Sorry, I intended to remove all ?_s. (Now done.)
01-20-2018, 11:05 PM
Post: #5
 Joe Horn Senior Member Posts: 1,687 Joined: Dec 2013
RE: (50g) Integer Ratio to Exact Repeating Decimal
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

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

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