quel est un moyen efficace de trouver des décimales répétitives

J'essaie de trouver un algorithme efficace en Java pour trouver la partie décimale répétitive de deux entiers aet boù a/b.

par exemple. 5/7 = 0,714258 714258 ....

Je ne connais actuellement que la méthode de la division longue.

Je crois qu'il y a deux approches générales ici, vous pouvez essentiellement rechercher par "force brute" la chaîne répétitive la plus longue, ou vous pouvez la résoudre comme un problème de théorie des nombres.

Cela fait longtemps que je n'ai pas rencontré ce problème, mais un cas spécial (1 / n) est le problème # 26 sur Project Euler, donc vous pourrez peut-être trouver plus d'informations en recherchant des solutions efficaces pour ce nom spécifique. Une recherche nous mène au site Web d'Eli Bendersky, où il explique sa solution . Voici une partie de la théorie de la page Expansion décimale de Mathworld :

Toute fraction non m/nrégulière est périodique et a une période lambda(n)indépendante de m, qui est au plus n-1 longue. Si nest relativement premier à 10, alors la période lambda(n)de m/nest un diviseur de phi(n)et a au plus des phi(n)chiffres, où phiest la fonction totiente. Il s'avère que lambda(n)c'est l' ordre multiplicatif de 10 (mod n) (Glaisher 1878, Lehmer 1941). Le nombre de chiffres dans la partie répétitive de l'expansion décimale d'un nombre rationnel peut également être trouvé directement à partir de l'ordre multiplicatif de son dénominateur.

Ma théorie des nombres est un peu rouillée pour le moment, donc le mieux que je puisse faire est de vous orienter dans cette direction.

Laissez n < d, et vous essayez de comprendre la partie répétitive de n/d. Soit ple nombre de chiffres dans la partie répétitive: alors n/d = R * 10^(-p) + R * 10^(-2p) + ... = R * ((10^-p)^1 + (10^-p)^2 + ...). La partie entre crochets est une série géométrique, égale à 1/(10^p - 1).

Alors n / d = R / (10^p - 1). Réorganisez pour obtenir R = n * (10^p - 1) / d. Pour trouver R, bouclez pde 1 à l'infini et arrêtez dès que la ddivision est égale n * (10^p - 1).

Voici une implémentation 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

( kgarde une trace de la longueur de la séquence répétée, afin que vous puissiez faire la distinction entre 1/9 et 1/99, par exemple)

Notez que cette implémentation (ironiquement) boucle pour toujours si l'expansion décimale est finie, mais se termine si elle est infinie! Vous pouvez vérifier ce cas, car n/dil n'aura une représentation décimale finie que si tous les facteurs premiers dqui ne sont pas 2 ou 5 sont également présents dans n.

Division longue? : /

Transformez le résultat en chaîne, puis appliquez-lui cet algorithme . Utilisez BigDecimal si votre chaîne n'est pas assez longue avec des types ordinaires.