31.05.2024 20:33
Sivchenko_translate 31 12000 Источник

Ещё одна причуда Python, исследование её подноготной и попытка понять, почему так случается.

Недавно в сети X был популярен этот твит (см. скриншот), и я обратил внимание. Это очередной сюрприз в Python, связанный с характерными для него уникальными деталями реализации.

Известно, насколько приблизительна математика для чисел с плавающей точкой, по причине присущих ей пределов представления. В других языках int зачастую неявно повышаются до double, благодаря чему операции сравнения получаются непротиворечивыми. Но в Python этот процесс осложняется из-за того, что в языке присутствуют целые числа с неограниченной разрядностью, и их использование приводит к неожиданным результатам.

В Python целочисленное значение сравнивается с представлением числа с плавающей точкой (двойной точности). При этом может снижаться точность, что вызывает такие расхождения. В этой статье мы подробно разберём, как такие сравнения выполняются в CPython. Так у нас будет отличная возможность подробнее исследовать эти сложности.

Итак, данная статья состоит из следующих разделов:

  • Мы быстро вспомним, что представляет собой IEEE-754 — формат для чисел двойной точности. Именно он используется для представления в памяти чисел с плавающей точкой

  • Проанализируем представление трёх чисел в соответствии со стандартом IEEE-754

  • Изучим алгоритм CPython, предназначенный для сравнения целых чисел и чисел с плавающей точкой

  • Проанализируем три тестовых сценария в контексте алгоритма CPython

Освежим знания по формату IEEE-754

Внутрисистемно в CPython используется тип double из C, и именно в нём хранится значение с плавающей точкой. Именно поэтому данный формат соответствует стандарту IEEE-754 для представления этих значений.

Объект «число с плавающей точкой» в CPython. На внутрисистемном уровне в нём используется тип double, в котором и хранится актуальное значение числа.
Объект «число с плавающей точкой» в CPython. На внутрисистемном уровне в нём используется тип double, в котором и хранится актуальное значение числа.

Быстро напомню, что сказано в стандарте о представлении значений с двойной точностью. Если вы всё это уже знаете, можете смело переходить к следующему разделу.

Значения с двойной точностью представляются каждое при помощи 64 разрядов, а именно:

  • 1 разряд используется в качестве знакового бита

  • В 11 разрядах представлен порядок. При указании порядка используется смещение в 1023, т.e., фактическое значение порядка на 1023 меньше, чем значение, представленное с двойной точностью.

  • В последних 52 разрядах представлена мантисса.

Этот формат подкреплён обширной теорией, описывающей, как в данный формат преобразуются числа и каковы различные способы округления, применяемые в нём — на эту тему есть целая статья, которую вам стоит прочесть, если вы интересуетесь темой.

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

Преобразование числа с плавающей точкой в формат IEEE-754

Чтобы преобразовать число с плавающей точкой в его двоичное представление, соответствующее формату IEEE-754, и для этого нужно проделать следующие три шага.  В качестве примера разберём эти шаги для числа 4.5.

Шаг 1: Преобразуем число в двоичный формат

Чтобы преобразовать значение с плавающей точкой из десятичной в двоичную систему, требуется отдельно преобразовать целочисленную часть и отдельно дробную часть, а затем в двоичном представлении записать их через двоичную точку (.).

4 в двоичном представлении будет 100, а 0.5 будет 1. Следовательно, можно представить 4.5 как 100.1.

Шаг 2: Нормализация двоичного представления

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

В нашем примере двоичная точка расположена так: 100.1, то есть, у нас 3 разряда до двоичной точки. Чтобы нормализовать его, необходимо выполнить сдвиг вправо на 2 разряда. Таким образом, нормализованное представление примет вид 1.001 * 2^2.

Шаг 3: Извлечение мантиссы и порядка из нормализованного представления

Из нормализованного представления прямо следуют мантисса и порядок. В примере, который мы сейчас рассматриваем, нормализованное значение равно 1.001. Чтобы его получить, нам потребовалось сдвинуть исходное значение на два разряда вправо — следовательно, порядок равен 2.

В формате IEEE-754 мантисса имеет форму 1.M. В сущности, ведущая единица перед двоичной точкой не входит в двоичное представление, так как известно, что здесь всегда будет 1. Поэтому, не сохраняя её, экономим 1 разряд под нужные данные. Следовательно, мантисса здесь составит 001. Поскольку ширина мантиссы составит 52 разряда, остальные 49 разрядов здесь будут заполнены нулями.

Итоговое двоичное представление

  • Знаковый разряд: Число положительное, следовательно, знаковый разряд будет равен 0.

  • Порядок: порядок равен 2. Правда, при представлении числа в формате IEEE-754, к нему потребуется добавить сдвиг в 1023, что даёт нам 1025. Таким образом, двоичное представление порядка составит 10000000001.

  • Мантисса: мантисса равна 001000…000

Соответственно, двоичное представление числа 4.5 в соответствии с форматом IEEE-74 будет:

(0) (10000000001) (001000…000)

(Для наглядности я заключил разные компоненты числа в круглые скобки.)

Анализ представления IEEE-754 на трёх тестовых примерах

Давайте проверим, что мы выучили о формате IEEE-754 для чисел двойной точности и попробуем выяснить, как были бы представлены три числа из трёх тестовых примеров. При этом их будет особенно удобно проанализировать в контексте алгоритма CPython для сравнения чисел с плавающей точкой.

Представление числа 9007199254740992.0 в формате IEEE-754

Возьмём значение из первого тестового сценария: 9007199254740992.0.

Оказывается, что 9007199254740992 — это 2^53. Таким образом, в двоичном представлении это будет единица, за которой следуют 53 нуля: 10000000000000000000000000000000000000000000000000000.

Нормализованная форма в данном случае 1.0 * 2^53, мы получим её, сдвинув разряды на 53 позиции вправо и представим порядок как 53.

Также напомню, что ширина мантиссы составляет всего 52 разряда, а мы сдвигаем значение на 53 разряда вправо — и это значит, что ведущий знаковый бит в нашем исходном значении будет потерян. Но, поскольку здесь все разряды равны 0, ничего страшного не случится, и мы всё равно сможем представить 9007199254740992.0 с достаточной точностью.

Давайте обобщим, из чего состоит 9007199254740992.0:

  • Знаковый разряд: 0

  • Порядок: 53 + 1023 (сдвиг) = 1076 (10000110100 в двоичной системе)

  • Мантисса: 0000000000000000000000000000000000000000000000000000

  • Представление в стандарте IEEE-754: 0100001101000000000000000000000000000000000000000000000000000000

Представление 9007199254740993.0 в формате IEEE-754

Во втором тестовом сценарии рассмотрим значение 9007199254740993.0, на единицу выше, чем в предыдущем примере. Чтобы получить его двоичное представление, достаточно всего лишь добавить единицу к двоичному представлению предыдущего значения:

10000000000000000000000000000000000000000000000000001.0

Опять же, чтобы преобразовать это число в нормализованный вид, нужно выполнить сдвиг на 53 разряда вправо, в результате получится, что порядок равен 53.

Но ширина мантиссы составляет всего 52 разряда. При сдвиге нашего значения на 53 разряда наименьший значащий разряд (LSB), равный 1, будет потерян, и в мантиссе останутся одни нули. В результате получатся следующие компоненты:

  • Знаковый разряд: 0

  • Порядок: 53 + 1023 (сдвиг) = 1076 (10000110100 в двоичной системе)

  • Мантисса: 0000000000000000000000000000000000000000000000000000

  • Представление в стандарте IEEE-754:  0100001101000000000000000000000000000000000000000000000000000000

Обратите внимание, что представление в стандарте IEEE-754 для 9007199254740993.0 точно такое же, как для 9007199254740992.0. Таким образом, в памяти число 9007199254740993.0 на самом деле представлено как 9007199254740992.0.

Вот почему Python выдаёт для 9007199254740993 == 9007199254740993.0 результат False, ведь он трактует эту операцию как сравнение 9007199254740993 и 9007199254740992.0.

Об этой частности мы ещё вспомним, когда будем анализировать 2-й сценарий после того, как обсудим алгоритм CPython.

Представление 9007199254740994.0 в формате IEEE-754

В третьем и последнем тестовом сценарии разберём число 9007199254740994.0, которое на единицу больше предыдущего значения. Его двоичное представление можно получить, добавив 1 к двоичному представлению 9007199254740993.0. В результате получим:

10000000000000000000000000000000000000000000000000010.0

Здесь также 54 разряда до двоичной точки. Чтобы преобразовать это число в нормализованный вид, его нужно сдвинуть вправо на 53 разряда. Таким образом, порядок будет 53.

Обратите внимание: на этот раз второй наименьший значащий разряд равен 1. Следовательно, если сдвинуть это число вправо на 53 разряда, он превращается в наименьший значащий разряд мантиссы (ширина которой составляет 52 разряда).

Компоненты выглядят так:

  • Знаковый разряд: 0

  • Порядок: 53 + 1023 (сдвиг) = 1076 (10000110100 в двоичной системе)

  • Мантисса: 0000000000000000000000000000000000000000000000000001

  • Представление в стандарте IEEE-754: 0100001101000000000000000000000000000000000000000000000000000001

Представление числа 9007199254740994.0 в формате IEEE-754, чего не скажешь о   9007199254740993.0, достижимо без какой-либо потери точности. Следовательно, результат 9007199254740994 == 9007199254740994.0 на Python будет равен True.

Как в СPython реализуется сравнение чисел с плавающей точкой

Выше мы рассмотрели представление трёх чисел в формате IEEE-754 и упомянули, что в Python не выполняется неявное расширение целых чисел до чисел двойной точности. Именно этим и объясняются неожиданные результаты тестовых сценариев, которые обсуждались в сети X.

Но, если вы хотите подробнее разобраться в этой теме и узнать, как именно в Python сравниваются целые числа и числа с плавающей точкой — читайте далее.

В CPython есть функция, в которой числа с плавающей точкой сравниваются как объекты — это float_richcompare. Она определяется в файле floatobject.c.

Функция float_richcompare, определяемая в файле floatobject.c — та самая, при помощи которой в CPython реализуется сравнение чисел с плавающей точкой.
Функция float_richcompare, определяемая в файле floatobject.c — та самая, при помощи которой в CPython реализуется сравнение чисел с плавающей точкой.

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

Часть 1: сравнение Float и Float

Python — это язык с динамической типизацией. Следовательно, когда интерпретатор вызывает эту функцию для обработки оператора ==, она «не представляет», каковы конкретные типы операндов. Функция должна определить конкретные типы и действовать соответственно. В первой части сравнивающей функции проверяется, относятся ли оба объекта к типу float (число с плавающей точкой), и в этом случае речь идёт о сравнении значений с двойной точностью, лежащих в их основе.

На следующем рисунке показан первый фрагмент функции:

Первая часть алгоритма: обрабатывает сравнение float vs float, а также случай, если  v бесконечна.
Первая часть алгоритма: обрабатывает сравнение float vs float, а также случай, если  v бесконечна.

Тут подсвечены и пронумерованы различные части. Давайте по порядку разберёмся, что здесь происходит:

  1. В i и j содержатся базовые значения с двойной точностью для v и w, а в r содержится окончательный результат сравнения.

  2. Когда эту функцию вызывает интерпретатор, уже известно, что аргумент v относится к типу double, для этого здесь и предусмотрено условие для проверки утверждения (assert condition). Причём, базовое значение двойной точности присваивается i.

  3. Далее проверяется, является ли w также объектом float в Python. Если так, то можно просто присвоить базовое значение двойной точности переменной j и напрямую сравнить два этих значения.

  4. Но, если w не является объектом float в Python, то нужно предусмотреть раннюю проверку, на тот случай, если в качестве значения v задано infinity. В таком случае переменной j присваивается значение 0.0, поскольку конкретное значение w непринципиально при сравнении его с бесконечностью.

Часть 2: Сравнение Float и Long

Если w в Python является не числом с плавающей точкой, а целым числом, то всё становится ещё интереснее. Алгоритм рассчитан на то, чтобы в целом ряде случаев избегать прямого сравнения. Рассмотрим все эти случаи по очереди.

В первом случае обрабатывается ситуация, когда v и w противоположны по знаку. В таком случае нет необходимости сравнивать конкретные значения v и w, именно так и устроен код в следующем листинге:

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

Давайте охарактеризуем каждую из пронумерованных частей этого листинга:

  1. В этой строке мы убеждаемся, что w — это целочисленный объект Python.

  2. vsign и wsign имеют тот же знак, что v и w соответственно.

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

Часть 2.1: w — огромное целое число

Далее также рассмотрим простой случай, в котором число w настолько велико, что определённо окажется больше, чем любое значение двойной точности (кроме бесконечности, но случай с бесконечностью уже рассмотрен выше). Данная ситуация рассмотрена в следующем листинге:

Часть 2.1: Обработка случая, в котором w — это огромное целое число, которое определённо больше, чем любое значение двойной точности.
Часть 2.1: Обработка случая, в котором w — это огромное целое число, которое определённо больше, чем любое значение двойной точности.

  1. Функция _PyLong_NumBits возвращает, сколько бит было использовано для представления целочисленного объекта w. Но, если целочисленный объект так велик, что в типе size_t не умещается нужное количество разрядов, то такая ситуация обозначается возвратом -1.

  2. Таким образом, если число w просто огромно, то оно определённо будет больше, чем любое значение двойной точности. В данном случае сравнение не составляет труда.

Часть 2.2: Когда w помещается в тип double

Следующий случай также прост. Если w умещается в тип double, то мы можем просто привести его к значению двойной точности, а затем сравнить два значения двойной точности. Код показан в следующем листинге:

Часть 2.2: Обрабатываем случай, когда w умещается в 48 разрядов. В таком случае его можно привести к значению двойной точности, и сравнение не составляет труда.
Часть 2.2: Обрабатываем случай, когда w умещается в 48 разрядов. В таком случае его можно привести к значению двойной точности, и сравнение не составляет труда.

Стоит подчеркнуть, что 48 разрядов используется в качестве критерия, по которому определяют, расширить ли до числа двойной точности целочисленное значение, лежащее в основе w. Не уверен, почему в данном случае было выбрано 48 разрядов, а не 54 (в последнем случае вышеописанного отказа не произошло бы) или какое-либо иное значение. Может быть, требовалась железная уверенность, что вероятность переполнения исключена на любой платформе? Не знаю.

Часть 2.3 Сравнение порядков

Большинство этих случаев специально подбирались так, чтобы не приходилось фактически сравнивать значения int и float. Последний и окончательный выход, позволяющий избежать прямого сравнения чисел — сравнивать их порядки. Если порядки у них в нормализованной форме отличаются, то действительно, достаточно сравнить порядки. Если порядок числа больше, то и число больше (предполагается, что v и w положительны).

Чтобы извлечь порядок значения с двойной точностью в v, в коде CPython применяется функция frexp из стандартной библиотеки C. Функция frexp принимает значение двойной точности x и делит его на две части: нормализованное дробное значение f и порядок e, так что x = f * 2 ^ e. Диапазон нормализованной дробной части f равен [0.5, 1).

Например, рассмотрим значение 16.4. Его двоичное представление — 10000.0110011001100110011. Чтобы превратить его в нормализованную дробную часть в соответствии с определением frexp, нужно сдвинуть правый бит на 5 позиций, и в результате получится 0.100000110011001100110011 * 2^5. Следовательно, нормализованное дробное значение будет 0.512500, а порядок — 5.

Что касается w — это целое число, поэтому его порядок просто равен количеству разрядов в нём, то есть. nbits. Теперь давайте рассмотрим код для этого случая:

Часть 2.3: Сравнение порядков двух чисел в их нормализованной дробной форме
Часть 2.3: Сравнение порядков двух чисел в их нормализованной дробной форме

Давайте по отдельности разберём все пронумерованные элементы:

  1. Сначала нужно убедиться, что значение v положительное.

  2. Затем при помощи функции frexp число i разделяется на нормализованную часть и порядок

  3. Далее проверяется, не является ли порядок v отрицательным или меньшим, чем порядок w. Если какое-то из этих условий выполняется, то v определённо меньше, чем w.

  4. Напротив, если порядок v больше, чем порядок w, то v больше, чем w.

Часть 2.4: Порядок обоих чисел одинаков

Это последняя и наиболее сложная часть нашей функции сравнение. Здесь у нас есть только один выход — непосредственно сравнить два числа.

На данном этапе уже известно, что порядок v и w одинаков, и это значит, что в обоих этих числах для представления целочисленных значений используется одинаковое количество разрядов. Таким образом, чтобы сравнить v и w, достаточно сравнить целочисленное значение v с w.

Чтобы разделить v на целочисленную и дробную часть, в коде CPython используется функция modf из стандартной библиотеки C. Например, если функция modf получит на вход значение 3.14, то разделит его на целочисленную часть 3 и дробную 0.14.

Как правило, должно быть достаточно сравнить целочисленные значения v и w, но только не в случае, если эти значения равны. Например, если v=5.75 и w=5, то их целочисленные значения равны, но фактически v больше w. В таких случаях при сравнении требуется учитывать и дробную часть значения v.

Для этого в коде CPython делается простой фокус. Если дробная часть v ненулевая, то целочисленные значения v и w сдвигаются влево на 1, после чего ведущий знаковый бит целочисленного значения v устанавливается в 1.

Зачем нужна эта операция сдвига влево и установки ведущего знакового бита?

  • Сдвигая влево целочисленные значения v и w, мы просто умножаем их на 2. Если у v и w были одинаковые целочисленные значения, то от этого ничего не изменится. Если w было больше v, то в результате оно немного увеличится, но результат сравнения останется прежним.

  • Когда мы задаём ведущий знаковый бит целочисленного значения v, оно просто увеличивается на 1. Такой инкремент позволяет учесть то дробное значение, которое входило в состав v. В рассматриваемом случае у v и w были равные целочисленные значения. Поэтому, после установки ведущего знакового бита целочисленное значение v будет на 1 больше, чем у w. Но, если w было больше v, то такое увеличение целочисленного значения v на 1 ничего не изменит.  

  • Например, если v=5.75 и w=5, то целочисленное значение у обоих равно 5. Сдвинув его влево на 1, получим 10. Если установить ведущий знаковый бит для целочисленного значения v, то станет равно 11, а w останется 10. Таким образом, мы получим верный результат, так как 11 > 10. С другой стороны, если v=5.75, а w=6, то, умножив их целочисленные значения на 2, получим 10 и 12 соответственно. Прибавив 1 к целочисленному значению v, получим 11. Но  w всё равно останется больше, и мы получим верный результат.

Ниже приведён листинг, описывающий эту часть кода:

Часть 2.4: Последний случай: сравнение конкретных значений
Часть 2.4: Последний случай: сравнение конкретных значений

А теперь разбор:

  1. fracpart и intpart содержат дробное и целочисленное значения v. vv и ww  — это целочисленные объекты Python (с бесконечной точностью), в которых представлены целочисленные значения v и w.

  2. Они вызывают функцию modf, чтобы извлечь целочисленную и дробную часть v.

  3. В этой части обрабатывается ситуация, когда у v ненулевая дробная часть. Как видите, vv и ww сдвигаются влево на 1, после чего ведущий знаковый бит vv устанавливается в 1.

  4. Теперь, чтобы узнать возвращаемое значение, остаётся всего лишь сравнить два целочисленных значения vv и ww.

Резюмируем алгоритм сравнения чисел с плавающей точкой в Python

Давайте обобщим весь алгоритм, уже не обращаясь к коду:

  1. Если и v, и w — это числа с плавающей точкой (объекты float), то Python просто сравнивает заложенные в них значения двойной точности.

  2. Но, если объект w — это целое число, то:

    1. Если числа противоположны по знаку, то достаточно сравнить их знаки.

    2. Иначе, если w — это огромное целое число (в Python точность целых чисел не ограничена), то этап сравнения конкретных чисел также можно пропустить, поскольку w больше.

    3. Если w умещается в 48 разрядов или менее, то Python преобразует w в число двойной точности, а затем напрямую сравнивает значения двойной точности чисел v и w.

    4. Иначе, если порядки v и w в нормализованной дробной форме не равны, то для сравнения чисел достаточно сравнить их порядки.

    5. Если ничего из вышеперечисленного не помогло, то сравниваем сами числа. Для этого разбиваем v на целочисленную и дробную часть, а затем сравниваем целочисленную часть v с w. (При этом мы учитываем дробную часть v).

Возвращаемся к нашей задаче

Опираясь на все наши знания о стандарте IEEE-754 и о том, как в CPython сравниваются числа с плавающей точкой, вернёмся к тестовым сценариям и попробуем порассуждать об их выводе.

Сценарий 1: 9007199254740992 == 9007199254740992.0

>>> 9007199254740992 == 9007199254740992.

True

>>> 

Имеем v=9007199254740992.0 и w=9007199254740992.

Мы уже выяснили мантиссу и порядок 9007199254740992.0. Порядок этого числа 53, а мантисса 0000000000000000000000000000000000000000000000000000.

Кроме того, число 9007199254740992 — это 2^53, то есть, для представления этого числа в памяти необходимо 54 разряда (nbits=54)

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

  • w — это целое число, поэтому часть 1 неприменима

  • Знак у v и w одинаков, поэтому часть 2 неприменима

  • w умещается в 54 разряда, т.e., оно не слишком велико, поэтому часть 2.1 неприменима

  • w требуется более 48 разрядов, поэтому часть 2.2 неприменима

  • Порядок как для v, так и для w в нормализованной дробной форме равен 54, т.e., порядки у них равные, поэтому часть 2.3 неприменима

  • Так мы приходим к последней части, 2.4. Давайте её разберём.

Нам требуется извлечь из v как целочисленную, так и дробную часть, прибавить единицу к целочисленной части, если дробная часть ненулевая, а затем сравнить целочисленное значение с w.

В данном случае у v=9007199254740992.0 целочисленная часть равна 9007199254740992, а дробная часть равна 0. Целочисленное значение w также равно 9007199254740992. Поэтому Python непосредственно сравнивает два целых числа и возвращает результат True.

Сценарий 2: 9007199254740993 == 9007199254740993.0

>>> 9007199254740993 == 9007199254740993.

False

>>> 

Такого результата мы не ожидали. Давайте его проанализируем.

Имеем v=9007199254740993.0 и w=9007199254740993

Оба эти значения на 1 больше, чем значения, рассмотренные в предыдущем сценарии, т.е., v = w = 2^53 + 1.

В двоичном представлении 9007199254740993 это 100000000000000000000000000000000000000000000000000001.

Напомню, что, когда мы нашли представление, соответствующее стандарту IEEE-754, выяснилось, что это число невозможно представить точно, и его представление такое же, как у 9007199254740992.0.

Поэтому в Python, фактически, сравниваются числа 9007199254740993 и 9007199254740992.0. Давайте посмотрим, что же происходит внутри алгоритма CPython.

Точно, как и в предыдущем сценарии, оказываемся в последней части алгоритма (2.4), где требуется извлечь целочисленную и дробную часть v, а затем сравнить целочисленную часть со значением w.

Внутрисистемно 9007199254740993.0 фактически представлено как 9007199254740992.0 , поэтому целочисленная часть равна 9007199254740992. При этом значение w равно 9007199254740993. Поэтому при сравнении двух этих значений получим False.

В языке с неявным расширением численных типов w со значением 9007199254740993 также было бы представлено как 9007199254740992.0, и при сравнении мы получили бы результат True.

Сценарий 3: 9007199254740994 == 9007199254740994.0

>>> 9007199254740994 == 9007199254740994.

True

>>> 

В отличие от предыдущего сценария, 9007199254740994.0 можно в точности представить в соответствии с форматом IEEE-754. Вот из чего оно состоит:

  • Знаковый разряд: 0

  • Порядок: 53 + 1023 (сдвиг) = 1076 (10000110100 в двоичной системе)

  • Мантисса: 0000000000000000000000000000000000000000000000000001

Здесь мы также добираемся до последней части алгоритма, требующей сравнить целочисленные части v и w. В данном случае их значения одинаковы, поэтому, проверив их на равенство, получим результат True.

Заключение

Стандарт IEEE-754 и арифметика чисел с плавающей точкой по определению сложны, и сравнивать числа с плавающей точкой — нетривиальная задача. В некоторых языках, например, C и Java, реализуется неявное расширение типов, что позволяет преобразовывать целые числа в числа двойной точности, а затем побитово их сравнивать. Правда, и такой подход может приводить к неожиданным результатам из-за потери точности.

Python в данном отношении уникален. В нём используются целые числа неограниченной разрядности, поэтому во многих случаях расширять типы попросту невозможно. Поэтому в Python для сравнения таких чисел применяется собственный специализированный алгоритм, и в этом алгоритме есть свои пограничные случаи.  

Независимо от того, с каким языком вы работаете — C, Java, Python или каким-нибудь другим, при сравнении чисел с плавающей точкой рекомендуется пользоваться библиотечными функциями, а не сравнивать числа напрямую — так можно обойти потенциальные подводные камни.

Честно говоря, до того, как писать эту статью, я никогда не задумывался, как именно в Python сравниваются целые числа и числа с плавающей точкой. Теперь, разобрав эту проблему, я чувствую, что стал увереннее ориентироваться в сложной математике чисел с плавающей точкой. Надеюсь, что и вы тоже!

Комментарии (31)


  1. MountainGoat
    31.05.2024 21:33
    #26886957
    +11

    Любопытно, конечно, но программисту на Питоне это знать нет необходимости.

    А нужно знать: ни на одном языке вообще нельзя сравнивать дробные числа на равенство!


    1. Sap_ru
      31.05.2024 21:33
      #26886981
      +2

      Вообще-вообще?


      1. MountainGoat
        31.05.2024 21:33
        #26886985
        +4

        Ну за Матлабы всякие не говорю, но вроде не один общий язык не гарантирует что 0.1 + 0.2 == 1.2 / 4.0 в любом случае.


        1. Sap_ru
          31.05.2024 21:33
          #26887019
          +9

          А если вы получаете параметр и вам нужно узнать то же самое это число или другое, чтобы понять, нужно ли пересчитывать всё, что от этого параметра зависит, то тоже сравнивать нельзя? А то после таких мощных утверждений всякие умельцы goto по-убирают, а потом оказывается, что есть алгоритмы, которые без него нормально и не запрограммируешь, и сидят с кодом, в котором хрен разберёшься. А некоторые, после громких заявлений и исключения поубирали и теперь страдают, но едят кактус и делают вид, что так оно и надо. А кто-то дженерики по-убирал. А одни даже обычный цикл по целым числами убрали и range вместо него кривыми болтами прикрутили, и только через 10 лет добавили кривую-косую оптмизицию в свой for-each.
          Это я к тому, что поймал себя на мысли, что мне неприлично часто приходится сравнивать на равенство плавающие числа. Повезло вот так. Есть же ситуаций, где можно и нужно сравнивать float/double, просто нужно понимать что, зачем и как оно работает. А если программист не знает ничего о представлении плавающих чисел, то хреновый он программист, и потому всё равно найдёт из чего себе в ногу выстрелить. Ведь есть же ещё переполнения, потеря точности при математических операциях, фокусы с округлениями и приведением к целому, не-числа и бесконечности и куча всего другого интересного, что произрастает из двоичного представления чисел.


          1. MountainGoat
            31.05.2024 21:33
            #26887113
            +7

            А если вы получаете параметр и вам нужно узнать то же самое это число или другое

            Советую вот так:

            static inline bool qFuzzyCompare(float p1, float p2)
{
    return (qAbs(p1 - p2) * 100000.f <= qMin(qAbs(p1), qAbs(p2)));
}

            Это кусок Qt.


            1. vk6677
              31.05.2024 21:33
              #26887555
              +1

              Вот так нетривиально, да и с "магическим числом" авторы Qt рассчитывают относительную погрешность в 0,001%.


              1. MountainGoat
                31.05.2024 21:33
                #26887563
                +1

                И что?


                1. vk6677
                  31.05.2024 21:33
                  #26887797
                  +3

                  Из названия функции непонятно, что это относительное, а не абсолютное сравнение. А так же оно некорректно сработает при p1 == 0.0. Ладно, если известно что сравнение будет с нулём. А если p1 или p2 получены в результате предыдущих расчётов и содержит 0.

                  Возможно, эти тонкости и отражены в документации. Но сравнение с нулём может получиться неожиданно. Это потребует дополнительной проверки.


          1. CrazyOpossum
            31.05.2024 21:33
            #26887719
            +4

            abs(a - b) < 1e-5


            1. leotrubach
              31.05.2024 21:33
              #26893485

              Вообще, лучше делать при помощи isclose()

              import math 

a = 0.1 + 0.2
b = 1.2 / 4
print(math.isclose(a, b))

              так как играет роль ещё и большие это числа или маленькие.


        1. miksoft
          31.05.2024 21:33
          #26888145

          SQL с типами DECIMAL/NUMBER с этим вполне справляется - https://www.db-fiddle.com/f/dkCP69QF5eEup8GLVuSGT5/1
          Хотя и в SQL бывают заморочки.


    1. Krasnoarmeec
      31.05.2024 21:33
      #26887017
      +1

      Это-то понятно, обычно сравнивают модуль разности чисел и некую дельта 10^{-9}-10^{-20}. Напрягает то, что в этом случае дельта равна единице!

      Что-то боязно стало использовать Питон.


      1. RH215
        31.05.2024 21:33
        #26888559

        обычно сравнивают модуль разности чисел и некую дельта

        А вот неправильно делают. Так можно делать только если примерно известен порядок сравниваемых чисел. Проблема из поста актуальна практически для всех языков, которые используют нативные float. Например, go:

        p := 9007199254740992.0
q := 9007199254740993.0
log.Printf("%f, %f, %t\n", p, q, p == q)

        Получаем на выходе:

           9007199254740992.000000, 9007199254740992.000000, true


    1. nronnie
      31.05.2024 21:33
      #26887383
      +6

      Я бы уточнил, что не "дробные", а "с плавающей точкой".


    1. ptr128
      31.05.2024 21:33
      #26887859
      +3

      Не дробные, а с плавающей запятой. Числа с фиксированной запятой сравниваются без проблем.


    1. netch80
      31.05.2024 21:33
      #26888177
      +2

      ни на одном языке вообще нельзя сравнивать дробные числа на равенство!

      Можно и нужно - но, понимая, что именно делаешь и почему. И имея в виду возможные проблемы от реализации. А вот если не понимать... вот тут целое собачье кладбище зарыто.

      В обсуждаемом случае сравнение int и float - это не сравнение двух float. Это отдельный вариант (хоть внутри и получается конверсия к float (double), но она замаскирована видом констант). И последствия от него примерно такие же, как в JS ситуация типа "ваш номер карточки 4.1492103e+15". Это больше проблема типизации, чем собственно сравнение floatʼов.

      Сравнение floatʼов на равенство вредно тогда, когда мы говорим о результатах вычислений с заведомо приближёнными значениями (типично для прикладной математики всех видов выше, чем 4 арифметические операции). Вот там появляется правило про корректный выбор относительной погрешности (каковой выбор ещё надо осилить, не всегда сразу получается адекватная погрешность).

      А вот если значения по каким-то причинам точные (или гарантированно точные, или результат однозначно определённых операций типа i*0.01), тогда и точное сравнение возможно. Также есть случаи сравнения с нулём, как признак полной потери значения (даже не денормализованные). Но очень часто само по себе такое сравнение подсказывает, что выбрана неверная модель представления числа.

      В финансовых расчётах точное сравнение возможно и нужно. Но тут вопрос, с какого момента может начаться недопустимое округление. Всякие Decimal из С# маскируют проблему до предела, давая аж до 28 знаков точности... обычно хватает. Но с фиксированной точкой таки честнее (и проблема, если что, выскочит явно).

      Но попросту, конечно, можно сказать "нельзя!" и это будет как деление на ноль ;)


  1. zergon321
    31.05.2024 21:33
    #26887001

    Плюс один вопрос на собесах


  1. AC130
    31.05.2024 21:33
    #26887029
    +21

    Я не очень понял при чём тут Питон. IEEE 754 флоаты имеют динамическую разрешающую способность, и начиная с какого-то достаточно большого числа машинное эпсилон (т.е. расстояние между двумя соседними флоатами сетки представления) становится больше единицы. Числа в сетке начинают идти через 2, потом через 4, потом через 8 и т.п. А обычные инты в Питоне -- biginteger, у них разрешающая способность везде равна 1. Вполне логично, что когда шаг сетки будет достаточно большой (т.е. само число достаточно большое по модулю), bigint будет представлять целые числа точнее, чем IEEE 754 float (по-крайней мере, 64-битный флоат, я не знаю, может другие представления у них с какими-то нюансами сделаны). Это должно быть так в любом языке, не только в Питоне. В чём мысль то?


    1. adeshere
      31.05.2024 21:33
      #26887181
      +13

      Числа в сетке начинают идти через 2, потом через 4, потом через 8 и т.п. А обычные инты в Питоне -- biginteger, у них разрешающая способность везде равна 1

      Именно что. Когда-то я вручную подбирал алгоритм отбрасывания лишних (незначащих) цифр при печати разных значений (потребовалось). И для удобства погружения в задачу даже для себя

      картинку наглядную сделал
      Особенности преобразования целых в real*4 и обратно. Пояснение - ниже в тексте. P.S. Прошу прощения, но картинка выложена в том виде, как я ее использовал. Кому такой формат не очень удобен - берите идею, и рисуйте по-своему ;-)
      Особенности преобразования целых в real*4 и обратно. Пояснение - ниже в тексте.
      P.S. Прошу прощения, но картинка выложена в том виде, как я ее использовал.
      Кому такой формат не очень удобен - берите идею, и рисуйте по-своему ;-)

      На верхнем графике (бокс 1) показан ряд натуральных чисел, заданных, как целые, и затем сохраненных в 4-байтовом Real, а на графике (5) - ряд округленных (дискретизированных до целого) приращений между последовательными значениями ряда (1). Видно, что для значений от 0 и до примерно 16 800 000 приращения равны 1, что и должно быть в идеале. Но далее до 33 600 000 приращения чередуются 0/2; далее до 67 000 000 идет чередование 0/4 и т.д. Это означает, что минимальный шаг между соседними Real равен (в целочисленном представлении) 1, 2, 4 и т.д. Другими словами, по мере роста целых значений они округляются к ближайшему Real со все большей погрешностью, которая начинает превышать шаг между integer уже начиная с 16 млн.

      На графиках 2-4 и 6-8 показаны аналогичные пары для рядов вида real(N)+1.0, realN)+0.5 и realN)+0.3. Видно, что раньше всего - начиная со значений 8 400 000 - точность представления теряется для ряда вида real[целое]+0.5. 8 400 000 - это как раз тот порог, где шаг между соседними real достигает 0.5 При этом числа вида real[целое]+0.5 округляются то в одну сторону, то в другую.

      И то же самое в числах: если число равно XXX, то шаг между соседними представимыми real*4-числами равен (с округлением) YYY:
      XXX YYY
      16 800 000 2
      1 680 000 0.2
      168 000 0.02
      16 800 0.002
      1 680 0.0002
      168 0.000 02
      16.8 0.000 0002
      1.68 0.000 000 02
      0.168 0.000 000 002

      Если число равно XXX, то ближайшее real-представимое значение
      отличается на YYY. Чтобы точность десятичной записи соответствовала
      точности машинного представления real-чисел, в записи должно быть
      NNN знаков после десятичной точки:
      XXX YYY NNN
      8 400 000 1 0
      840 000 0.1 1
      84 000 0.01 2
      8 400 0.001 3
      840 0.0001 4
      84 0.00001 5
      8.4 0.000001 6
      0.84 0.0000001 7
      0.084 0.00000001 8

      UPD: что-то насчет графика 6 сомнения у меня возникли сейчас - точно ли там real(N)+1.0. В в моем readme к картинке вроде бы так, но могла опечатка закрасться. Давно уже очень дело было, а пересчитывать сейчас некогда.


    1. vitaliy2
      31.05.2024 21:33
      #26888761
      +1

      Я когда читал, не заметил точку в конце второго числа, поэтому удивился, что два одинаковых BigInt при сравнении дают false. В реальности же в конце второго числа стоит точка, из-за чего оно хранится как float. Получается сравнение 9007199254740993 == 9007199254740992.0, что логично даёт false.


  1. LatypovAlbert
    31.05.2024 21:33
    #26887695
    +1

    Не стоит сравнивать float числа с помощью оператора ==. Можно сравнивать так или использовать модуль decimal:

    num = 0.1 + 0.1 + 0.1
eps = 0.000000001           # точность сравнения
if abs(num - 0.3) < eps:    # число num отличается от числа 0.3 менее чем 0.000000001
    print('YES')
else:
    print('NO')


    1. redfox0
      31.05.2024 21:33
      #26888093

      esp = 1e-9


  1. Zara6502
    31.05.2024 21:33
    #26887723
    +4

    откровения западных коллег иногда на уровне "ой, солнышко вышло из-за гор, папа, а это почему?" Хотя судя по имени ABHINAV UPADHYAY - это скорее индусский первооткрыватель.


  1. ptr128
    31.05.2024 21:33
    #26887875
    +7

    Самое интересное начинается при регистровой оптимизации. Регистры FPU в x86-64 80-битные. А числа с плавающей запятой в памяти - 64 битные. Поэтому сравнение (a*b)==c может оказаться истинным или ложным, в зависимости от того, сохранялся ли результат произведения в память, или оставался в регистре FPU.


    1. DungeonLords
      31.05.2024 21:33
      #26888257
      +4

      А ещё есть известный баг под названием баг 323 в x86 компьютерах.


      1. ptr128
        31.05.2024 21:33
        #26888301
        +1

        Великолепная статья! Мне больше повезло, так как программа была намного проще Вашей и разница в ассемблерном коде сразу бросилась в глаза. Тоже выкрутился volatile.


  1. sci_nov
    31.05.2024 21:33
    #26887965

    Еперный бабай, так он же точку в конце вторых чисел поставил)


  1. goldexer
    31.05.2024 21:33
    #26888023
    +2

    Подожди как, но ведь числа из начала статьи выглядят как целое, без точек и дробной части.

    В Python целочисленное значение сравнивается с представлением числа с плавающей точкой

    Знаете, наверно программистов разбаловали, но вообще хотелось бы, чтобы целочисленное (БЕЗ явно назначенной конвертации в плавающую точку) всегда равнялось самому себе, без условностей, что где-то там, под капотом, язык как-то по-другому себе это представляет и потому... К числам с плавающей точкой вопросов нет.


    1. vvzvlad
      31.05.2024 21:33
      #26888963

      >Знаете, наверно программистов разбаловали, но вообще хотелось бы, чтобы целочисленное (БЕЗ явно назначенной конвертации в плавающую точку) всегда равнялось самому себе, без условностей, что где-то там, под капотом, язык как-то по-другому себе это представляет и потому... 

      Так там же вторая половина оканчивается на .0 что и равносильно явно конвертации во флоат


      1. goldexer
        31.05.2024 21:33
        #26889097

        Оканчивается на «.», а не «.0». Числа длинные и «xxxxx.0» было бы гораздо заметнее, чем просто «xxxxx.» Потому сразу и незаметно было, это уже сильно позже присмотрелся. Спасибо)

        Так то да, тогда всё сходится. Ни при каких обстоятельствах никие плавающие напрямую сравнивать нельзя.


  1. sci_nov
    31.05.2024 21:33
    #26888563
    +1

    В текущем python наоборот всё корректно сделано в плане арифметики. Например, целочисленное деление отрицательного целого числа на положительное с остатком даёт корректный остаток - неотрицательный, в отличие например от С++.

    То, что сравнивается bigint целое с числом с "точкой" ограниченной разрядности, это само по себе некорректно. Если ты поставил точку после числа, то оно - число с плавающей точкой. В С++ аналогично, только там целые по умолчанию ограничены по разрядности.