Post Reply 
(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
(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-
Visit this user's website Find all posts by this user
Quote this message in a reply
01-20-2018, 05:13 PM (This post was last modified: 01-20-2018 09:46 PM by Gerald H.)
Post: #2
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

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
    "_"
    &$
  ;
;
Find all posts by this user
Quote this message in a reply
01-20-2018, 09:18 PM
Post: #3
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-
Visit this user's website Find all posts by this user
Quote this message in a reply
01-20-2018, 09:27 PM (This post was last modified: 01-20-2018 09:38 PM by Gerald H.)
Post: #4
RE: (50g) Integer Ratio to Exact Repeating Decimal
Yes, DUP 1PUTLAM is the correct reading. Sorry, I intended to remove all ?_s. (Now done.)
Find all posts by this user
Quote this message in a reply
01-20-2018, 11:05 PM
Post: #5
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
Your 1st program: 3.61 seconds!
Your 2nd program: 3.56 seconds!

<0|ɸ|0>
-Joe-
Visit this user's website Find all posts by this user
Quote this message in a reply
Post Reply 




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