Finding recurring cycle in a decimal.

[Sam Benry]

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]

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]

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]

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]

@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]

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]

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.

import java.math.BigDecimal;
 
public class Recurrence {
   
   public static void main(String[] args) {
      for (int i = 1; i < 100; i++) {
         System.out.println("1 / " + i + " is "
               + (isRecurring(1, i) ? "" : "not")
               + " recurring.");
      }
   }
   
   static boolean isRecurring (int numerator, int denominator) {
      BigDecimal n = new BigDecimal(numerator);
      n.setScale(2 * denominator + 1);
      
      BigDecimal d = new BigDecimal(denominator);
      try {
         n.divide(d);
         return false;
      } catch (ArithmeticException ae) {
         return true;
      }
   }
}

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

[Campbell Ritchie]

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]

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]

Did you have a look at the BigDecimal in the java.math package?

[Garrett Rowe]

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>.

Map<Integer, Integer> myMap //Map of previous divisors to cycle length
 
loop
   if (!myMap.contains(currentDivisor))
      myMap.put(currentDivisor, 0)
      for each key value pair in the map
         add 1 to the value and reinsert with the key
   else
      return myMap.get(currentDivisor)
end loop

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]

That Map trick sounds a good idea, Garrett Rowe.

[Sam Benry]

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]

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.