Jak porównać liczby w postaci a + b * sqrt (c) bez pośrednich liczb całkowitych, które stają się coraz większe?

Question

Pracuję nad aplikacją do rozwiązywania ograniczeń kwadratowych w geometrii Euklidesa 2D, w tym okręgów i linii (Constructable Numbers) i graficznie przedstawiających wyniki. Znalazłem this paper na temat reprezentowania takich problemów w drzewie binarnym, ale mam problem z implementacją:

Potrzebuję porównać numery formularza a + b*sqrt(c) dla standardowych operacji relacyjnych mniejszych niż, większych niż i równość. Wartości c dla mojej aplikacji są ograniczone do 2, 3, 5, 6, 10, 15 lub 30. Na przykład (C-jak pseudokod, ^ jest „do potęgi” operatora):

boolean CompareConstructibleNumbers(int a1, b1, c1, a2, b2, c2) 
{ 
    return a1plusb1sqrtc1_is_greater_than_a2plusb2sqrtc2 = 
     4 * ((a1 - a2)^2) * (b1^2) * c1 
      > ((b2^2) * c2 - (b1^2) * c1 - (a1 - a2)^2)^2; 
     // Not sure if I have the direction right for > 
} 

Ten naiwny realizacja wymaga mnie mnożyć wiele razy, więc 32-bitowe liczby całkowite stać 64-bitowe liczby całkowite, a następnie 128 bit, itp. Nie chcę używać niestandardowego BigInteger w mojej implementacji wyłącznie do przechowywania tymczasowej wartości używanej tylko do porównania.

Ja również wolałbym nie używać pływaków i chcieć uniknąć ryzyka błędu zaokrąglenia, próbując bezpośrednio obliczyć wartość sqrt(c) jako zmienną. Potrzebuję dokładnych obliczeń dla tej aplikacji, niekoniecznie nieskończonej precyzji, ale chcę uniknąć błędu zaokrąglania i zapewnić poprawne wyniki.

Jak mogę poradzić sobie z porównywaniem konstruktywnych liczb w formularzu a + b * sqrt(c) bez konieczności stosowania dużych liczb całkowitych? Moje początkowe wartości dla a i b są w zakresie 32-bitowym.

**** AKTUALIZACJA **** Dziękuję wszystkim za odpowiedzi. Podążając za sugestią kontynuowania ułamków, mogłem użyć Fundamental Recurrence Formulas do generowania dowolnie dokładnych przybliżeń dla pierwiastków kwadratowych.

Znalazłem także this paper, która omawia gromadzenie się błędów z mnożenia przybliżeń liczb rzeczywistych z reprezentacjami stałymi punktami przez liczby całkowite. Na szczęście część całkowita wszystkich pierwiastków kwadratowych, które mnie interesują, wynosi co najwyżej 6 (potrzebuję tylko 3 bitów), więc mam dużo bitów dostępnych do reprezentacji części ułamkowej dla przybliżenia. W przypadku mnożenia przez 32-bitową liczbę całkowitą, potrzebuję minimalnej aproksymacji stałoprzecinkowej Q3.32 bitów, aby błąd był 1-bitowy po mnożeniu.

Podczas gdy 53-bitowa precyzja double wystarcza do zachowania dokładnego przybliżenia dla pierwiastka kwadratowego, nie wystarczy zapisać wyniku po pomnożeniu przez 32-bitową liczbę całkowitą, ponieważ wymaga to minimum 67- bity precyzji, aby zminimalizować błąd. Używając reprezentacji stałoprzecinkowej w 64-bitowej liczbie całkowitej (powiedz Q16.48) dla c i 32-bitowej liczbie całkowitej b, zamierzam użyć arytmetyki wielowyrazowej z liczbami 96 lub 128-bitowymi, aby wykonać porównanie bez wystarczającego błędu zrzucić wyniki. Jestem przekonany, że będzie to wystarczająca dokładność do porównywania konstruktywnych liczb, które wykorzystują tylko te 7 kwadratowych korzeni, ale interesują mnie drugie opinie. jakieś pomysły?

Answer 1

Nie sądzę, że istnieje formuła, która pozwala na pozostanie w granicach 64 bitów dla dokładnego porównania przy założeniu, że twoje wartości wykorzystują pełne 32 bity. Problemem, jaki widzę, jest to, że liczba postaci a + b * sqrt (c) jest gęsta w realiach (zakładając, że c nie jest kwadratem), więc otrzymujesz bardzo subtelne porównania wymagające dużej precyzji. Dlatego zasadniczo musisz pozbyć się pierwiastków kwadratowych przez kwadraty, które wykorzystają 3 multiplikacje.

Implementacja BigInt w tym przypadku nie jest tak zła, ponieważ wystarczy zaimplementować mnożenie, dodawanie, odejmowanie i porównywanie. Można je skutecznie wdrożyć w bardzo niewielu liniach kodu. Zazwyczaj podział jest denerwujący do wdrożenia. Ponadto wiesz, że twoje liczby nigdy nie mogą przepełnić tablicy dwoma komórkami 64-bitowymi, więc nie musisz śledzić liczby bitów w produktach.

EDYCJA: W odniesieniu do użycia podwójnych sugerowanych przez Thomas i Nemo komentarz na ten temat, w rzeczywistości jest bardzo łatwo znaleźć przybliżenie za pomocą 32-bitowych ints w ciągu 2^{- 53} sqrt (2) przy użyciu kontynuowanych ułamków reprezentacja.