Почему Math.sqrt(i*i) .floor == я?
Я задаюсь вопросом, верно ли это: Когда я пускаю квадратный корень целого числа в квадрате, как в
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
Вышеупомянутый сценарий никогда ничего не печатает. Почему то, что так?
ОБНОВЛЕНИЕ: Спасибо за быстрый ответ это, кажется, решение: Согласно Википедии
Любое целое число с абсолютным значением, меньше чем или равным 2^24, может быть точно представлено в формате одинарной точности, и любое целое число с абсолютным значением, меньше чем или равным 2^53, может быть точно представлено в формате двойной точности.
Math.sqrt(i*i) начинает вести себя, поскольку я ожидал это начинающий с i=9007199254740993, который является 2^53 + 1.
4 ответа
Для "маленьких" целых чисел обычно существует точное представление с плавающей точкой.
Не так уж и сложно найти случаи, когда это ломается, как вы и ожидали:
Math.sqrt(94949493295293425**2).floor
# => 94949493295293424
Math.sqrt(94949493295293426**2).floor
# => 94949493295293424
Math.sqrt(94949493295293427**2).floor
# => 94949493295293424
Ruby's Float - это номер с плавающей точкой двойной точности, что означает, что он может точно представлять числа с (правилом пальцем) около 16 значительных десятичных цифр. Для регулярных номеров с плавающей точкой с одним точностью это о значительных 7 цифрах.
Вы можете найти подробную информацию здесь:
Что каждый компьютерный ученый должен знать о арифметике с плавающей точкой: http://docs.sun.com/source/819-3693/ncg_goldberg.html
Вот суть вашей путаницы:
Из-за точности представления с плавающей запятой это могло быть что-то вроде 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 чуть больше 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, либо 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 не соответствует ' t переполнение или потеря значимости), поэтому единственный способ встретить округление для этого типа вычислений - это представление самого x , поэтому вы видите его, начиная с 2 ^ 53 + 1 (наименьшее непредставимое целое число).