(50g) Integer Ratio to Exact Repeating Decimal

[Joe Horn]

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

[Gerald H]

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
    "_"
    &$
  ;
;

[Joe Horn]

"DUP1PUTLAM_" won't compile on a standard HP 50g. Can it be replaced with "DUP 1PUTLAM"?

[Gerald H]

Yes, DUP 1PUTLAM is the correct reading. Sorry, I intended to remove all ?_s. (Now done.)

[Joe Horn]

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!