¿Cuál es una manera eficiente de encontrar decimales repetidos

Estoy tratando de encontrar un algoritmo eficiente en Java para encontrar la parte decimal repetitiva de dos enteros ay bdónde a/b.

p.ej. 5/7 = 0.714258 714258 ....

Actualmente solo conozco el método de división larga.

Creo que hay dos enfoques generales aquí, esencialmente puedes "fuerza bruta" buscar la cadena de repetición más larga, o puedes resolverlo como un problema de teoría de números.

Ha pasado mucho tiempo desde que me encontré con este problema, pero un caso especial (1 / n) es el problema # 26 en el Proyecto Euler, por lo que puede encontrar más información buscando soluciones eficientes para ese nombre específico. Una búsqueda nos lleva al sitio web de Eli Bendersky, donde explica su solución . Aquí hay algo de la teoría de la página Expansiones decimales de Mathworld :

Cualquier fracción no regular m/nes periódica y tiene un período lambda(n)independiente de m, que es como máximo de n-1 dígitos. Si nes relativamente primo a 10, entonces el período lambda(n)de m/nes un divisor de phi(n)y tiene como máximo phi(n)dígitos, donde phies la función totient. Resulta que lambda(n)es el orden multiplicativo de 10 (mod n) (Glaisher 1878, Lehmer 1941). El número de dígitos en la porción repetida de la expansión decimal de un número racional también se puede encontrar directamente del orden multiplicativo de su denominador.

Mi teoría de los números está un poco oxidada en este momento, así que lo mejor que puedo hacer es señalarlo en esa dirección.

Deja n < d, y estás tratando de descubrir la parte que se repite n/d. Deje pser el número de dígitos en la parte que se repite: entonces n/d = R * 10^(-p) + R * 10^(-2p) + ... = R * ((10^-p)^1 + (10^-p)^2 + ...). La parte entre corchetes es una serie geométrica, igual a 1/(10^p - 1).

Por lo tanto n / d = R / (10^p - 1). Reorganizar para obtener R = n * (10^p - 1) / d. Para encontrar R, repita pde 1 a infinito y pare tan pronto como se ddivida de manera uniforme n * (10^p - 1).

Aquí hay una implementación en 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

( krealiza un seguimiento de la longitud de la secuencia de repetición, por lo que puede distinguir entre 1/9 y 1/99, por ejemplo)

Tenga en cuenta que esta implementación (irónicamente) se repite para siempre si la expansión decimal es finita, ¡pero termina si es infinita! Sin embargo, puede verificar este caso, ya n/dque solo tendrá una representación decimal finita si todos los factores primos dque no son 2 o 5 también están presentes n.

¿División larga? : /

Convierta el resultado en una cadena y luego aplique este algoritmo . Use BigDecimal si su cadena no es lo suficientemente larga con los tipos normales.