Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 2 down vote favorite

I am trying to find a efficient algorithm in Java to find the repeating decimal part of two integers a and b where a/b.

eg. 5/7 = 0.714258 714258....

I currently only know of the long division method.

share|improve this question
1  
So you have a=5 and b=7, and you can calculate a/b in floating point easily enough, but what you want to know is that it repeats after 6 decimal places? – Sparr Mar 27 at 5:02

3 Answers

up vote 3 down vote accepted

I believe that there are two general approaches here, you can essentially "brute force" look for the longest repeating string, or you can solve it as a problem of number theory.

It's been a long time since I ran across this problem, but a special case (1 / n) is problem #26 on Project Euler, so you may be able to find more information by searching for efficient solutions for that specific name. One search leads us to Eli Bendersky's website, where he explains his solution. Here's some of the theory from Mathworld's Decimal Expansions page:

Any nonregular fraction m/n is periodic, and has a period lambda(n) independent of m, which is at most n-1 digits long. If n is relatively prime to 10, then the period lambda(n) of m/n is a divisor of phi(n) and has at most phi(n) digits, where phi is the totient function. It turns out that lambda(n) is the multiplicative order of 10 (mod n) (Glaisher 1878, Lehmer 1941). The number of digits in the repeating portion of the decimal expansion of a rational number can also be found directly from the multiplicative order of its denominator.

My number theory is a bit rusty at the moment, so the best I can do is point you in that direction.

share|improve this answer
up vote 2 down vote

Let n < d, and you're trying to figure out the repeating part of n/d. Let p be the number of digits in the repeating part: then n/d = R * 10^(-p) + R * 10^(-2p) + ... = R * ((10^-p)^1 + (10^-p)^2 + ...). The bracketed part is a geometric series, equal to 1/(10^p - 1).

So n / d = R / (10^p - 1). Rearrange to get R = n * (10^p - 1) / d. To find R, loop p from 1 to infinity, and stop as soon as d evenly divides n * (10^p - 1).

Here's an implementation in Python:

def f(n, d):
    x = n * 9
    z = x
    k = 1
    while z % d:
        z = z * 10 + x
        k += 1
    return k, z / d

(k keeps track of the length of the repeating sequence, so you can distinguish between 1/9 and 1/99, for example)

Note that this implementation (ironically) loops forever if the decimal expansion is finite, but terminates if it's infinite! You can check for this case, though, because n/d will only have a finite decimal representation if all the prime factors of d that aren't 2 or 5 are also present in n.

share|improve this answer
This answer seems correct. The method is based on following "rule": 0.123123... = 123/999 0.714258714258... = 714258/999999 (=5/7) etc. – COME FROM Mar 28 at 11:01
up vote 1 down vote

Long division? :/

Turn the result into a string, and then apply this algorithm to it. Use BigDecimal if your string isn't long enough with ordinary types.

share|improve this answer
1  
"Turn it into a string" could require arbitrary precision calculations and a very long string to calculate two copies of the repeating part of the string (and how do you know when to stop calculating? .121212312121231212123... would be a problem) – Sparr Mar 27 at 5:04
@Sparr The length of the repetition is always smaller than the denominator. – MichaelT Mar 28 at 14:11
@MichaelT I was not aware of that. If true, the precision is not precisely "arbitrary", but can be arbitrarily high depending on the denominator. – Sparr Mar 28 at 14:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.