Ich arbeite an einer Anwendung zur Lösung von quadratischen Zwangsbedingungen in der 2D euklidischen Geometrie mit Kreisen und Linien ( Constructable Numbers ) und die Ergebnisse graphisch darstellen. Ich habe dieses Paper gefunden, um solche Probleme in einem Binärbaum darzustellen, aber ich stoße auf ein Implementierungsproblem:
Ich muss Zahlen der Form a + b*sqrt(c) für die standardmäßigen relationalen Operationen von kleiner als, größer als und Gleichheit vergleichen. Die Werte von c für meine Anwendung sind auf 2 , 3 , 5 , 6 , 10 , 15 oder 30 beschränkt. Zum Beispiel (C-ähnlicher Pseudocode, ^ ist "der Potenz von" Operator):
Diese naive Implementierung erfordert, dass ich viele Male multipliziere, also 32-Bit-Integer werden 64-Bit-Integer, und dann 128-Bit usw. Ich möchte keinen benutzerdefinierten BigInteger in meiner Implementierung verwenden, nur um einen temporären Wert zu speichern nur zum Vergleich verwendet.
Ich würde es auch vorziehen, keine Gleitkommazahlen zu verwenden und das Risiko eines Rundungsfehlers bei der direkten Berechnung von sqrt(c) als Gleitkommazahl zu vermeiden. Ich brauche genaue Berechnungen für diese Anwendung, nicht unbedingt unendliche Präzision, aber ich möchte Rundungsfehler vermeiden und korrekte Ergebnisse sicherstellen.
Wie kann ich konstruierbare Zahlen der Form a + b * sqrt(c) vergleichen, ohne riesige Zwischenwerte zu benötigen? Meine Anfangswerte für a und b liegen im 32-Bit-Bereich.
**** UPDATE **** Danke an alle für ihre Antworten. Im Anschluss an den Vorschlag, fortlaufende Brüche zu verfolgen, konnte ich die Grundwiederholungsformeln verwenden, um beliebig genaue Annäherungen für das Quadrat zu erzeugen Wurzeln.
Ich fand auch dieses Papier , das die Fehlerakkumulation aus der Multiplikation von Approximationen reeller Zahlen mit Festkommadarstellungen durch ganze Zahlen diskutiert . Zum Glück ist der ganzzahlige Teil aller Quadratwurzeln, an denen ich interessiert bin, höchstens 6 (benötigt nur 3 Bits), so dass ich viele Bits zur Verfügung habe, um den Bruchteil für eine Annäherung darzustellen. Für die Multiplikation mit einer 32-Bit-Ganzzahl benötige ich eine minimale Festkommaproximation von Q3.32 Bits um den Fehler nach der Multiplikation auf 1 Bit zu halten.
Während also eine 53-Bit-Genauigkeit double ausreicht, um eine hinreichend genaue Approximation für eine Quadratwurzel zu speichern, ist es nicht ausreichend, das Ergebnis nach der Multiplikation mit einer 32-Bit-Ganzzahl zu speichern, da hierfür ein Minimum von 67 erforderlich ist -bits der Genauigkeit, um Fehler zu minimieren. Unter Verwendung einer Festkommadarstellung in einer 64-Bit-Ganzzahl (etwa Q16.48) für c und einer 32-Bit-Ganzzahl b , beabsichtige ich, Mehrwortarithmetik mit 96 oder 128 Bitzahlen zu verwenden, um den Vergleich durchzuführen ohne genug Fehler, um die Ergebnisse zu werfen. Ich bin zuversichtlich, dass dies genug Genauigkeit sein wird, um konstruierbare Zahlen zu vergleichen, die nur diese 7 Quadratwurzeln verwenden, aber ich bin an zweiten Meinungen interessiert. Irgendwelche Gedanken?
Ich glaube nicht, dass es eine Formel gibt, mit der Sie für einen exakten Vergleich innerhalb von 64 Bits bleiben können, vorausgesetzt, Ihre Werte verwenden die vollen 32 Bits. Das Problem, wie ich es sehe, ist, dass Zahlen der Form a + b * sqrt (c) in den Realen dicht sind (vorausgesetzt, dass c kein Quadrat ist), so dass Sie sehr subtile Vergleiche erhalten, die viel Präzision benötigen. Daher müssen Sie im Wesentlichen die Quadratwurzeln durch Quadrieren loswerden, die 3 Multiplikationen verwenden.
Eine BigInt-Implementierung ist in diesem Fall eigentlich nicht so schlecht, da Sie nur Multiplikation, Addition, Subtraktion und Vergleich implementieren müssen. Diese können in wenigen Codezeilen effizient implementiert werden. In der Regel ist die Aufteilung störend. Außerdem wissen Sie, dass Ihre Zahlen niemals ein Array mit zwei 64-Bit-Zellen überlaufen können, so dass Sie nicht wirklich die Anzahl der Bits in den Produkten verfolgen müssen.
EDIT: Bezüglich der Verwendung von Doppelpunkten, die von Thomas und Nemos Kommentar dazu vorgeschlagen wurden, ist es sehr einfach, eine Näherung mit 32-Bit-Ints innerhalb von 2 ^ {- 53} von sqrt (2) zu finden, indem die fortgesetzte Bruchdarstellung verwendet wird .
Tags und Links language-agnostic math sqrt