|
---|
Ich würde gerne die folgende Formel lösen: a ≈ Das folgende is bekannt: und sind Ganzzahlen. und haben jeweils einen bekannten Wert. und haben unbekannte Werte. Der Unterschied zwischen a und soll gering sein. und müssen beide jeweils einen Wert zwischen 1 und haben. und können beide größer als sein. Die einzige Möglichkeit, welche ich kenne, besteht darin, alle Möglichkeiten durchzuprobieren und nach jedem Probieren einen Vergleich durchführen, ob ich bereits bessere Werte für und gefunden habe. Kennt jemand eine bessere Lösung? Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
Hallo Für ist das Problem ja trivial. Das wirst du nicht meinen. Eine spontane Algorithmus-Einschränkung / Verkürzung, die du vielleicht schon bedacht aber noch nicht benannt hast, ist ja bestimmt, eine Fallunterscheidung zu tätigen: Für den Fall betrachtest du natürlich nur die Zahlen die innerhalb von liegen. Für den Fall betrachtest du natürlich nur die Zahlen die innerhalb von liegen. Aber zugegeben, das ist noch kein großer Fortschritt und immer noch eine elende Sucherei... PS: Und ebenso naheliegend: Algorithmus abbrechen, wenn du eine echte Ganzzahl-Division gefunden hast. |
|
Ja genau, es geht um den Fall, dass oder ist. Achso, ja, danke für den Hinweis, das steht nicht in der Frage: ist bei mir immer deshalb ist automatisch immer . Jemand von Intel hat das Problem so gelöst: while(y Für die Nicht-Programmierer: bedeutet, dass durch 2 geteilt wird. Also quasie wie beim Kürzen. Aber ich glaube dadurch erreicht man nur ein suboptimales Ergebnis, weil die Nachkommastellen bei Ganzzahlen bei jedem Teilen verloren gehen. Außerdem lässt die Schleife noch Potential offen, den Ablauf zu beschleunigen. |
|
Achso, jetzt habe ich es kapiert. Oh man, ich bin so dumm. Ich benutze einfach für und berechne dann . Das ist vielleicht nicht die bestmögliche Kombination von und aber eine relativ schnelle Lösung. |
|
Ich kenne den Syntax nicht, aber wenn "x " tatsächlich praktisch eine Division durch 2 bedeuten sollte, dann bedeutet das doch, dass praktisch nur Möglichkeiten der potenziellen Kandidaten durchprobiert werden. Das ist natürlich schnell, aber noch weit, weit entfernt von "...alle Möglichkeiten durchzuprobieren und nach jedem Probieren einen Vergleich durchführen", um das echte Optimum zu erforschen. |
|
. ist ein Basic-Befehl für kaufmännisch runden. Der Fehlerbetrag ist dann kleinergleich . |
|
Stichwort: Kettenbruchentwicklung mit Abbruch. |
|
@calc007: Ja, das ist richtig. Aber ich dachte ich veröffentliche die suboptimale Lösung als Denkanstoß trotzdem. Die Endlösung ist übrigens aus einer Kombination von Ihrem Denkanstoß (dass lediglich jener Fall gelöst werden muss, in welchem ist) und Intels Lösung entstanden. KartoffelKäfer hat dann noch zur Vervollständigung den maximalen Fehler berechnet. Schritt für Schritt sind wir so zum Ziel gekommen. Das "x 1" bedeutet übrigens: Um 1 Binärstelle nach rechts schieben und entspricht deshalb einer Division durch 2. Für das Ausführen von einem Schiebebefehl ist 1 Maschinenzyklus notwendig. Für die Ausführung von einem Divisionsbefehl sind etwa Maschinenzyklen notwendig. |
|
Stichwort: Stern-Brocot Damit kann man mit geringem Rechenaufwand bei vorgegebener oberer Schranke für den Nenner den optimalen Näherungsbruch für bestimmen. Hier ist sogar ein Python-Skript dafür zu finden: www.matheboard.de/thread.php?postid=2224264#post2224264 Wennn du beispielsweise im verlinkten Skript approx(728194023, 1973482019) aufrufst, dann werden alle besten rationalen Näherungsbrüche von ausgegeben, das sind 1/2 1/3 2/5 3/8 4/11 7/19 24/65 31/84 38/103 69/187 238/645 307/832 376/1019 1059/2870 1435/3889 3246/8797 4681/12686 10797/29261 15478/41947 51115/138527 66593/180474 82071/222421 97549/264368 405674/1099419 503223/1363787 600772/1628155 698321/1892523 5684117/15404552 6382438/17297075 7080759/19189598 7779080/21082121 8477401/22974644 9175722/24867167 9874043/26759690 10572364/28652213 31018771/84064116 41591135/112716329 218528039/592233858 260119174/704950187 301710309/817666516 343301444/930382845 384892579/1043099174 728194023/1973482019 Dein Ansinnen ist, dass Zähler wie Nenner sind, damit wäre der beste Näherungsbruch unter diesen Rahmenbedingungen dann , der absolute Approximationsfehler ist dabei . Man kann natürlich das Skript leicht so umgestalten, dass nur genau dieser letzte passende Näherungsbruch ausgegeben wird und dann abgebrochen wird. @HJKweseleit Die Kettenbruch-Näherungswerte tauchen sämtlich in dieser Liste auch mit auf, aber i.a. nicht nur diese, sondern auch noch welche "dazwischen". Der im obigen Beispiel gefundene Bruch ist ein solcher "dazwischen", d.h. die letzte Kettenbruchapproximation mit Nenner ist dann doch geringfügig schlechter hinsichtlich der absoluten Genauigkeit der Approximation. |