Hi folgendes Problem: Gegeben ist ein rationaler und immer teilerfremder Bruch wie zB. 32910 / 24703 = 1,332226855038 Die Summe aus Zähler und Nenner ist 32910 + 24703 = 57613. Nun soll dieser Bruch reduziert werden so das die Summe aus Zähler und Nenner <= 32768 wird aber das Teilerverhältnis mit kleinstem Fehler gefunden wird. In meinem Beispiel wäre das der Bruch: 14047 / 10544 = 1,332226858877, 14047 + 10544 = 24591 <= 32768. Fehlerabweichung wäre demnach +0,00000351. Bisher benutze ich eine Brute Force Suche indem ich alle Nenner von 1 bis 14050 durchrechne und den Bruch mit dem kleinsten Fehler suche. Das ist ineffizient. Ich suche einen Algorithmus der möglichst binär und mit wenigen Divisionen sich dem besten Bruch in quadratischer Zeit annähern könnte. Hat jemand Ideen dazu? Gruß Hagen
Hagen R. schrieb: > Ich suche einen Algorithmus der möglichst binär und mit wenigen > Divisionen sich dem besten Bruch in quadratischer Zeit annähern könnte. Dein Ansatz läuft doch in quadratischer Zeit.
Ich wuerde die 32768 nehmen und durch den 1+Quotienten teilen. Das waer dann der Startwert. Von da dann Bresenham-maessig verkleinern bis der Fehler minimal ist. Ob man mit einer quadratischen Verkleinerung durchkommt wuesst ich grad nicht. Denke nicht.
:
Bearbeitet durch User
D. I. schrieb: > Hagen R. schrieb: >> Ich suche einen Algorithmus der möglichst binär und mit wenigen >> Divisionen sich dem besten Bruch in quadratischer Zeit annähern könnte. > > Dein Ansatz läuft doch in quadratischer Zeit. Ähm Ja ;) Ich meinte es in Richtung das er bei jedem Schritt sich um 1 Bit dem gewünschten Resultat annähert, also in maximal 15 Iterationen das best mögliche Resultat gefunden hat, sorry für die Verwirrung. Gruß hagen
Oh D. schrieb: > Ich wuerde die 32768 nehmen und durch den 1+Quotienten teilen. Das waer > dann der Startwert. Das mache ich schon, der Wert "1 bis 14050" kommt daher. > Von da dann Bresenham-maessig verkleinern bis der > Fehler minimal ist. Hm, das scheint nicht zu gehen bzw. ich verstehe deinen Ansatz noch nicht. Ich finde nämlich keinen Ansatz wie ich die Suchrichtung und Schrittweite ermitteln soll. Ich habe mit verschiedenen Testfällen durchgetestet (ggT, erw. ggT, Faktorization, binär etc.pp.) und keine Logik gefunden wie ich mich auf direktem Wege dem besten Bruch annähern kann. Zur Verifikation habe ich natürlich die Brute Force Methode benutzt. Das Problem als solches sollte nicht unbekannt sein da ich meine das es bei verschiedenen Problemstellungen von Relevanz sein sollte. (Fraktional Teiler etc.pp.) Gruß Hagen
Hagen R. schrieb: > Ähm Ja ;) Ich meinte es in Richtung das er bei jedem Schritt sich um 1 > Bit dem gewünschten Resultat annähert, also in maximal 15 Iterationen > das best mögliche Resultat gefunden hat, sorry für die Verwirrung. > > Gruß hagen Das wäre dann ein Algorithmus in logarithmischer Zeit. Woher kommt die Anforderung das in logarithmischer Zeit zu lösen?
D. I. schrieb: > Hagen R. schrieb: >> Ähm Ja ;) Ich meinte es in Richtung das er bei jedem Schritt sich um 1 >> Bit dem gewünschten Resultat annähert, also in maximal 15 Iterationen >> das best mögliche Resultat gefunden hat, sorry für die Verwirrung. >> >> Gruß hagen > > Das wäre dann ein Algorithmus in logarithmischer Zeit. Woher kommt die > Anforderung das in logarithmischer Zeit zu lösen? ;) um Rechenzeit zu optimieren? Ob nun in logarithmischer Zeit oder ein bischen langsammer ist egal, Hauptsache nicht so wie jetzt per Brute Force Suche aller Nenner < 2^15 und mit mehreren Divisonen/Vergleichen pro Iteration. Kannst du sonst nochwas Konstruktives beitragen? Gruß Hagen
Hagen R. schrieb: > Kannst du sonst nochwas Konstruktives beitragen? Ein linearer Ansatz waere ausgehend vom Ursprungbruch sukzessiv Zaehler / Nenner zu dekrementieren jenachdem in welche Richtung sich der Fehler entwickelt und dann das beste Ergebnis nehmen welches die Anforderung < 2^15 erfuellt. Worst-Case Zeit ist dann O(z+n) Wenn du auf logarithmische Zeit willst laeuft es im wesentlichen darauf raus binaere / ternaere Suche anzuwenden. Dafuer brauchst du dann aber eine griffige Funktion für deine Fehlerberechnung die am besten nur von einer Variable abhaengt und die Anforderungen fuer solche Sucharten erfuellt.
D. I. schrieb: > Hagen R. schrieb: >> Kannst du sonst nochwas Konstruktives beitragen? > > Ein linearer Ansatz waere ausgehend vom Ursprungbruch sukzessiv Zaehler > / Nenner zu dekrementieren jenachdem in welche Richtung sich der Fehler > entwickelt und dann das beste Ergebnis nehmen welches die Anforderung < > 2^15 erfuellt. Ich glaube das geht nicht. Um bei meinem Bespiel zu bleiben poste ich mal den Anfang der sortierten Tabelle aller möglichen Brüche: Am Anfang der Tabelle steht das Optimimum von 14047 / 10544: M1: 14047, M2: 10544, F: 0,000000003839 M1: 9231, M2: 6929, F: 0,000000017527 M1: 18462, M2: 13858, F: 0,000000017527 M1: 4816, M2: 3615, F: 0,000000022396 M1: 9632, M2: 7230, F: 0,000000022396 M1: 14448, M2: 10845, F: 0,000000022396 M1: 13646, M2: 10243, F: 0,000000031616 M1: 18061, M2: 13557, F: 0,000000038818 M1: 14849, M2: 11146, F: 0,000000047214 M1: 10033, M2: 7531, F: 0,000000059128 M1: 4415, M2: 3314, F: 0,000000061076 M1: 8830, M2: 6628, F: 0,000000061076 M1: 13245, M2: 9942, F: 0,000000061076 M1: 17660, M2: 13256, F: 0,000000061076 M1: 15250, M2: 11447, F: 0,000000070728 M1: 17259, M2: 12955, F: 0,000000084368 M1: 12844, M2: 9641, F: 0,000000092374 M1: 5217, M2: 3916, F: 0,000000093036 M1: 10434, M2: 7832, F: 0,000000093036 M1: 15651, M2: 11748, F: 0,000000093036 M1: 8429, M2: 6327, F: 0,000000108768 M1: 16858, M2: 12654, F: 0,000000108768 M1: 16052, M2: 12049, F: 0,000000114229 Wie man sieht besteht das Problem darin bei der Suche die richtige Richtung zu ermitteln. Desweiteren kann man erkennen das es Gruppen gibt mit gleichem Fehler, wie hier: M1: 4816, M2: 3615, F: 0,000000022396 M1: 9632, M2: 7230, F: 0,000000022396 M1: 14448, M2: 10845, F: 0,000000022396 Logisch da die Zähler/Nenner nur ein Mehrfaches von 2 und 3 sind. Das lässt mich schließen das man diese "Suchpfade" bei der Suche von vornherein ausschließen könnte, ergo: die Suche sich beschleunigen lassen muß. Aber ich finde keinen Weg die Richtung, ausgehend vom aktuellen Fehler, in welche ich nun die Zähler/Nenner verändern muß, zu bestimmen. Gruß hagen
Was du suchst ist unter dem Begriff sukzessiven Approximation zu finden. Bei diesem Verfahren Verfahren wird der Definitionsbereich halbiert und geprüft ob das Ergebnis sich dem Optimum nähert oder nicht. je nach dem wird im nächsten schritt der als nächstes die hälfte des Definitionsbereiches betrachtet welche sich dem Optimum nähert. diese verfahren eignet sich für die bitweise optimierung vom MSB zum LSB hin siehe z.B ADU sukzessive Approximation. Dein Kriterium ist freilich der gewünschte Quotient und und nicht ein Analogwert mit welchem zu vergleichen ist. Namaste
Hi Winfried, das geht eben nicht. Hier mal der Tabellenausschnit der Brüche die sich um das Optimum befinden: M1: 14037, M2: 10537, F: 0,000064000335 M1: 14038, M2: 10537, F: 0,000030903337 M1: 14039, M2: 10538, F: 0,000000626152 M1: 14040, M2: 10538, F: 0,000094268515 M1: 14040, M2: 10539, F: 0,000032149658 M1: 14041, M2: 10539, F: 0,000062736005 M1: 14041, M2: 10540, F: 0,000063667182 M1: 14042, M2: 10540, F: 0,000031209478 M1: 14043, M2: 10541, F: 0,000000311067 M1: 14044, M2: 10541, F: 0,000094556593 M1: 14044, M2: 10542, F: 0,000031825632 M1: 14045, M2: 10542, F: 0,000063033029 M1: 14045, M2: 10543, F: 0,000063334218 M1: 14046, M2: 10543, F: 0,000031515445 M1: 14046, M2: 10544, F: 0,000094836828 M1: 14047, M2: 10544, F: 0,000000003839 M1: 14048, M2: 10545, F: 0,000031501790 M1: 14049, M2: 10545, F: 0,000063329884 M1: 14049, M2: 10546, F: 0,000063001444 M1: 14050, M2: 10546, F: 0,000031821238 M1: 14050, M2: 10547, F: 0,000094495125 M1: 14051, M2: 10547, F: 0,000000318566 M1: 14052, M2: 10548, F: 0,000031178132 M1: 14053, M2: 10548, F: 0,000063626570 M1: 14053, M2: 10549, F: 0,000062668859 M1: 14054, M2: 10549, F: 0,000032126856 M1: 14054, M2: 10550, F: 0,000094153616 Angenommen ich befinde mich bei der Suche bei: M1: 14053, M2: 10548, F: 0,000063626570 gehe ich nach oben finde ich: M1: 14052, M2: 10548, F: 0,000031178132 nach unten: M1: 14053, M2: 10549, F: 0,000062668859 Beide haben einen kleineren Fehler, also welche Richtung gehe ich nun? Gruß Hagen
Hagen R. schrieb: > Ich glaube das geht nicht. Um bei meinem Bespiel zu bleiben poste ich > mal den Anfang der sortierten Tabelle aller möglichen Brüche: Glaubst du oder weißt du? Mein Testprogramm spuckt deine Lösung aus. Dein Denkfehler ist, dass du vom Fehlerbetrag ausgehst. Ich gucke nur ob der Fehler positiv oder negativ ist und adaptiere dann.
Den Fall, dass Quotient 0 ist müsste man noch abfangen, das tut mein Programm nicht. Edit: eine Optimierung wäre noch wenn man Zähler und Nenner erstmal an den Summenthreshold runterprügelt in einem Schritt, dann ist die Laufzeit O(threshold) aber immer noch linear.
cs --- > console script ? welches programm / app erzeugt dieses Format? im Übriegen ist das exakt die imho richtige Umsetzung. Namaste
D. I. schrieb: > Hagen R. schrieb: >> Ich glaube das geht nicht. Um bei meinem Bespiel zu bleiben poste ich >> mal den Anfang der sortierten Tabelle aller möglichen Brüche: > > Glaubst du oder weißt du? Mein Testprogramm spuckt deine Lösung aus. > Dein Denkfehler ist, dass du vom Fehlerbetrag ausgehst. Ich gucke nur ob > der Fehler positiv oder negativ ist und adaptiere dann. Also das mit dem Fehler-vorzeichen habe ich auch schon probiert und das hat nicht funktioniert. Wie sieht dein Algorithmus konkret aus? Ansonsten bin ich auf die CFE (Kettenbruchentwicklung) gestoßen. Auf mein Beispiel und obige sortierte Tabelle bezogen: 32910/24703 has CF [1; 3, 100, 11, 1, 2, 2] 14047/10544 has CF [1; 3, 100, 11, 1, 2] 9231/ 6929 has CF [1; 3, 100, 11, 2] 4816/ 3615 has CF [1; 3, 100, 12] Ausgangsbasis ist der Bruch 32910/24703. Bestes Ergbnis ist der Bruch 14047/10544. Nachfolgende werden immer schlechter. Also müsste ich doch nur die CFE(32910/24703) berechnen und von hinten beginnend ein Element nach dem anderen entfernen. Naja, muß mich erstmal weiter einarbeiten. Gruß Hagen
Winfried J. schrieb: > welches programm / app erzeugt dieses Format? C# Hagen R. schrieb: > Also das mit dem Fehler-vorzeichen habe ich auch schon probiert und das > hat nicht funktioniert. Wie sieht dein Algorithmus konkret aus? Siehe mein Beitrag mit dem Anhang.
Hagen R. schrieb: > Also müsste ich doch nur die CFE(32910/24703) berechnen und von hinten > beginnend ein Element nach dem anderen entfernen. Ja, aber Kettenbruchmethode hat eine andere Laufzeit, siehe Wiki Kettenbruchmethode
Wenn Yalu den Thread entdecken sollte, wird er bestimmt eine fundiertere Antwort liefern können als ich, da er in mathematischen Dingen stärker ist.
Die viel interessantere Frage ist noch: Dürfen Zähler und Nenner negativ sein? Dann kannst du nämlich bis in die Unendlichkeit ausprobieren, wenn es keinen Threshold nach unten gibt für die Summe.
D. I. schrieb: > Die viel interessantere Frage ist noch: Dürfen Zähler und Nenner > negativ > sein? Dann kannst du nämlich bis in die Unendlichkeit ausprobieren, wenn > es keinen Threshold nach unten gibt für die Summe. Nein. Habe deine Algo. gerade mal in der Zerre und teste ihn. Danke erstmal. Eine Optimierung ist auf alle Fälle schonmal möglich: man kann die Startbedigungen direkt so berechnen das man Denom+Nom <= 2^15 berechnen kann. Ein weitere Optimierung ist der Verzicht auf Fließkommaberechnungen. Gruß hagen
Hagen R. schrieb: > Eine Optimierung ist auf alle Fälle schonmal möglich: man kann > die Startbedigungen direkt so berechnen das man Denom+Nom <= 2^15 > berechnen kann. Ja das hatte ich ja schon erwähnt. Hagen R. schrieb: > Ein weitere Optimierung ist der Verzicht auf > Fließkommaberechnungen. Sicher, ja. Mein Programm ist fern jeglicher Qualitätskontrolle. Einfach schnell in 10 Minuten hingerotzt ohne weitere Randfallbetrachtung etc... aber dein Fall wurde korrekt berechnet ;)
Jo, und es ist nicht besser als die lineare Suche, leider. Die Anzahl an Iterationen beträgt für mein Beispiel 32766 bei geänderten Startbedigungen. decimal t = 32768 / (32910 + 24703); nom = 32910 * t; denom = 24703 * t; Gruß hagen
Naja linear bleibt linear. Zum Tragen käme das erst spürbar wenn Zähler und Nenner entsprechend groß sind. Wie gesagt O(z+n) vs O(threshold) ist beides linear.
Das mit der CFE wird schneller sein denke ich, bin noch am basteln.
Hagen R. schrieb: > Das mit der CFE wird schneller sein denke ich, bin noch am basteln. Kettenbruchentwicklung (Continued Fractions) ist meines Wissens das beste was du machen kannst, da die daraus resultierenden Brüche in gewisser Hinsicht "optimale" Näherungen sind (es gibt keine besseren Näherungen bei denen der Nenner kleiner ist). Ich hänge mal ein Python-Skript an, das das Zeugs berechnet. Sorry, das ist ein Bastel-Skript mit ohne Kommentaren und nicht besonders aufgeräumt, aber es tut mir immer wieder mal sinnvolle Dienste. Die Laufzeit ist linear zur Anzahl der Elemente in der Kettenbruchentwicklung. Viele Grüße, Simon
Hi Simon, Danke für deine Bestätigung, bin schon am Umsetzen in einen Algorithmus. So wie es aussieht wird das super funktionieren und die Anzahl an Iterationen ist super gering im Vergleich zu den bisherigen Lösungen. Beispiel 198370/147321: 1: 1-1, 2: 3-2, 1: 4-3, 7: 31-23, 1: 35-26, 3: 136-101, 4: 579-430, 1: 715-531, 5: 4154-3085, 2: 9023-6701, 1: 13177-9786, 4: 61731-45845, 3: 198370-147321 Bestes Ergebnis 13177/9786, Anzahl an Iterationen gerade mal 11. Beispiel 24770/18441: 1: 1-1, 2: 3-2, 1: 4-3, 10: 43-32, 1: 47-35, 1: 90-67, 2: 227-169, 4: 998-743, 2: 2223-1655, 1: 3221-2398, 7: 24770-18441 Bestes Ergebnis 18328/13645. Hier muß im letzten Schritt abgebrochen werden und der Multiplikator bis auf 5 dekrementiert werden. Ich denke es wird auf einen rekursiven Algorithmus abzielen. Allerdings bin ich mir nicht sicher unter welchen Rahmenbedingungen ich immer das beste Resultat erreichen werde. Gruß hagen
Hagen R. schrieb: > Allerdings bin ich mir nicht sicher unter welchen Rahmenbedingungen ich > immer das beste Resultat erreichen werde. Für deinen Anwendungsfall liefert die Kettenbruchentwicklung nicht immer das beste Ergebnis. Einfaches Beispiel: Gesucht ist der beste rationale Näherung p/q für √2 mit p+q ≤ 50. Die Kettenbruchentwicklung liefert die Brüche
1 | p / q p+q |
2 | ————————————— |
3 | 1 / 1 2 |
4 | 3 / 2 5 |
5 | 7 / 5 12 |
6 | 17 / 12 19 |
7 | 41 / 29 70 |
8 | ... |
9 | ————————————— |
Der letzte Bruch überschreitet die Grenze für p+q, also würde der Algorithmus 17/12 ausgeben, was einen Fehler von 2,453E-3 hat. Die beste Näherung ist aber 24/17 mit einem Fehler von nur 2,449E-3. Wie Simon schon geschrieben hat, gilt für die Ergebnisse aus dem Kettenbruchverfahren zwar: Simon B. schrieb: > es gibt keine besseren Näherungen bei denen der Nenner kleiner ist Allerdings liefert das Verfahren nicht alle Brüche mit dieser Eigenschaft. So lässt es im obigen Beispiel 24/17 aus.
:
Bearbeitet durch Moderator
Yalu X. schrieb: > Die beste Näherung ist aber 24/17 mit einem Fehler von nur 2,449E-3. Puh, das hat mein Programm geliefert :D
Yalu X. schrieb: > Gesucht ist der beste rationale Näherung p/q für √2 mit p+q ≤ 50. > > Die Kettenbruchentwicklung liefert die Brüche Jetzt wärs interessant zu wissen ob diese Diskrepanz nur bei irrationalen Qoutienten auftritt oder auch bei rationalen.
D. I. schrieb: > Jetzt wärs interessant zu wissen ob diese Diskrepanz nur bei > irrationalen Qoutienten auftritt oder auch bei rationalen. Genau dasselbe Problem tritt auch bei 1.414 auf.
Je grösser der Nenner, desto kleiner der Fehler, wenn Zähler und Nenner teilerfremd sind. Beweis? Also sollte man auch die Zwischenergebnisse kürzen.
Yalu X. schrieb: > Hagen R. schrieb: >> Allerdings bin ich mir nicht sicher unter welchen Rahmenbedingungen ich >> immer das beste Resultat erreichen werde. > > Für deinen Anwendungsfall liefert die Kettenbruchentwicklung nicht immer > das beste Ergebnis. > > Einfaches Beispiel: > > Gesucht ist der beste rationale Näherung p/q für √2 mit p+q ≤ 50. Mein bisheriger Algo. angewendet auf dein Beispiel liefert: 1: 1/1 (2) 2: 3/2 (5), 1: 2/1 (3) 2: 7/5 (12), 1: 4/3 (7) 2: 17/12 (29), 1: 10/7 (17) 2: 41/29 (70), 1: 24/17 (41) 24/17 ist mit dabei ;) Ich habe als Input 41/29 und erzeuge die CFE iterativ. Schon bei der Zerlegung erzeuge ich parallel die neuen Zähler und Nenner solange bis ich das Maximum überschreite. Die CFE für 41/29 ist [1,2,2,2,2], an der letzten Stelle steht 2. Da das zu einem Bruch von 41/29 (70) führt reduziere ich den Muliplikator um -1 bis er auf 1 ist. Und somit komme ich auf eine CFE von [1,2,2,2,1] was 24/17 entspricht. Gruß hagen
Yalu X. schrieb: > Simon B. schrieb: >> es gibt keine besseren Näherungen bei denen der Nenner kleiner ist > > Allerdings liefert das Verfahren nicht alle Brüche mit dieser > Eigenschaft. So lässt es im obigen Beispiel 24/17 aus. Stimmt, das ist mir auch nachträglich noch aufgefallen: Die Kettenbruchentwicklung liefert sehr gute Kandidaten für kleine Zähler und Nenner, aber das Kriterium dass die Summe der beiden unter einem gewissen Wert bleibt berücksichtigt sie überhaupt nicht. Ich hatte eben noch die Idee, dass man ja einfach Zähler und Nenner mit (Maximalwert) / (Zähler+Nenner) multiplizieren könnte, aber das Ergebnis war auch nicht gut: Man bekommt so den maximal möglichen Nenner, das heißt aber nicht, dass es nicht noch bessere Approximationen mit kleinerem Nenner gäbe (In Yalus Beispiel landet man bei 29/21, 24/17 ist aber besser). Das mit dem Runterzählen des letzten Kettenbruch-Elements ist ein spannender Ansatz, meine Zahlentheorie-Vorlesung ist aber zu lange her, um das wirklich beurteilen zu können. Es könnte allerdings sein, dass man da in eine Falle läuft, wenn dieses plötzlich deutlich größer ist, als die vorhergehenden: Beispiel: Wir approximieren 1.33333330000: 1: 1/1 (2) 2: 4/3 (7) 3: 13333333/10000000 (23333333) Die Kettenbruchentwicklung ist [1; 3, 3333333]. Wenn Du da jetzt naiv runterzählst, bist Du ein Weilchen beschäftigt... (man kann da vielleicht irgendwas Intervallschachtelungstechnisches einbauen, könnte aber lästig werden...) Viele Grüße, Simon
Ich bin mir nicht sicher ob ich euch richtig verstanden habe. Ihr geht von einer vorwärtsgerichteten Kettenbruchentwicklung aus. Ich gehe aber von einem gegebenen Bruch (32Bit/32Bit) aus und erzeuge die CFE und gleichzeitig den neuen Bruch. Im Pseudocode
1 | BestError = MaxRange; |
2 | Limit = 32768; |
3 | Zi = 199070; |
4 | Ni = 146631; |
5 | Qi = Zi / Ni; |
6 | Zx = Zi; |
7 | Nx = Ni; |
8 | Zr = Zi; |
9 | Nr = Ni; |
10 | Z0 = 1; |
11 | Z1 = 0; |
12 | N0 = 0; |
13 | N1 = 1; |
14 | repeat |
15 | Swap(Z0, Z1); |
16 | Swap(N0, N1); |
17 | |
18 | Q = Zx div Nx; // Q als Ausgabe ergibt CFE[Z/N] |
19 | R = Zx mod Nx; |
20 | Zx = Nx; |
21 | Nx = R; // swap Zx<->Nx |
22 | |
23 | for q = Q downto 1 do |
24 | begin |
25 | Z2 = Z0 + Z1 * q; |
26 | N2 = N0 + N1 * q; |
27 | if Z2 + N2 <= Limit then |
28 | begin |
29 | Error = Abs(Qi - Z2 / N2); |
30 | if Error < BestError then |
31 | begin |
32 | BestError = Error; |
33 | Zr = Z2; |
34 | Nr = N2; |
35 | end; |
36 | end; |
37 | end; |
38 | |
39 | Z0 = Z0 + Z1 * Q; |
40 | N0 = N0 + N1 * Q; |
41 | until (R = 0) or (Z0 + N0 > Limit); |
Jetzt muß ich noch überprüfen ob es in allen Fällen korrekt funktioniert und dann die Divisionen/Multiplikationen weg optimieren. Gruß hagen
Simon B. schrieb: > Die Kettenbruchentwicklung ist [1; 3, 3333333]. > > Wenn Du da jetzt naiv runterzählst, bist Du ein Weilchen beschäftigt... Ok, da muß ich noch meinen Algo. optimieren stimmt ;) Vielleicht Q faktorisieren? Gruß hagen
Hier ist der Vorschlag für einen auf Farey-Folgen basierenden Ansatz:
1 | The code takes a number x between 0 and 1 and a maximum denominator size N. |
2 | It returns the numerator and denominator of the best rational approximation |
3 | to x using denominators no larger than N. |
http://www.johndcook.com/blog/2010/10/20/best-rational-approximation/ Zahlen außerhalb von von [0,1] können einfach aud diesen Fall zurückgeführt werden.
...im Endeffekt wohl binäre "Suche" in einem Stern-Brocot-Baum, wo immer nur 2 Werte mitgeführt werden: der nächste kleinere Bruch und der nächste größere Bruch. https://en.wikipedia.org/wiki/Stern–Brocot_tree#Mediants_and_binary_search
:
Bearbeitet durch User
Ich habe jetzt mal grob beide Algorithmen umgesetzt, also CFE und Stern-Brocot-Tree. Beide sind noch nicht ganz sauber aber es gibt ein interessantes Resultat: die Anzahl an Iterationen ist bei beiden durchschnittlich fast gleich, aber bei bestimmten Brüchen benötigt CFE wesentlich weniger Schritte. Im Falle von 13333333/10000000 benötigt CFE 4684 und Stern-Brocot 4685 Schritte. Aber in der CFE kann ich diesen Fall weiter enorm beschleunigen. Dafür lässt sich Stern-Brocot besser ohne viele Divisionen implementieren. Gruß hagen
Danke Leute, sehr spannend. Ein Thread, der einen Stern bekommen sollte.
Hi ich habe mich jetzt für die CFE Methode entschieden. Man kann zwar die Methode nach Stern-Brocot soweit optimieren das sie mit nur 6 Variablen und ausschließlich Additionen+Vergleichen auskommt, aber die durchschnittliche Anzahl an Iterationen ist bei der CFE besser. In solchen Extremfällen wie 13333333/10000000 benötigt die CFE nur 3 Iterationen die Stern-Brocot aber bis zu 3333337 Iterationen. Durchschnittlich betrachtet ist die Stern-Brocot Methode, gerade in Assembler, performanter. Aber in extremen Fällen ist die CFE Methode bedeutend besser und damit hat sie durchschnittlich betrachtet eine gleichmäßigere Konvergenz. Letztendlich ist die CFE Methode um Magnituden performanter als die bisherige Brute Force Methode. Gruß hagen
:
Bearbeitet durch User
Hi hier noch der finale Pseudocode. Das Problem mit solchen Brüchen wie 133333333/10000000 ist beseitigt, siehe Berechnung von T (Division wird in 27% aller Fälle aufgerufen). Alles ohne Fließkommaberechnungen und pro Iteration eine Integer Division mit modularem Rest. In 11% der Fälle muß am Ende der Berechnung noch ein Vergleich durchgeführt werden für den eine Integer Division und 5 Multiplikationen nötig sind. Schön wäre es noch gewesen wenn ich den finalen Vergleich F < G und deren Berechnung ebenfalls noch weg optimieren könnte. Gruß Hagen
1 | function Reduce(var Zr,Nr; const Zi,Ni,Limit): Boolean; |
2 | begin |
3 | Result = False; |
4 | Zx = Zi; // Input Zi/Ni |
5 | Nx = Ni; |
6 | Zr = 1; // Output Zr/Nr |
7 | Nr = 1; |
8 | Z1 = 0; |
9 | Z2 = 1; |
10 | N1 = 1; |
11 | N2 = 0; |
12 | repeat |
13 | Z0 = Z1; Z1 = Z2; |
14 | N0 = N1; N1 = N2; |
15 | |
16 | Q = Zx div Nx; |
17 | R = Zx mod Nx; |
18 | |
19 | Zx = Nx; |
20 | Nx = R; |
21 | |
22 | Z2 = Z0 + Z1 * Q; |
23 | N2 = N0 + N1 * Q; |
24 | |
25 | if Z2 + N2 <= Limit then |
26 | begin |
27 | Zr = Z2; |
28 | Nr = N2; |
29 | Result = True; |
30 | end else |
31 | begin |
32 | T = -(Z0 + N0 - Limit) div (Z1 + N1); |
33 | if (T > 0) and (T >= (Q +1) div 2) then |
34 | begin |
35 | Z2 = Z0 + Z1 * T; |
36 | N2 = N0 + N1 * T; |
37 | F = Abs(Zi * N2 - Ni * Z2); |
38 | G = (Abs(Zi * Nr - Ni * Zr) * N2) div Nr; |
39 | if F < G then |
40 | begin |
41 | Zr = Z2; |
42 | Nr = N2; |
43 | Result = True; |
44 | end; |
45 | end; |
46 | Break; |
47 | end; |
48 | until R = 0; |
49 | return Result; |
50 | end; |
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.