24

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.

  • 2
    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 '13 at 5:02
10

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.

8

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.

  • 1
    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 '13 at 11:01
  • 4
    It fails cases like 1/6 or 5/12 :\ – razpeitia Nov 11 '13 at 6:08
  • 1
    @razpeitia I've made something similar, but working in all cases (including integer division). Check out: codepad.org/hKboFPd2 – Tigran Saluev Apr 7 '17 at 20:03
  • I've made a javascript implementation similar to @TigranSaluev's at github.com/Macil/cycle-division – Macil Oct 7 '18 at 9:28
2

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.

  • 4
    "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 '13 at 5:04
  • @Sparr The length of the repetition is always smaller than the denominator. – user40980 Mar 28 '13 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 '13 at 14:13
  • @Sparr math.stackexchange.com/questions/298844/… though I find everything2.com/title/recurring+decimal more readable. – user40980 Mar 28 '13 at 14:15
  • I don't think that the algorithm you link to would work without modification. It includes repetitions which overlap and it searches all over the string (not just for consecutive matches). E.g., the longest repeated substring in "banana" is "ana". – Web_Designer Jun 2 '17 at 0:02

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