Win a copy of Head First Android this week in the Android forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
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:
  • Tim Cooke
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Liutauras Vilda
Sheriffs:
  • Jeanne Boyarsky
  • Rob Spoor
  • Bear Bibeault
Saloon Keepers:
  • Jesse Silverman
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Piet Souris
  • Al Hobbs
  • salvin francis

Finding recurring cycle in a decimal.

 
Ranch Hand
Posts: 89
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Marshal
Posts: 74371
334
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
author & internet detective
Posts: 40797
829
Eclipse IDE VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Bartender
Posts: 5167
11
Netbeans IDE Opera Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@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: 74371
334
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Netbeans IDE Opera Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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: 74371
334
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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: 40797
829
Eclipse IDE VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Author
Posts: 3450
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Did you have a look at the BigDecimal in the java.math package?
 
Ranch Hand
Posts: 1296
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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: 74371
334
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That Map trick sounds a good idea, Garrett Rowe.
 
Sam Benry
Ranch Hand
Posts: 89
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Ranch Hand
Posts: 425
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
You showed up just in time for the waffles! And this tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic