Was ist ein effizienter Weg, um sich wiederholende Dezimalstellen zu finden

24

Ich versuche, einen effizienten Algorithmus in Java zu finden, um den sich wiederholenden Dezimalteil von zwei Ganzzahlen zu finden aund bwo a/b.

z.B. 5/7 = 0,714258 714258 ....

Ich kenne derzeit nur die Methode der langen Teilung.

Jun Hao
quelle
2
Sie haben also a = 5 und b = 7, und Sie können a / b im Gleitkomma leicht genug berechnen, aber was Sie wissen wollen, ist, dass es nach 6 Dezimalstellen wiederholt wird?
Sparr

Antworten:

10

Ich glaube, dass es hier zwei allgemeine Ansätze gibt, Sie können im Wesentlichen "Brute Force" nach der längsten sich wiederholenden Zeichenfolge suchen oder Sie können es als ein Problem der Zahlentheorie lösen.

Es ist lange her, dass ich auf dieses Problem gestoßen bin, aber ein Sonderfall (1 / n) ist Problem Nr. 26 in Project Euler, sodass Sie möglicherweise mehr Informationen finden, indem Sie nach effizienten Lösungen für diesen bestimmten Namen suchen. Eine Suche führt uns zu Eli Benderskys Website, auf der er seine Lösung erklärt . Hier ist ein Teil der Theorie von Mathworlds Decimal Expansions-Seite :

Jeder unregelmäßige Bruch m/nist periodisch und hat einen von ihm lambda(n)unabhängigen Zeitraum m, der höchstens n-1 Ziffern lang ist. Wenn nes sich um eine Primzahl von 10 handelt, ist die Periode lambda(n)von m/nein Teiler von phi(n)und hat höchstens phi(n)Ziffern, wobei phies sich um die Totientenfunktion handelt. Es stellt sich heraus, dass dies lambda(n)die multiplikative Ordnung von 10 (mod n) ist (Glaisher 1878, Lehmer 1941). Die Anzahl der Stellen im Wiederholungsteil der Dezimalerweiterung einer rationalen Zahl kann auch direkt aus der multiplikativen Reihenfolge ihres Nenners ermittelt werden.

Meine Zahlentheorie ist im Moment ein bisschen verrostet, also ist das Beste, was ich tun kann, Sie in diese Richtung zu lenken.

Daniel B
quelle
8

Lassen Sie n < d, und Sie versuchen, den sich wiederholenden Teil von herauszufinden n/d. Sei pdie Anzahl der Ziffern im Wiederholungsteil: dann n/d = R * 10^(-p) + R * 10^(-2p) + ... = R * ((10^-p)^1 + (10^-p)^2 + ...). Das Klammerteil ist eine geometrische Reihe, gleich 1/(10^p - 1).

Also n / d = R / (10^p - 1). Neu anordnen, um zu bekommen R = n * (10^p - 1) / d. Um R zu finden, gehen Sie pvon 1 bis unendlich und halten Sie an, sobald Sie sich dgleichmäßig geteilt haben n * (10^p - 1).

Hier ist eine Implementierung 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

( kVerfolgt die Länge der Wiederholungssequenz, sodass Sie beispielsweise zwischen 1/9 und 1/99 unterscheiden können.)

Beachten Sie, dass diese Implementierung (ironischerweise) eine Endlosschleife ausführt, wenn die Dezimalerweiterung endlich ist, aber endet, wenn sie unendlich ist! Sie können diesen Fall jedoch überprüfen, da n/dnur dann eine endliche Dezimaldarstellung dvorliegt, wenn alle Primfaktoren , die nicht 2 oder 5 sind, auch in vorhanden sind n.

Valtron
quelle
1
Diese Antwort scheint richtig zu sein. Die Methode basiert auf folgenden "Regeln": 0.123123... = 123/999 0.714258714258... = 714258/999999 (=5/7)usw.
KOMMEN
4
Es scheitert Fälle wie 1/6 oder 5/12: \
Razpeitia
1
@razpeitia Ich habe etwas ähnliches gemacht, arbeite aber in allen Fällen (auch Integer Division). Check out: codepad.org/hKboFPd2
Tigran Saluev
Ich habe eine Javascript - Implementierung ähnlich wie @ TigranSaluev die bei gemacht github.com/Macil/cycle-division
macil
2

Lange Trennung? : /

Verwandeln Sie das Ergebnis in eine Zeichenfolge und wenden Sie diesen Algorithmus darauf an. Verwenden Sie BigDecimal, wenn Ihre Zeichenfolge bei normalen Typen nicht lang genug ist.

Robert Harvey
quelle
4
„Drehen Sie es in einen String“ könnte beliebiger Genauigkeit Berechnungen erfordern und eine sehr lange Zeichenfolge zwei Kopien des sich wiederholenden Teil der Zeichenfolge zu berechnen (und wie Sie wissen, wann 0,121212312121231212123 Berechnung zu stoppen ... wäre ein Problem?)
Sparr
@Sparr Die Länge der Wiederholung ist immer kleiner als der Nenner.
@MichaelT Das war mir nicht bewusst. Wenn dies zutrifft, ist die Genauigkeit nicht genau "willkürlich", sondern kann je nach Nenner beliebig hoch sein.
Sparr
Ich glaube nicht, dass der Algorithmus, mit dem Sie verknüpfen, ohne Änderung funktionieren würde. Es enthält sich überlappende Wiederholungen und durchsucht die gesamte Zeichenfolge (nicht nur nach aufeinanderfolgenden Übereinstimmungen). ZB ist die längste wiederholte Teilzeichenfolge in "Banane" "ana".
Web_Designer