Точность целого квадратного корня в Python

Я хотел бы понять, почему что-то происходит. Мне нужно было реализовать целочисленный квадратный корень в Python (isqrt(64) = 8 = isqrt(80)). Я убедился, что наивный подход:

def isqrt(n):
    return int(math.sqrt(n))

должен был время от времени терпеть неудачу, когда переданное n является квадратным числом, предполагая, что Python преобразует в числа с плавающей запятой, а затем выполняет вычисление квадратного корня для чисел с плавающей запятой. Например, вызывая isqrt(13*13), я ожидал, что после преобразования в числа с плавающей запятой и вычисления sqrt можно получить что-то вроде 12,999999843, что после приведения к целому числу даст нам 12.

Но я выполнял большие циклы тестирования значений, больших и малых, и всегда получал правильный результат. Казалось бы, нет необходимости реализовывать специальный квадратный корень для целых чисел, в конце концов!

Непонимание беспокоит меня так же сильно, как когда что-то, что должно было работать, терпит неудачу. Почему это происходит?

Есть еще один вопрос, касающийся целочисленного квадратного корня в python: целочисленный квадратный корень в python

В определенной там функции isqrt() к n добавляется +0,5, что, я думаю, было включено именно для решения проблемы, о которой я упоминал, которую я ожидал, но не могу найти в конкретном случае.

РЕДАКТИРОВАТЬ: забыл указать, я использую Python 2.7


python python-2.7 integer math.sqrt
person zeycus    schedule 21.01.2016    source источник
comment
Почему это происходит? stackoverflow .com/questions/588004/   -  person Łukasz Rogalski    schedule 21.01.2016
comment
В Python 2.7.6 я получаю math.sqrt(5) == 2.23606797749979, поэтому результаты sqrt всегда с плавающей запятой, даже для небольших целочисленных аргументов. Но я думаю, что это изменилось в Python 3. Python имеет динамическую типизацию, поэтому в принципе может изменять тип результата по мере необходимости, давая целочисленный результат (включая большие целые числа), где аргумент является целым числом, если это то, что решает власть. Это имеет большой смысл, но я не проверял (поэтому комментарий не отвечает).   -  person Steve314    schedule 21.01.2016
comment
@Rogalski Моя проблема в том, почему это (то, что описывает ваша ссылка) не происходит?   -  person zeycus    schedule 21.01.2016
comment
В CPython 2.7 math.sqrt() напрямую перенаправляется (помимо магии обработки комплексных чисел) соответствующей функции в libm (обратите внимание, что Decimal.sqrt() отличается). Неудивительно, что чистая версия C ведет себя так же.   -  person dhke    schedule 21.01.2016

Ответы (1)


arrow_upward
4
arrow_downward

Использование python 2.7 на машине с типом C long как 64-битным целым числом и типом C double, реализованным как 64-битное число с плавающей запятой IEEE, дает

>>> import math
>>> x = (2<<53) + 1
>>> int(math.sqrt(x*x)) == x
False

Я сжульничал и выбрал число, которое 64-битное число с плавающей запятой IEEE не может точно представлять (но может целочисленный тип Python), (2<<53) + 1. Python 2.7 вычисляет x*x как целое число Python 2.7 long. (Примечание: это отличается от C long; python 2.7 может представлять 2<<600 как целое число, но C не может.)

Говоря о 2<<600,

>>> import math
>>> x = 2<<600
>>> int(math.sqrt(x*x)) == x
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
OverflowError: long int too large to convert to float
person David Hammen    schedule 21.01.2016
comment
@Davin Хороший пример, вы протестировали намного больше, чем я пробовал. Насколько я понимаю, происходит то, что для квадратных чисел с точным представлением в виде плавающих чисел точно вычисляется и квадратный корень. Что-то я не знал! - person zeycus; 21.01.2016
comment
FWIW, предполагая семантику IEEE 754 (с double C, совпадающим с двоичным кодом IEEE 75464), наименьшим n, для которого int(math.sqrt(n)) не дает правильного результата, является n = 2**52 + 2**27. - person Mark Dickinson; 30.12.2019