Почему 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. Вот небольшой скрипт ruby ​​для проверки первых 100 миллионов чисел:

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

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

ОБНОВЛЕНИЕ: Спасибо за быстрый ответ, это, кажется, решение: Согласно wikipedia

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

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

Answer 1

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

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

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

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

, где 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)

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

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

Answer 2

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

Answer 3

Нетрудно найти случаи, когда это выходит из строя, как и следовало ожидать:

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

Answer 4

Ruby's Float - это число с плавающей запятой двойной точности, что означает, что он может точно представлять числа с (эмпирическим правилом) около 16 значащих десятичных цифр. Для обычных чисел с плавающей запятой одинарной точности это примерно 7 цифр.

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

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