che cosa è un modo efficace per trovare il decimale ricorrente

Credo che ci siano due approcci generali qui, puoi essenzialmente cercare "la forza bruta" per la stringa ripetuta più lunga, oppure puoi risolverlo come un problema di teoria dei numeri.

È passato molto tempo da quando ho riscontrato questo problema, ma un caso speciale (1 / n) è il problema n. 26 su Project Euler, quindi potresti essere in grado di trovare più informazioni cercando soluzioni efficienti per quel nome specifico . Una ricerca ci porta al sito web di Eli Bendersky, dove spiega sua soluzione . Ecco alcuni aspetti della pagina Decimal Expansions di Mathworld

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.

La mia teoria dei numeri è un po 'arrugginita al momento, quindi il meglio che posso fare è indicarti quella direzione.

Lascia n < d e stai cercando di capire la parte ripetitiva di n/d . Lascia che p sia il numero di cifre nella parte che si ripete: quindi n/d = R * 10^(-p) + R * 10^(-2p) + ... = R * ((10^-p)^1 + (10^-p)^2 + ...) . La parte a forcella è una serie geometrica, uguale a 1/(10^p - 1) .

Quindi n / d = R / (10^p - 1) . Riordina per ottenere R = n * (10^p - 1) / d . Per trovare R, loop p da 1 a infinito e fermati non appena d divide equamente n * (10^p - 1) .

Ecco un'implementazione 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 tiene traccia della lunghezza della sequenza ripetitiva, quindi puoi distinguere tra 1/9 e 1/99, per esempio)

Si noti che questa implementazione (ironicamente) si interrompe per sempre se l'espansione decimale è finita, ma termina se è infinita! Puoi verificare questo caso, perché n/d avrà una rappresentazione decimale finita solo se tutti i fattori primi di d che non sono 2 o 5 sono presenti anche in n .

Lunga divisione? : /

Trasforma il risultato in una stringa, quindi applica questo algoritmo . Usa BigDecimal se la tua stringa non è abbastanza lunga con i tipi ordinari.