Repeating Decimals

[lrdheat]

How would I produce repeating decimals such as 142857 being repeated endlessly for 1/7. Some CASIO calculators do so including the fax-115ES PLUS and the Japanese version of the CLASSWIZ fox-991EX.

[lrdheat]

Spell check turned fx into fax and fox for the CASIO model prefixes!

[salvomic]

(01-13-2018 12:22 AM)lrdheat Wrote:  How would I produce repeating decimals such as 142857 being repeated endlessly for 1/7. Some CASIO calculators do so including the fax-115ES PLUS and the Japanese version of the CLASSWIZ fox-991EX.

please, see if this routine by retoa helps.

Salvo

[lrdheat]

Thanks...I wish to go in the other direction...from a fraction to determine the repeating decimal.

[Joe Horn]

Wow, you launched me into a delightful revisit to the old PPC days when we wrote programs called "infinite division" which essentially performed long division, outputting as many digits of a division as you asked for. It's easy; to get N digits of A/B you just calculate iquo(A*10^N,B), and if the result is too few digits you just tack on leading zeros.

Now we have to discern how many digits we should ask for. The decimal expansion of every ratio of integers has two parts after the decimal point: a sequence of digits which don't repeat (called the transient) followed by a sequence of digits which repeat (called the repetend). Example: 1/208 = 0.0048076923 with the underlined digits repeating forever. Here's how to determine that the transient is 4 digits long, and the repetend is 6 digits long.

EDIT: STEP ZERO: Fully reduce the fraction, if your machine doesn't automatically do that for you (like RPL machines do). [Thanks to tgray for catching this oversight!]

First, factor out all 2's and 5's like this: 208 = 2^4 * 5^0 * 13. The powers of 2 and 5, as you can see, are 4 and 0. The length of the transient will always be the larger of those two powers (in this case, 4). This can be easily programmed. After factoring out the 2's and 5's, what's left is 13.

Next, find the multiplicative order of 10 (mod 13). It's always 10 because we are using base-10 ("decimal") notation. The 13 is from the previous paragraph. Finding the multiplicative order is not a simple task, but it's been programmed for the HP 50g and the algorithm would be the same on the Prime. The multiplicative order of 10 (mod 13) is 6. That's the length of the repetend.

So now we know that 1/208 consists of 4 non-repeating digits after the decimal point, followed by 6 repeating digits. All we have to do is use "infinite division" to crank out 10 digits of 1/208, and insert a symbol (such as an underscore) after the 4th digit, like this:

"0.0048_076923" which would mean 0.0048 followed by 076923 repeating forever.

Of course, if the repetend length is zero, then the decimal terminates, and the underscore symbol should not be inserted, e.g. 1/40 = 0.025 with no repeating part.

One benefit of using the above method is that it'll work for ANY fraction, no matter how many digits it has or how messy it might be. Anybody have time to code this for the Prime?

[lrdheat]

As always, an informative and interesting response!

[Joe Horn]

Oh my goodness, it hit me today that the whole headache of finding the multiplicative order of 10 (mod X) can be entirely avoided! All we have to do is:

• Find how many digits DON'T repeat (easily done, as explained above).
• Using infinite division, output that many digits.
• At that point, save the current remainder.
• Output more digits using infinite division, but as soon as the remainder saved in the previous step reoccurs, STOP.

That's all it takes! Example using RPL (because I think in RPL):

123/208

EDIT: STEP ZERO: Fully reduce the fraction, if your machine doesn't automatically do that for you (like RPL machines do). [Thanks to tgray for catching this oversight!]

First, find how many digits after the decimal point don't repeat:
208 = 2^4 * 5^0 * 13, and MAX(4,0) is 4, so any integer divided by 208 will have 4 digits after the decimal point which don't repeat.

Secondly, find the integer part of the answer:
123 208 IDIV2 --> 0 123 <-- Integer part of answer (on level 2 of the stack; the remainder 123 is on level 1 of the stack).

Thirdly, print that 0 and a decimal point here.

Fourthly, do 10 * 208 IDIV2 four times to get the 4 digits which don't repeat, printing each digit as it's calculated:
10 * 208 IDIV2 --> 5 190 <-- Begin non-repeating part
10 * 208 IDIV2 --> 9 28
10 * 208 IDIV2 --> 1 72
10 * 208 IDIV2 --> 3 96 <-- End repeating part. Save that remainder.

Fifthly, print the underscore character "_" to separate the non-repeating digits from the repeating digits.

Sixthly and finally, repeat 10 * 208 IDIV2, printing each digit as it's calculated, until that saved remainder reappears.
10 * 208 IDIV2 --> 4 128
10 * 208 IDIV2 --> 6 32
10 * 208 IDIV2 --> 1 112
10 * 208 IDIV2 --> 5 80
10 * 208 IDIV2 --> 3 176
10 * 208 IDIV2 --> 8 96 <-- There it is! STOP. Done.

So 123/208 = 0.5913_461538 (using the underscore to mean "here begin the repeating digits").

Holy smokes, that's EASY to program in RPL! No "multiplicative order" routine is necessary! Writing it in HP PPL is left as an exercise for the student.

[lrdheat]

Nice!

[Joe Horn]

The algorithm explained above has been coded in RPL for the HP 50g here: http://www.hpmuseum.org/forum/thread-9973.html

Unlike the Casio calculators which support repeating decimal notation, the above program always returns ALL the digits (albeit slowly). Casio's give up after less than 100 digits.

[StephenG1CMZ]

That's an interesting challenge Joe.

I've attempted to turn your algorithm using multiplicative order into what you could think of as pseudocode for a CAS solution...
I am more familiar with PPL than CAS, so this first attempt is in PPL.
As such, the range of inputs it works with is quite limited.
For example NN=208 (representing 1/208) works, but 301 doesn't.
And if whats left is 1, I think the call to MultiplicativeOrder either stalls or is slow.
Here is what I have so far

Code:


 LOCAL CRID:="REPEATING DECIMAL 0.01";
 //Written 2018 StephenG1CMZ
 //Following Joe Horn`s algorithm using Multiplicative Order

 //Disclaimer: This implement yields visually useful results
 // for some repeating decimals EG NN=208
 //But stalls or slows given a non-repeating value.
 //Large Repeating Lengths yield weird output eg NN=301

 LOCAL FR2,FR5;

 ZEROS(NN)
 BEGIN
  IF NN>0 THEN
   RETURN "0"+ZEROS(NN-1);
  END;
  RETURN ""; 
 END;

 EXPORT MAXFACTOR25(NN)
 BEGIN 
  LOCAL MAXFACTR:=0;
  LOCAL LST,LP;
 
  LST:=mat2list(ifactors(NN));
  FR2:=0; FR5:=0;
  LP:=POS(LST,2); 
  IF LP THEN
   FR2:=LST(LP+1);
  END;
  LP:=POS(LST,5); 
  IF LP THEN
   FR5:=LST(LP+1);
  END;
  
  MAXFACTR:=MAX(FR2,FR5);
  RETURN MAXFACTR;//0=NONE
 END;

 EXPORT SOFAR (NN )
 BEGIN
  LOCAL TRANSIENTLEN:=MAXFACTOR25(NN);
  LOCAL WHATSLEFT,MO;
  LOCAL TP,RP,NDIGITS;
  LOCAL ST;//STRINGVERSION
 
  WHATSLEFT:=exact(NN/(2^FR2*5^FR5));
  IF WHATSLEFT==1 THEN
   MSGBOX("WHATS LEFT "+WHATSLEFT);
   //RETURN 1/NN;//OR AVOID
  END;
  //PRINT("BEFORE");
  //See http://www.hpmuseum.org/forum/thread-3212.html
  MO:=MultiplicativeOrder(WHATSLEFT,10);
  //PRINT("AFTER");
  NDIGITS:=TRANSIENTLEN+MO;
  //GET TP (WITHOUT ROUNDING LAST DIGIT)
  TP:=(1/NN)*10^TRANSIENTLEN;
  TP:=IP(TP)/(10^TRANSIENTLEN);
  RP:=iquo(1*10^NDIGITS,NN);
  //The string version asks for leading zeros I hoped
  //but no...pad it manually 
  //ST:=format(RP,"s"+NDIGITS);
   
  ST:=ZEROS(NDIGITS-DIM(STRING(RP)))+RP;
  PRINT(); 
  PRINT("Input Fraction: 1/"+NN);
  PRINT("Whats Left: "+WHATSLEFT);
  PRINT("Multiplicative Order: "+MO);
  PRINT("Length: "+{TRANSIENTLEN,MO});
  IF MO>12 THEN //EXPECT REPEATING PART TO GO WEIRD
   PRINT("MO>12: CAUTION");
  END;
  PRINT("PPL REAL: "+1/NN);
  PRINT("TRANSIENT PART: "+IFTE(TRANSIENTLEN,TP," (none)"));
  PRINT(ST);
   //NB REMEMBER THE LAST REPEATING DIGIT MUST NOT BE ROUNDED
  
  //RETURN RESULTS
  //TRANSIENTLEN=0 =NO TRANSIENT
  //MO=0 =NO REPEATING
  RETURN {{TRANSIENTLEN,TP},{MO,ST}};
 END;

 EXPORT NUMB()
 BEGIN
  PRINT(CRID);  
  //PRINT(SOFAR(208));
 END;

But Joe has moved the goalposts and given us a new approach that no longer requires MultiplicativeOrder, so there is probably no further use for this implement.

Update: The maxfactors25 procedure here has a bug: Instead of seeing {3,2} as 3^2, it finds the 2 and sees that as 2^???. There is an updated version in the software library.

[StephenG1CMZ]

Here is version of Joe Horn's algorithm using Multiplicative Order, coded in PPL.
http://www.hpmuseum.org/forum/thread-9986.html

[StephenG1CMZ]

Joe Horn, it occurs to me that there is an important difference between your latest algorithm and the earlier one using Multiplicative Order, that might mean the earlier algorithm remains useful.

If I understand your latest algorithm correctly, it outputs the transient part and then keeps producing the recurring part until it identifies that it is going to repeat.

That means there is no advance knowledge of how long the repeating part is... Which could mean you consume lots of resources (time, disk space, ...) Producing lots of digits before exhausting resources.

By contrast, your solution using multiplicative order starts by working out how many recurring digits there will be...providing the opportunity to just return NaN before exhausting resources.

By the way, do you think adding a final underscore to numbers would be a useful formatting improvement? It is clear that 1.2_34_ has 34 as the repeating part, whereas 1.2_34 leaves room for doubt as to whether the number has exceeded the size of a page.

[Joe Horn]

(01-21-2018 10:22 PM)StephenG1CMZ Wrote:  Jo Horn, it occurs to me that there is an important difference between your latest algorithm and the earlier one using Multiplicative Order, that might mean the earlier algorithm remains useful.

If I understand your latest algorithm correctly, it outputs the transient part and then keeps producing the recurring part until it identifies that it is going to repeat.

That means there is no advance knowledge of how long the repeating part is... Which could mean you consume lots of resources (time, disk space, ...) Producing lots of digits before exhausting resources.

By contrast, your solution using multiplicative order starts by working out how many recurring digits there will be...providing the opportunity to just return NaN before exhausting resources.

Correct. The non-multiplicative-order algorithm is much simpler to code, but for large repeating sections it runs much slower. In fact, if you use instead the algorithm which pre-calculates the repeating section's length (using the multiplicative order), ALL of decimal number's digits (both the transient and repeating sections) can be obtained with a SINGLE simple calculation, without any looping at all. It would make a Prime program for fraction-to-repeating-decimal a bazillion timers faster than the non-multiplicative-order algorithm, even for huge denominators. I'll keep watching these discussions to see if anybody programs this method... if they haven't already.

EDIT: Ooh ooh, I see above that you have! Do you generate the digits by looping or all at once? I gotta go look...

[StephenG1CMZ]

I generate the repeating digits using a call to iquot (a built-in). But in PPL it only works correctly up to 12 digits. Apologies for the typo in your name.

[Joe Horn]

(01-21-2018 10:58 PM)StephenG1CMZ Wrote:  I generate the repeating digits using a call to iquot (a built-in).

Excellent! That's the shortcut that I was thinking of.

Quote:But in PPL it only works correctly up to 12 digits.

Aha. Since this task is done entirely in the integer domain, doing it as a CAS program would allow any size input and any length output. iquo and iquorem are CAS functions just begging to be given large inputs.

[tgray]

Cool post. I learned something. I also implemented Joe's method for the DM42/Free42: link

I did notice that Joe's algorithm misses the first repeating period of 11632/864. I think this is because when you factor 864 for factors of 2 and 5, you get 2^5 for the 2's. So following the method, there are 5 non repeating digits after the decimal, even though there are actually only 2, with the next 3 being the first period of the repeating set of 3 digits. I didn't attempt to fix this.

11632/864 -> 13.46_296...

[Joe Horn]

(01-23-2018 01:46 AM)tgray Wrote:  Cool post. I learned something. I also implemented Joe's method for the DM42/Free42: link

I did notice that Joe's algorithm misses the first repeating period of 11632/864.

It doesn't. See below.

Quote:I think this is because when you factor 864 for factors of 2 and 5, you get 2^5 for the 2's.

But you shouldn't factor 864, because your input (11632/864) reduces to 727/54. If your program inputs the numerator and denominator separately, then YOU must reduce them yourself before doing anything else. The work for your example is therefore done on 54, not 864.

EDIT: Aha! I just noticed that my algorithm posting above doesn't mention that the input fraction must be fully reduced. If I may offer a feeble (but true) excuse, it's because I think in RPL, and when you put a fraction on an RPL stack, it automatically gets reduced, so I assumed that the input would always already be reduced. This of course is not the case for program which input the numerator and denominator separately. I will edit the algorithm posting above to insert STEP ZERO: Fully reduce the fraction.

Quote:So following the method, there are 5 non repeating digits after the decimal, even though there are actually only 2, with the next 3 being the first period of the repeating set of 3 digits. I didn't attempt to fix this.

11632/864 -> 13.46_296...

11632/864 = 727/54, and 54 = 2^1 * 3^3. Therefore there is actually only ONE non-repeating digit: "13.4_629_".

[tgray]

Ahh, I knew I was missing something. Thanks for the explanation (and the previous one).

[lrdheat]

Wonder what CASIO did in their program...the old fx-115 ES PLUS and the new fx-JP900 CLASSWIZ (Japanese version of the CLASSWIZ) comes up with results easily, even with denominators such as 59 or 61 which have lengthy repeating decimals...

[StephenG1CMZ]

Version 0.7 of my program now handles fractions as well as reciprocals, reducing the fractions as necessary (Joes Horn's "Step 0").
http://www.hpmuseum.org/forum/thread-998...l#pid90463
Searching online for fractions with long transients hasn't yielded much test data, any suggestions?