GCC und C-Lang haben einen uint128_t Datentyp. Ich habe ein paar
Berechnungen & Konstanten, für die das gerade so ausreichen müsste.
Einige der Berechnungen will ich mit Rationalen Zahlen bestehend aus 2
int128_t machen. Die 2 Komponenten wachsen bei so ziemlich jeder
Operation, ist halt so bei Rationalen Zahlen. Wenn ich glück habe, kann
ich dann durch den grössten gemeinsamen Teiler teilen, aber ich kann
mich nicht darauf verlassen, dass das immer geht.
Für den Fall suche ich nun die Beste Approximation a'/b' für a/b mit
a'<m und b'<m. Dabei geht es mir nicht darum, a'/b' - a/b zu minimieren,
mir ist die Präzision beider Komponenten gleich wichtig. Vorerst
definiere ich das zu minimierende deshalb so. Mit dem nächste Punkt X
auf die Linie a'b/a, die Distanz vom Punkt (a'/b') zu X im Verhältnis
zur Distanz vom Punkt (0/0) zu X.
Wenn ich das ausrechne komme ich auf:
1
f(n) = (a^3 (a^2 + b^2))/(2 (a + b) (2 a^2 n + a b + 2 b^2 n))
2
3
0 < b < a
4
0 < n < m <= a
5
6
g(m) = n with smallest f(n) for m
(btw. n ist hier a'). Das 0 < b < a ist da, um das ganze etwas zu
vereinfachen, die beste Approximation für a'/b' und b'/a' ist ja
eigentlich die Selbe, nur die Zahlen sind vertauscht, daher kann ich das
immer umtauschen so das b'<a', und nachher zurück tauschen.
Was ich herausfinden muss ist g(m). In meinem konkreten fall wäre
m=2**127, aber eine Allgemeine Lösung wäre mir lieber, falls ich die
Präzision später mal ändern will.
Ich brauche eine Effiziente Formel für g(m), aber ich stehe hier absolut
auf dem Schlauch. Wie gehe ich sowas überhaupt an?
Was ich bisher herausgefunden habe, ist, dass g(a) >= a/2 aber das hilft
mir nicht wirklich weiter. Wolframalpha hat mich bisher auch nicht
weiter gebracht...
Habs leider gerade nicht zur Hand, aber in "Concrete Mathematics" [1]
sollten sich da Hinweise finden. Google spuckt das aus:
https://github.com/alidasdan/best-rational-approximation
[1] R.L. Graham, D.E. Knuth, and O. Patashnik, Concrete Mathematics, 2nd
Edition, Addison-Wesley Longman, 1994.
rµ schrieb:> https://github.com/alidasdan/best-rational-approximation> A fraction n/d, where d is at most a given limit l, is the best rational> approximation to a target real number t if the absolute difference (the> absolute error) between n/d and t is the smallest among all the fractions> each of whose denominator is at most l.
Hmm... Da wird also einfach die Differenz der Brüche minimiert? Aber ist
die beste Lösung für min a'/b'-a/b wirklich immer die beste Lösung für
min b'/a'-b/a, oder ist das ein anderes Problem?
Ehrlich gesagt hab ich die Rechnung nach diesem Satz
🐧 DPA 🐧 schrieb:> Dabei geht es mir nicht darum, a'/b' - a/b zu minimieren,> mir ist die Präzision beider Komponenten gleich wichtig.
nicht mehr weiter nachvollzogen. Wenn mit Komponenten die Zahlen a', a,
b' und b gemeint sind, das sind ganze Zahlen, und die sind per Defintion
exakt, haben also keine "Präzision". Rationale Zahlen ditto.
Was die "Operationen" angeht die die Koeffizienten "aufblasen", dazu
gibts bei Knuth z.b. in TeX auch Algorithmen zumindest für die
Grundrechenarten.
🐧 DPA 🐧 schrieb:> Dabei geht es mir nicht darum, a'/b' - a/b zu minimieren,> mir ist die Präzision beider Komponenten gleich wichtig.
Was genau meinst Du mit "mir ist die Präzision beider Komponenten gleich
wichtig"? Suchst Du nun die beste rationale Approximation zu a/b mit a',
b' < m = 2^127 oder gibt es eine weitere Nebenbedingung?
Was ist Dein g(m)?
Alexander S. schrieb:> 🐧 DPA 🐧 schrieb:>> Dabei geht es mir nicht darum, a'/b' - a/b zu minimieren,>> mir ist die Präzision beider Komponenten gleich wichtig.>> Was genau meinst Du mit "mir ist die Präzision beider Komponenten gleich> wichtig"?
Stell dir ein Raster a x b breit vor. Nun stell dir eine Linie von 0,0
zu a,b vor. a',b' wäre der Punkt, der am nächsten an der Linie liegt,
wobei 0<a'<m und 0<b<m
> Suchst Du nun die beste rationale Approximation zu a/b mit a',> b' < m = 2^127 oder gibt es eine weitere Nebenbedingung?>> Was ist Dein g(m)?
Die Funktion suche ich ja.
https://en.wikipedia.org/wiki/GNU_Multiple_Precision_Arithmetic_Library
Wieso nicht einfach "die" Standardbibliothek für mathematische
Operationen verwenden?
Generell für das Rechnen mit großen Zahlen ist auch die OEIS immer einen
Blick wert, dort findet man viele Algorithmen usw.
Boost und die Bibliotheken in C++ sind auch einen Blick wert.
🐧 DPA 🐧 schrieb:> Wenn ich das ausrechne komme ich auf:f(n) = (a^3 (a^2 + b^2))/(2 (a + b)> (2 a^2 n + a b + 2 b^2 n))> 0 < b < a> 0 < n < m <= a> g(m) = n with smallest f(n) for m
ich versteh zwar noch immer nicht was die rechnung da genau soll, aber
minimum von f(n) rechnet man aus indem man nach n ableitet und die
ableitung 0 setzt und ausrechnet. f(n) ist von der struktur her ja recht
einfach (konstante faktoren herausheben, dann bleibt die ableitung von
sowas wie 1/(x+const)), ableitung 0 setzen ergibt quadratische
Gleichung. Man nimmt dann die Lösung wo 2te Ableitung <0 ist.
Bei weiterem Nachdenken fällt mir ein dass n vermutlich ganzzahlig sein
soll, das macht das dann zu einer diophantischen Gleichung, und da
beisst man sich dann vermutlich direkt die Zähne aus.
🐧 DPA 🐧 schrieb:> Dabei geht es mir nicht darum, a'/b' - a/b zu minimieren,> mir ist die Präzision beider Komponenten gleich wichtig. Vorerst> definiere ich das zu minimierende deshalb so. Mit dem nächste Punkt X> auf die Linie a'b/a, die Distanz vom Punkt (a'/b') zu X im Verhältnis> zur Distanz vom Punkt (0/0) zu X.
Das verstehe ich überhaupt nicht.
> Wenn ich das ausrechne komme ich auf:> f(n) = (a^3 (a^2 + b^2))/(2 (a + b) (2 a^2 n + a b + 2 b^2 n))
Wie du auf diese wilde Formel kommst, verstehe ich auch nicht.
🐧 DPA 🐧 schrieb:> Stell dir ein Raster a x b breit vor. Nun stell dir eine Linie von 0,0> zu a,b vor. a',b' wäre der Punkt, der am nächsten an der Linie liegt,> wobei 0<a'<m und 0<b<m
Das verstehe ich schon eher :)
Du willst also nicht den auf den Wert des Bruchs bezogenen Fehler
minimieren (was IMHO am naheliegendsten wäre), sondern stattdessen den
auf den Nenner des Bruchs bezogenen Fehler
Habe ich das richtig verstanden?
Falls ja: Wenn es zwei Paare (a', b') gibt, die zum gleichen Fehler e2
führen, welcher der beiden Alternativen gibst du dann den Vorzug?
Noch eine Frage zum Sinn des Ganzen:
Rationale Arithmetik verwendet man üblicherweise dann, wenn man mit
gebrochenen Zahlen exakt rechnen möchte, was mit Fest- oder
Gleitkommaarithmetik nicht immer möglich ist (schon 1/3 führt dort zu
Rundungsfehlern). Dafür nimmt man den zusätzlichen Rechenaufwand (Finden
des kleinsten gemeinsamen Nenners bei Additionen und Subtraktionen und
Kürzen der Ergebnisse bei allen Rechenoperationen) in Kauf.
Du möchtest jetzt mit noch höherem Rechenaufwand Näherungslösungen für
die einzelnen Rechenoperationen finden, womit der Vorteil der rationalen
Arithmetik zunichte gemacht und ihr Nachteil noch verstärkt wird. Warum
verwendest du stattdessen nicht einfach Fest- oder Gleitkommaarithmetik?
Yalu X. schrieb:> Falls ja: Wenn es zwei Paare (a', b') gibt, die zum gleichen Fehler e2> führen, welcher der beiden Alternativen gibst du dann den Vorzug?
Wenn man die zwei Varianten gleichsetzt umstellt und ausrechnet ergibt
sich
Wenn man von (0/0) Linien nach (a/b) und (a'/b') zeichnet, den Winkel
dazwischen, den will ich minimieren.
Mir ist aufgefallen, bei der Formel f(n) oben hatte ich einen Fehler
beim umformen gemacht, die sollte eigentlich so aussehen:
Yalu X. schrieb:> Du möchtest jetzt mit noch höherem Rechenaufwand Näherungslösungen für> die einzelnen Rechenoperationen finden, womit der Vorteil der rationalen> Arithmetik zunichte gemacht und ihr Nachteil noch verstärkt wird. Warum> verwendest du stattdessen nicht einfach Fest- oder Gleitkommaarithmetik?
Das ganze ist eigentlich nur eine Spielerei. Ein versuch, eine kleine
Physiksimulation aufzubauen, basierend auf Plank Einheiten. Die sind
teils sehr gross / klein, deshalb nehme ich int128_t. Der Grundgedanke
dabei war, wenn ich beim Rechnen etwas aufpasse, kann ich den Fehler so
halten, dass der eh kleiner ist als eine Plank länge/zeit bleibt usw.
bleibt. Beim Relativitätszeugs gibt es aber ein paar fiese Sachen, die
man beachten muss. z.B. wenn man 2 Geschwindigkeiten addiert:
Das +1 ist bei floats fies. Und wenn man bei allen Variablen 1/x macht,
kommt wieder das selbe raus. Also je nachdem, ob es schnelle oder
langsame Geschwindigkeiten sind, ändert sich der Zähler oder der Nenner
quasi linear. Also kann ich nicht sagen, dass mir die Genauigkeit beim
einen oder beim anderen wichtiger wäre. Aber ich hoffe, es mit
Rationalen Zahlen ganz gut abbilden zu können.
Und deshalb der Versuch, den Fehler bei beiden Komponenten klein zu
halten.
Vermutlich wird aus dem ganzen am Ende nichts. Ich bin mir noch nicht
einmal sicher, was ich überhaupt simulieren möchte. Aber was auch immer
dabei raus kommt, ist wieder eine neue Erfahrung. Es geht ja nur um den
Spass an der Freude.
Thread beobachten
Seitenaufteilung abschalten