Dezimalbruchentwicklung - Periodizität erkennen
-
Hallo
Ich möchte rationale Zahlen in der Dezimalbruchentwicklung darstellen; Z.B. 31/12 -> 2.58(3)
Für Zahlen mit periodischer Dezimalbruchentwicklung muss man bekanntlich alle bisherigen Zwischenschritte der schriftlichen Division speichern und bei jedem weiteren Schritt den aktuellen Wert mit allen bisherigen vergleichen. Das ist sehr ineffizient, inbesondere für Bignums. Ich stelle mir vor, dass Hashing da zumindest ein wenig Abhilfe schafft, auch wenn nicht viel. Gibt es für dieses Prozedere einen besseren Algorithmus?LG
-
Fytch schrieb:
Für Zahlen mit periodischer Dezimalbruchentwicklung muss man bekanntlich alle bisherigen Zwischenschritte der schriftlichen Division speichern und bei jedem weiteren Schritt den aktuellen Wert mit allen bisherigen vergleichen.
Ist das bekanntlich so? Woher kennt man das denn?
Ich hätte ja jetzt erst einmal mathematisch festgestellt, dass eine rationale Zahl genau dann im Zehnersystem periodisch ist, wenn der Nenner andere Primfaktoren als 2 und 5 enthält.
Und weiter hätte ich dann auf Wikipedia geguckt (oder eigentlich hätte ich längst vorher gucken sollen), und dort dann die Formeln gefunden, wie man diese Dinge ausrechnet:
https://en.wikipedia.org/wiki/Repeating_decimal
Also nichts vonwegen Speichern von Zwischenschritten. Und wenn's dort steht, ist das eigentlich auch "bekannt".
-
"Bekanntlich" war vielleicht eine etwas ungünstige Wortwahl meinerseits. Ich habe dieses Problem auf Stackoverflow recherchiert und alle Lösungen enthielten dieses Speichern der Zwischenschritte der Division, daher ging ich davon aus, dass dies die gängige/bekannte Lösung ist. Ein paar Beispiele: (Name der Array-Variable in Klammern)
https://stackoverflow.com/questions/36529512/convert-fraction-to-string-with-repeating-decimal-places-in-brackets (subresults)
https://stackoverflow.com/questions/29924688/how-to-detect-a-repeating-decimal (remainders)
https://codereview.stackexchange.com/questions/87522/decimal-expansion-of-a-rational-number (remainders)
https://stackoverflow.com/questions/33445238/fraction-to-recurring-decimal (map)Zum Wiki-Artikel: Den habe ich mir schon angeschaut (nicht vollständig durchgelesen), habe aber nichts Verwertbares gesehen.
1.2 ist die im OP angesprochene schriftliche Division; im Absatz wird auch gesagt, man müsse wissen, dass 500 vorher schon einmal der Dividend war. Folglich müsste man doch eine Liste führen mit allen vorherigen Dividenden.
4 & 5 sind nicht von Interesse, weil es da nur um den Fall Zähler=1 geht.
9 ist in erster Linie für den Fall Zähler=1, aber die eine Kongruenzformel sieht interessant aus, die schaue ich mir mal an. Hast du diese gemeint?LG
-
Fytch schrieb:
4 & 5 sind nicht von Interesse, weil es da nur um den Fall Zähler=1 geht.
Doch, die sind super von Interesse! Ein Vielfaches von solch einer Zahl zu haben, ändert schließlich nichts wesentliches.
PS: Es kann letztlich sein, dass die andere Methode für den Computer weniger aufwendig ist. Primfaktorzerlegung ist schließlich nicht ganz ohne. Aber das wäre zumindest erst einmal mein Ansatz, solche Probleme über Zahlentheorie anzugehen, anstatt über die algorithmische Sichtweise. Ob dies wirklich besser ist, kann ich an dieser Stelle noch nicht beurteilen.
