programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Jeanne Boyarsky
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Rob Spoor
• Devaka Cooray
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Frits Walraven
• Tim Moores
Bartenders:
• Mikalai Zaikin

# Finding recurring cycle in a decimal.

Sam Benry
Ranch Hand
Posts: 89
• Number of slices to send:
Optional 'thank-you' note:
lets say we have
double x = 1/7;

x = 0.142857 142857 142857 142857
the recurring cycle in this decimal is 142857

is there anyway to find this using java?
for example, if x = 1/7 >> y = 142857
Thanks

Campbell Ritchie
Marshal
Posts: 79260
377
• Number of slices to send:
Optional 'thank-you' note:
It's not Java that is the problem; finding a recurrent pattern in decimal fractions is easy.

The hard part is working out the algorithm. Please show us what algorithm you plan to use.

Jeanne Boyarsky
author & internet detective
Posts: 41878
909
• Number of slices to send:
Optional 'thank-you' note:
Sam,
One problem you can run into is that a double doesn't store the exact value. For example, 2/3 is stored as .666....667. This isn't a recurring decimal in storage although I'm sure you'd want to flag it as one.

Darryl Burke
Bartender
Posts: 5167
11
• Number of slices to send:
Optional 'thank-you' note:
Not to mention that
double x = 1/7;
would, because of integer division, assign x a value of 0 and not 0.142857 142857 142857 142857

Sam Benry
Ranch Hand
Posts: 89
• Number of slices to send:
Optional 'thank-you' note:
@Campbell Ritchie
I need help with the algorithm itself, not the code, I don't want a code. I want a way to solve this problem.

@Jeanne Boyarsky
so you suggest changing the declaration? float maybe? or something else?

Campbell Ritchie
Marshal
Posts: 79260
377
• Number of slices to send:
Optional 'thank-you' note:
I don't know which algorithm to use. Sorry. What I can tell you however is that a recurring fraction a/b will recur in less than b places. So 1/7 has 6 figures in its recurrence.

You won't manage it easily with any of the Java inbuilt types; float has less precision than double and BigDecimal needs to be told the precision before trying division. I think you need to get a String representation of your number.

Darryl Burke
Bartender
Posts: 5167
11
• Number of slices to send:
Optional 'thank-you' note:

What I can tell you however is that a recurring fraction a/b will recur in less than b places.

Hmm.. didn't know that, thanks. Isn't it also true that a rational number will either be a terminating or a recurring decimal? that is, it will never be both non-terminating and non-recurring?? If so, using BigDecimal with an appropriate scale, the non-terminating decimals can be caught by the ArithmeticException generated. Yea, I know, programming by exception and all that, but the alternative is to reinvent the wheel.. to find out how BigDecimal throws the exception and use the same algorithm.

[ May 11, 2008: Message edited by: Darryl Burke ]

Campbell Ritchie
Marshal
Posts: 79260
377
• Number of slices to send:
Optional 'thank-you' note:
Programming by Exception?

If you try dividing, what you get is a quotient, which in integer arithmetic is equivalent to i/j, and a remainder, which is i%j. The next time you try dividing, you do it on the remainder. The remainder is either the same as it was last time, or different. (!)

Try dividing 100000000000000000000000000000000000000000000000000000000000000000000000000000 by 9 with a pencil and paper and you see the remainder always comes out as 1. So the recurring decimal number will always be the same.

Try dividing 100000000000000000000000000000000000000000000000000000000000000000000000000000 by 7 with a pencil and paper and you see the remainder is 3 then 2 then 6 then 4 then 5 then 1
and when you get to 1 you start again.

Since the remainder when you divide i/j is never >= j, you will get back to a remainder of 1 in not more than j-1 stages, so your recurrence can never be longer than j-1.

And yes, a rational division always either terminates or recurs, not both. termination means you eventually reach a remainder of 0. That can only happen in decimal arithmetic when the divisor (=denominator) only has 2 and 5 as its factors, repeated any number of times.

Your app correctly picks up which divisions recur and which terminate, but I thought you were after something more.

Jeanne Boyarsky
author & internet detective
Posts: 41878
909
• Number of slices to send:
Optional 'thank-you' note:

Originally posted by Sam Benry:
@Jeanne Boyarsky
so you suggest changing the declaration? float maybe? or something else?

I wasn't actually suggesting anything, just pointing something out.

That said, knowing that a decimal recurs (using the method in this thread) makes it possible to find the recurring cycle. You can ignore the last digit when finding the recurring cycle. If you didn't already know it recurred this wouldn't work of course.

arulk pillai
Author
Posts: 3473
• Number of slices to send:
Optional 'thank-you' note:
Did you have a look at the BigDecimal in the java.math package?

Garrett Rowe
Ranch Hand
Posts: 1296
• Number of slices to send:
Optional 'thank-you' note:
Campbell Ritchie: Your app correctly picks up which divisions recur and which terminate, but I thought you were after something more.

I think the OP is after something more. I believe he wants the length of the recurring cycle. One possible way is to code in the long division. You can keep track of the numbers you've already divided using a Map<Integer, Integer>.

I've purposely left out the details of the long division or the looping structure, but I hope you get the idea.
[ May 11, 2008: Message edited by: Garrett Rowe ]

Campbell Ritchie
Marshal
Posts: 79260
377
• Number of slices to send:
Optional 'thank-you' note:
That Map trick sounds a good idea, Garrett Rowe.

Sam Benry
Ranch Hand
Posts: 89
• Number of slices to send:
Optional 'thank-you' note:
thanks for your posts, I never used maps before, and I can't seem to find a clear tut the teaches how to use them, could you please give me a link to explain how to use maps?

thanks

Purushoth Thambu
Ranch Hand
Posts: 425
• Number of slices to send:
Optional 'thank-you' note:
If you are looking for algorithm take a look at wiki. Look at the section "Fractions with prime denominators". This explains how we can easily look for the pattern.

 Consider Paul's rocket mass heater.