Repeating Decimals

01132018, 12:22 AM
Post: #1




Repeating Decimals
How would I produce repeating decimals such as 142857 being repeated endlessly for 1/7. Some CASIO calculators do so including the fax115ES PLUS and the Japanese version of the CLASSWIZ fox991EX.


01132018, 12:23 AM
Post: #2




RE: Repeating Decimals
Spell check turned fx into fax and fox for the CASIO model prefixes!


01132018, 10:06 AM
Post: #3




RE: Repeating Decimals
(01132018 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 fax115ES PLUS and the Japanese version of the CLASSWIZ fox991EX. please, see if this routine by retoa helps. Salvo ∫aL√0mic (IT9CLU) :: HP Prime 50g 41CX 71b 42s 39s 35s 12C 15C  DM42, DM41X  WP34s Prime Soft. Lib 

01132018, 06:09 PM
Post: #4




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


01172018, 06:20 AM
(This post was last modified: 01232018 02:32 AM by Joe Horn.)
Post: #5




RE: Repeating Decimals
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 base10 ("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 nonrepeating 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? <0ɸ0> Joe 

01182018, 05:46 AM
Post: #6




RE: Repeating Decimals
As always, an informative and interesting response!


01192018, 03:58 AM
(This post was last modified: 01232018 02:31 AM by Joe Horn.)
Post: #7




RE: Repeating Decimals
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:
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 nonrepeating 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 nonrepeating 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. <0ɸ0> Joe 

01192018, 03:11 PM
Post: #8




RE: Repeating Decimals
Nice!


01202018, 06:02 AM
Post: #9




RE: Repeating Decimals
The algorithm explained above has been coded in RPL for the HP 50g here: http://www.hpmuseum.org/forum/thread9973.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. <0ɸ0> Joe 

01202018, 09:08 AM
(This post was last modified: 02052018 11:39 PM by StephenG1CMZ.)
Post: #10




RE: Repeating Decimals
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:
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. Stephen Lewkowicz (G1CMZ) 

01212018, 11:34 AM
(This post was last modified: 01212018 04:33 PM by StephenG1CMZ.)
Post: #11




RE: Repeating Decimals
Here is version of Joe Horn's algorithm using Multiplicative Order, coded in PPL.
http://www.hpmuseum.org/forum/thread9986.html Stephen Lewkowicz (G1CMZ) 

01212018, 10:22 PM
(This post was last modified: 01212018 10:48 PM by StephenG1CMZ.)
Post: #12




RE: Repeating Decimals
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. Stephen Lewkowicz (G1CMZ) 

01212018, 10:41 PM
(This post was last modified: 01212018 10:43 PM by Joe Horn.)
Post: #13




RE: Repeating Decimals
(01212018 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. Correct. The nonmultiplicativeorder algorithm is much simpler to code, but for large repeating sections it runs much slower. In fact, if you use instead the algorithm which precalculates 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 fractiontorepeatingdecimal a bazillion timers faster than the nonmultiplicativeorder 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... <0ɸ0> Joe 

01212018, 10:58 PM
Post: #14




RE: Repeating Decimals
I generate the repeating digits using a call to iquot (a builtin). But in PPL it only works correctly up to 12 digits. Apologies for the typo in your name.
Stephen Lewkowicz (G1CMZ) 

01222018, 01:35 AM
Post: #15




RE: Repeating Decimals
(01212018 10:58 PM)StephenG1CMZ Wrote: I generate the repeating digits using a call to iquot (a builtin). 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. <0ɸ0> Joe 

01232018, 01:46 AM
Post: #16




RE: Repeating Decimals
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... 

01232018, 02:18 AM
(This post was last modified: 01232018 02:28 AM by Joe Horn.)
Post: #17




RE: Repeating Decimals
(01232018 01:46 AM)tgray Wrote: Cool post. I learned something. I also implemented Joe's method for the DM42/Free42: link 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 = 727/54, and 54 = 2^1 * 3^3. Therefore there is actually only ONE nonrepeating digit: "13.4_629_". <0ɸ0> Joe 

01232018, 02:24 AM
Post: #18




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


01272018, 09:53 PM
Post: #19




RE: Repeating Decimals
Wonder what CASIO did in their program...the old fx115 ES PLUS and the new fxJP900 CLASSWIZ (Japanese version of the CLASSWIZ) comes up with results easily, even with denominators such as 59 or 61 which have lengthy repeating decimals...


02052018, 11:34 PM
(This post was last modified: 02052018 11:37 PM by StephenG1CMZ.)
Post: #20




RE: Repeating Decimals
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/thread998...l#pid90463 Searching online for fractions with long transients hasn't yielded much test data, any suggestions? Stephen Lewkowicz (G1CMZ) 

« Next Oldest  Next Newest »

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