Где неточности в math.sqrt() и math.pow(), исходящие из-за больших чисел?

Если вы берете число, берете его квадратный корень, отбрасываете десятичную дроби, а затем поднимаете его на вторую мощность, результат всегда должен быть меньше или равен исходному числу.

Это похоже на правду в python, пока вы не попробуете его по 99999999999999975425 по какой-либо причине.

import math

def check(n):
    assert math.pow(math.floor(math.sqrt(n)), 2) <= n

check(99999999999999975424)  # No exception.
check(99999999999999975425)  # Throws AssertionError.

Похоже, что math.pow(math.floor(math.sqrt(99999999999999975425)), 2) возвращает 1e+20.

Я предполагаю, что это имеет какое-то отношение к тому, как мы храним значения в python... что-то связано с арифметикой с плавающей запятой, но я не могу объяснить, как конкретно это влияет на этот случай.

Ответ 1

Ты дико краснешь свой ответ. Проблема не в том, что речь идет о sqrt или pow, проблема в том, что вы используете цифры, большие, чем плавающая точка. Стандартная арифметика с плавающей точкой IEEE 64 бит не может представлять любое целое значение за пределами 52 бит (плюс один знаковый бит).

Попробуйте просто преобразовать ваши входы в float и обратно:

>>> int(float(99999999999999975424))
99999999999999967232
>>> int(float(99999999999999975425))
99999999999999983616

Как вы можете видеть, представляемое значение пропущено на 16384. Первый шаг в math.sqrt преобразуется в float (C double), и в этот момент ваше значение увеличилось достаточно, чтобы испортить конечный результат.

Краткая версия: float не может точно представлять большие целые числа. Используйте decimal, если вам нужна большая точность.

Ответ 2

В отличие от требований Evan Rose (теперь удаленных), это не связано с значением epsilon в алгоритме sqrt.

Большинство функций модуля math передают свои входы в float, а math.sqrt - один из них.

99999999999999975425 не может быть представлен как float. Для этого ввода литье производит поплавок с точным числовым значением 99999999999999983616, который repr показывает как 9.999999999999998e+19:

>>> float(99999999999999975425)
9.999999999999998e+19
>>> int(_)
99999999999999983616L

Ближайший float к квадратному корню из этого числа 10000000000.0, и то, что возвращает math.sqrt.