27

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.

1
  • 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
    Commented Mar 27, 2013 at 5:02

3 Answers 3

11

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.

4
  • 2
    This answer seems correct. The method is based on following "rule": 0.123123... = 123/999 0.714258714258... = 714258/999999 (=5/7) etc.
    – COME FROM
    Commented Mar 28, 2013 at 11:01
  • 4
    It fails cases like 1/6 or 5/12 :\
    – razpeitia
    Commented Nov 11, 2013 at 6:08
  • 1
    @razpeitia I've made something similar, but working in all cases (including integer division). Check out: codepad.org/hKboFPd2 Commented Apr 7, 2017 at 20:03
  • I've made a javascript implementation similar to @TigranSaluev's at github.com/Macil/cycle-division
    – Macil
    Commented Oct 7, 2018 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.

5
  • 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
    Commented Mar 27, 2013 at 5:04
  • @Sparr The length of the repetition is always smaller than the denominator.
    – user40980
    Commented Mar 28, 2013 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
    Commented Mar 28, 2013 at 14:13
  • @Sparr math.stackexchange.com/questions/298844/… though I find everything2.com/title/recurring+decimal more readable.
    – user40980
    Commented Mar 28, 2013 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". Commented Jun 2, 2017 at 0:02

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