Почему Math.sqrt (i * i) .floor == i?

Question

мне интересно, если это правда: Когда я беру корень квадратный из квадрата целого числа, как в

f = Math.sqrt(123*123) 

я получить число с плавающей точкой очень близко к 123. Из-за точности представления с плавающей запятой это может быть что-то вроде 122.99999999999999999999 или 123.000000000000000000001.

С floor(122.999999999999999999) - 122, я должен получить 122 вместо 123. Поэтому я ожидаю, что floor(sqrt(i*i)) == i-1 примерно в 50% случаев. Как ни странно, для всех номеров, которые я тестировал, floor(sqrt(i*i) == i. Вот небольшой рубиновый скрипт для проверки первых 100 миллионов номеров:

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

Приведенный выше сценарий никогда ничего не печатает. Почему это так?

UPDATE: Спасибо за быстрый ответ, это, кажется, решение: В соответствии с wikipedia

Любое целое число с абсолютным значением меньше чем или равной 2^24 может быть точно представлены в формат одиночной точности , а любое целое число с абсолютным значением , значение которого меньше или равно 2^53, может быть точно представлено в двойном прецизионном формате.

Math.sqrt (я * I) начинает вести себя, как я ожидал, что, начиная с I = 9007199254740993, что 2^53 + 1.

Answer 1

Для "маленьких" целых чисел, то, как правило, точное представление с плавающей запятой.

Answer 2

Это не слишком трудно найти случаи, когда это ломается, как и следовало ожидать: Float

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

Answer 3

Руби является двойной точности с плавающей запятой, что означает, что он может точно представлять числа с (правило большого пальца) около 16 значащих десятичных цифр. Для регулярных чисел с плавающей запятой с одинарной точностью это около 7 цифр.

Вы можете найти более подробную информацию здесь:

Что каждый компьютер ученый должен знать о арифметики с плавающей точкой: http://docs.sun.com/source/819-3693/ncg_goldberg.html

Answer 4

Вот суть вашей путаницы:

В связи с плавающей точкой представление точность, это может быть что-то как 122.99999999999999999999 или 123.000000000000000000001.

Это неверно. Он всегда будет ровно 123 на совместимой с IEEE-754 системе, которая почти все системы в эти современные времена. Арифметика с плавающей точкой не имеет «случайной ошибки» или «шума». Он имеет точное, детерминированное округление, и многие простые вычисления (например, этот) вообще не требуют округления.

123 точно представима в плавающей точкой, и поэтому 123*123 (поэтому они все целые числа скромных размеров). Таким образом, ошибка округления не возникает при преобразовании 123*123 в тип с плавающей запятой. Результат точно15129.

Квадратный корень правильно округленный операция по стандарту IEEE-754. Это означает, что если есть точный ответ, для его создания требуется функция квадратного корня. Так как вы извлекая квадратный корень точно15129, который точно123, это точно результат, который вы получите от функции квадратного корня. Не происходит округления или аппроксимации.

Теперь, насколько велика целое число, это будет верно?

Двойная точность может точно представлять все целые числа до 2^53. До тех пор, пока i*i будет меньше 2^53, округление не произойдет при вычислении, и результат будет точным по этой причине. Это означает, что для всех i меньше 94906265, мы знаем, что вычисление будет точным.

Но вы пробовали i больше! Что происходит?

Для самых больших i что вы пытаетесь, i*i всего лишь 2^53 (1.1102... * 2^53, фактически). Поскольку преобразования из целого числа в двойное (или умножение в двойном) также являются правильно округленным операций, i*i будет представляемым значением, ближайшим к точному квадрату i. В этом случае, поскольку i*i имеет ширину 54 бита, округление произойдет в самом нижнем разряде. Таким образом, мы знаем, что:

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

где либо -1,0, or 1. Если округление равно нулю, то квадрат является точным, поэтому квадратный корень является точным, поэтому мы уже знаем, что вы получите правильный ответ. Давайте проигнорируем этот случай.

Итак, теперь мы смотрим на квадратный корень i*i +/- 1. Используя разложение в ряд Тейлора, бесконечно точное (неокругленное) значение этого квадратного корня:

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

Теперь это немного неудобным, чтобы увидеть, если вы еще не сделали какого-либо анализа ошибок с плавающей точкой и раньше, но если вы использовать тот факт, что i^2 > 2^53, вы можете увидеть, что: термин

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

меньше 2^-54, что означает, что (так как квадратный корень правильно округлый, и, следовательно, его ошибка округления должна быть меньше, чем 2^54), округленный Результатом функции sqrt является точно i.

Оказывается, что (с аналогичным анализом) для любого точно представляемого числа с плавающей запятой x, sqrt (x * x) является ровно x (при условии, что промежуточный расчет x*x не переполнен или нисходит) поэтому единственный способ, которым вы можете столкнуться при округлении для этого типа вычислений, находится в представлении самого x, поэтому вы видите его начиная с 2^53 + 1 (наименьшее непредставимое целое число).