I am trying to find a efficient algorithm in Java to find the repeating decimal part of two integers
eg. 5/7 = 0.714258 714258....
I currently only know of the long division method.
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/nis periodic, and has a period
m, which is at most
n-1digits long. If
nis relatively prime to 10, then the period
m/nis a divisor of
phi(n)and has at most
phiis 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.
n < d, and you're trying to figure out the repeating part of
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).
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
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.