Dlaczego Math.sqrt (i * i) .floor == i?

Question

Zastanawiam się, czy to prawda: Kiedy biorę pierwiastek kwadratowy z kwadratów liczb całkowitych, jak w

f = Math.sqrt(123*123) 

otrzymam liczbę zmiennoprzecinkową bardzo blisko 123. Ze względu na dokładność reprezentacji zmiennoprzecinkowej może to wynosić 122.99999999999999999999 lub 123.000000000000000000001.

Od jest 122, powinienem otrzymać 122 zamiast 123. Tak więc oczekuję, że floor(sqrt(i*i)) == i-1 w około 50% przypadków. O dziwo, dla wszystkich liczb, które przetestowałem, floor(sqrt(i*i) == i. Oto mały skrypt z rubinami, aby przetestować pierwsze 100 milionów numerów:

100_000_000.times do |i| 
    puts i if Math.sqrt(i*i).floor != i 
end 

Powyższy skrypt nigdy niczego nie drukuje. Dlaczego to jest takie?

UPDATE: Dzięki na szybką odpowiedź, to wydaje się być rozwiązaniem: Zgodnie wikipedia

liczbą całkowitą o wartości bezwzględnej mniejszej niż lub równą 2^24 może być dokładnie reprezentowane format pojedynczej precyzji i dowolna liczba całkowita o wartości bezwzględnej o wartości mniejszej lub równej 2^53 mogą być dokładnie reprezentowane w podwójnym formacie precyzyjnym .

Math.sqrt (I * i) zaczyna zachowywać się jak ja spodziewałem się, że począwszy od I = 9007199254740993, czyli 2^53 + 1.

Answer 1

Dla "małych" liczb całkowitych, jest zazwyczaj dokładna reprezentacja zmiennoprzecinkowa.

Answer 2

To nie jest zbyt trudno znaleźć przypadki, gdy ten zepsuje jak można się spodziewać: Float

Math.sqrt(94949493295293425**2).floor 
# => 94949493295293424 
Math.sqrt(94949493295293426**2).floor 
# => 94949493295293424 
Math.sqrt(94949493295293427**2).floor 
# => 94949493295293424 

Answer 3

Ruby jest podwójnej precyzji liczbę zmiennoprzecinkową, co oznacza, że ​​można go dokładnie oznaczają numery z (reguły of kciuka) około 16 istotnych cyfr dziesiętnych. W przypadku zwykłych liczb zmiennoprzecinkowych pojedynczej precyzji jest to około 7 cyfr.

można znaleźć więcej informacji tutaj:

Co każdy komputer naukowiec powinien wiedzieć o arytmetyki zmiennoprzecinkowej: http://docs.sun.com/source/819-3693/ncg_goldberg.html

Answer 4

Oto esencja twojego zamieszania:

Ze względu na zmiennoprzecinkowych reprezentacja precyzja, to może być coś jak 122.99999999999999999999 lub 123.000000000000000000001.

To jest fałszywe. Zawsze będzie dokładnie 123 na systemie zgodnym ze standardem IEEE-754, czyli prawie wszystkie systemy w tych czasach nowożytnych. Arytmetyki zmiennoprzecinkowej nie ma „przypadkowy błąd” lub „szum”. Posiada precyzyjny deterministyczny zaokrąglania i wielu prostych obliczeń (jak ten) nie ponosić żadnej zaokrąglenie w ogóle.

123 jest dokładnie reprezentowalna w zmiennoprzecinkowych, a więc jest 123*123 (tak są wszystkie skromny wielkości liczb całkowitych). Więc nie występuje błąd zaokrąglania podczas konwersji 123*123 na typ zmiennoprzecinkowy. Wynik to dokładnie15129.

Pierwiastek kwadratowy to prawidłowo zaokrąglona operacja według standardu IEEE-754. Oznacza to, że jeśli istnieje dokładna odpowiedź, do jej wytworzenia wymagana jest funkcja pierwiastka kwadratowego. Ponieważ pacjent jest pierwiastek kwadratowy z dokładnie15129, który jest dokładnie123, to dokładnie wyniku, który się z funkcji pierwiastka kwadratowego. Nie ma zaokrąglenia ani przybliżenia.

Teraz, jak duże z liczby całkowitej będzie to prawda?

Podwójna precyzja może dokładnie przedstawiać wszystkie liczby całkowite do 2^53. Tak długo, jak i*i jest mniej niż 2^53, nie będzie zaokrąglania w obliczeniach, a wynik będzie dokładny z tego powodu. Oznacza to, że dla wszystkich i mniejszych niż 94906265 wiemy, że obliczenia będą dokładne.

Ale wypróbowałeś i większy niż to! Co się dzieje?

W przypadku największego i, którego próbujesz, i*i jest zaledwie nieco większy niż 2^53 (faktycznie). Ponieważ konwersje z liczby całkowitej do podwójnej (lub mnożenia w podwójnej) są również odpowiednio zaokrąglone, to reprezentowana wartość jest najbliższa dokładnemu kwadratowi i. W tym przypadku, ponieważ i*i ma szerokość 54 bitów, zaokrąglenie nastąpi w bardzo najniższym bicie. Tak więc wiemy, że:

i*i as a double = the exact value of i*i + rounding 

gdzie jest albo -1,0, or 1. Jeśli zaokrąglenie wynosi zero, to kwadrat jest dokładny, więc pierwiastek kwadratowy jest dokładny, więc wiemy już, że otrzymujesz właściwą odpowiedź. Zignorujmy tę sprawę.

Więc teraz patrzymy na pierwiastek kwadratowy z i*i +/- 1. Korzystanie z ekspansji szereg Taylora, nieskończenie precyzyjny (niezaokrąglona) wartość tego pierwiastka jest:

i * (1 +/- 1/(2i^2) + O(1/i^4)) 

Teraz jest to nieco fiddly aby sprawdzić, czy nie zrobili żadnych zmiennoprzecinkowych analizy błędu przed, ale jeśli wykorzystują fakt, że i^2 > 2^53, można zobaczyć, że: Termin

1/(2i^2) + O(1/i^4) 

jest mniejszy niż 2^-54, co oznacza, że ​​(ponieważ pierwiastek kwadratowy jest poprawnie zaokrąglone, i stąd jego błąd zaokrąglenia musi być mniejszy niż 2^54), zaokrąglony wynik funkcji sqrt to dokładnie i.

Okazuje się, że (z podobną analizą), dla każdej dokładnie reprezentowalnej liczby zmiennoprzecinkowej x, sqrt (x * x) jest dokładnie x (przy założeniu, że obliczenia pośrednie x*x nie przekroczą lub nie będą miały wartości), więc jedyny sposób, w jaki można uzyskać zaokrąglenie dla tego typu obliczeń, jest reprezentowany przez samą x, dlatego zaczyna się od 2^53 + 1 (najmniejszej niereprezentowalnej liczby całkowitej).