Почему 2x - x == x в точности с плавающей запятой IEEE?
Я ожидаю, что это будет действовать только тогда, когда последний бит мантиссы равен 0. В противном случае, чтобы их вычесть (поскольку их показатели степени отличаются на 1), x сначала потеряет немного точности, и результат будет либо округлен в большую, либо в меньшую сторону.
Но быстрый эксперимент показывает, что, похоже, это всегда справедливо (при условии, что x и 2x конечны) для любого случайного числа (включая те, у которых есть завершающий бит 1).
import random
import struct
from collections import Counter
def float_to_bits(f: float) -> int:
"""
Convert a double-precision floating-point number to a 64-bit integer.
"""
# Pack the float into 8 bytes, then unpack as an unsigned 64-bit integer
return struct.unpack(">Q", struct.pack(">d", f))[0]
def check_floating_point_precision(num_trials: int) -> float:
true_count = 0
false_count = 0
bit_counts = Counter()
for _ in range(num_trials):
x = random.uniform(0, 1)
if 2 * x - x == x:
true_count += 1
else:
false_count += 1
bits = float_to_bits(x)
# Extract the last three bits of the mantissa
last_three_bits = bits & 0b111
bit_counts[last_three_bits] += 1
return (bit_counts, true_count / num_trials)
num_trials = 1_000_000
(bit_counts, proportion_true) = check_floating_point_precision(num_trials)
print(f"The proportion of times 2x - x == x holds true: {proportion_true:.6f}")
print("Distribution of last three bits (mod 8):")
for bits_value in range(8):
print(f"{bits_value:03b}: {bit_counts[bits_value]} occurrences")
The proportion of times 2x - x == x holds true: 1.000000
Distribution of last three bits (mod 8):
000: 312738 occurrences
001: 62542 occurrences
010: 125035 occurrences
011: 62219 occurrences
100: 187848 occurrences
101: 62054 occurrences
110: 125129 occurrences
111: 62435 occurrences
Изменит ли «оптимизация» компилятора фактическое значение вывода? Это кажется плохим
Для величин значений, с которыми вы работаете, умножение на 2 изменяет только показатель степени без изменения мантиссы. Вычитание почти равных значений может привести к потере точности, но 2*x на порядок больше, чем x.
@chepner Пожалуйста, прочитайте описание. Я ожидаю, что разница в показателе степени в 1 будет иметь значение, когда речь идет о равенстве с плавающей запятой. Я обнаружил, что 4x - 3x примерно в половине случаев кажется равным x (то есть 4x - 3x имеет поведение, которое я ожидал от 2x - x). Похоже, что вычитание имеет на один бит больше точности, чем мантисса, и я надеялся, что кто-нибудь сможет это подтвердить или указать мне на ресурс или что-то в этом роде.
@Progman Я вижу, вы добавили тег python к этому вопросу. Являются ли числа с плавающей запятой в Python не просто стандартными числами с плавающей запятой двойной точности IEEE-754, которые используются в каждом языке?
Кстати, может ли кто-нибудь объяснить, почему мой вопрос так сильно отвергается?
@dspyz Технически, Python не дает никаких обещаний относительно float; это любые типы с плавающей запятой, предоставляемые базовой платформой. На практике я никогда не видел ничего, что не обеспечивало бы арифметику с плавающей запятой IEEE-754.
Вы можете увидеть больше вариаций, если не ограничиваете себя значениями от 0 до 1; попробуйте другой единичный интервал, например, начиная с гораздо больших значений. (Вы неравномерно выбираете действительные числа от 0 до 1.)
Я рекомендую вам добавить пример, который показывает другой результат для 4*x - 3*x, поскольку это дает совпадение примерно на 60%, а не на 100%.
@JonSG Моя интуиция подсказывает, что на самом деле это 50%, и причина, по которой это выглядит как 60, заключается в том, что оказывается, что Python random.uniform не так уж однороден в младших битах
Ответы 3
Когда вы выполните арифметические действия вручную, вы поймете, почему это всегда справедливо. Да, в наименее значимых моментах вы иногда делаете xyz10 - wxyz1. Но вы также вычитаете самый значимый бит, поэтому внизу остается место для полной точности. Это свойство известно как лемма Штербенца. (Эта ссылка дает более длинное и формальное доказательство.)
Если бы нам приходилось выполнять арифметические действия только в формате с плавающей запятой, даже для внутренних значений во время арифметики, то да, 2*x - x не всегда давало бы x. Например, с четырехбитными мантиссами мы могли бы иметь:
x
1.001•20 (9)
2*x
1.001•21 (18)
2*x - x
1.001•21 − 1.001•20= 1.001•21 − 0.100•21 (сдвинут правый операнд и немного потерян)
= 0.101•21 = 1.010•20 (10).
Однако реализации с плавающей запятой работают не так. Чтобы получить правильные результаты, они используют либо больше цифр внутри, либо более сложные алгоритмы, либо и то, и другое. IEEE-754 определяет, что результатом элементарной операции является значение, которое вы могли бы получить, вычислив точный результат арифметических операций с действительным числом без ошибок, округлений или ограничений на цифры, а затем округлив это действительное число до ближайшего значения, представимого в формате назначения. , используя правило округления, действующее для операции. (Чаще всего правило округления заключается в округлении до ближайшего значения, разрывая связи в пользу значения с четной младшей цифрой в мантиссе.)
Следствием этого требования является то, что, если математический результат представим в формате, вычисленный результат должен быть этим математическим результатом. Когда математический результат представим, в правильно реализованной элементарной операции никогда не возникает ошибок округления.
Объясняет ли это, почему 2x -x == x всегда верно, а 4x - 3x == x верно только в 60% случаев? Я не знаю, так это или нет. Если да, то это здорово, но, возможно, было бы еще лучше показать, почему второй пример не работает.
@JonSG: Масштаб чисел не имеет значения для чисел с плавающей запятой, если он находится в пределах формата. Примеры будут работать так же, если вы умножите их все на 1024, 1/512 или другие степени двойки. Причина 4*x - 3*x не всегда будет x в том, что 3• x не всегда представимо, поэтому иногда 3*x будет иметь некоторую ошибку округления. Тогда 4*x - 3*x может не дать x, потому что он не вычисляет 4•x−3•x, а вычисляет 4•x−y, где y — некоторое число, близкое к 3•x, но не равное ему.
Итак, x всегда представляется как «некое значение с плавающей запятой», а 2x и 4x всегда могут быть представлены правильно, поскольку они представляют собой степени 2, умноженные на что-то с плавающей запятой, в то время как 3x не всегда может быть представлено правильно и иногда должно быть округлено до ближайшего значения. Этот звук, верно?
@JonSG: Да, для двоичных чисел с плавающей запятой числа 2•x и 4•x всегда представимы. (Для других оснований, возможно, нет. Например, при четырехзначном десятичном числе 7,003 представимо, но 2•7,003 = 14,006 непредставимо, поскольку для этого требуется 5 цифр. Умножение на основание всегда имеет представимый результат, поэтому 10• Для числа 7,003 = 70,03 требуется всего 4 цифры, и оно представимо.)
В любом случае, всегда представимо, пока вы не нажмете на переполнение.
Пусть x и y будут реальными значениями, представленными числами с плавающей запятой x и 2*x. Умножение на 2 является точным: мантисса остается прежней, просто показатель степени увеличивается на 1. Итак, y = 2x. Потом вычитаешь. Вычитание числа с плавающей запятой не всегда может привести к реальной разнице, поскольку ее нельзя представить как число с плавающей запятой. Но указано, что оно дает ближайшее значение, которое можно представить как число с плавающей запятой (или ближайшее в случае связей). И здесь реальная разница равна y-x = 2x-x = x, и это можно представить как число с плавающей запятой, поскольку это x, с которого мы начали.
В другом случае 4*x - 3*x умножение на 4 снова является точным (показатель степени просто увеличивается на 2). Но умножение на 3 обычно не так. Если мантисса нечетная, для умножения на 3 потребуется еще один бит в новой мантиссе. Этот бит теряется, и вы получаете число с плавающей точкой, значение которого либо немного меньше, либо немного больше, чем в 3 раза превышает значение x. Поэтому, когда вы затем вычитаете, одно из двух значений уже может быть «неточным». Тогда вычитание также может привести к «неточному» общему результату, или вычитание также может быть неточным и компенсировать предыдущую неточность, так что вы получите ровно x. Но проблема в 3*x, а не в вычитании. Если 3*x также точно, то, как и в случае 2*x - x, все операции точны и общий результат равен точно x.
Как вычитание может выполнить расчет так, чтобы результатом было ближайшее значение, представимое с плавающей запятой? Я обычно думаю с некоторыми дополнительными битами или хитростью во время вычислений. Но я не думаю, что стандарт определяет, как реализации должны вычислять исправленный результат, его просто волнует, что они это делают.
Проявляется ли такое же поведение, когда
2*xиxпоступают из вызовов функций? Можно предположить, что2*x - x == xможет быть оптимизирован компилятором.