Início / coding / Perguntas / 78932341
Accepted
dspyz
Asked: 2024-08-30 21:47:03 +0800 CST

Por que 2x - x == x na precisão de ponto flutuante IEEE?

  • 772

Eu esperaria que isso só acontecesse quando o último bit da mantissa fosse 0. Caso contrário, para subtraí-los (já que seus expoentes diferem em 1), xperderia um pouco de precisão primeiro e o resultado acabaria sendo arredondado para cima ou para baixo.

Mas um experimento rápido mostra que isso parece sempre valer (assumindo que xe 2xsão finitos) para qualquer número aleatório (incluindo aqueles com um 1bit à direita).

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
python

3 respostas

  1. Quando você faz a aritmética manualmente, verá por que isso sempre vale. Sim, nas partes menos significativas você às vezes está fazendo xyz10 - wxyz1. Mas você também está subtraindo a parte mais significativa, então há espaço para a precisão total na parte inferior. Essa propriedade é conhecida como lema de Sterbenz . (Esse link fornece uma prova mais longa e formal.)

    • 4
  2. Best Answer

    Se tivéssemos que fazer aritmética somente no formato de ponto flutuante, mesmo para valores internos durante a aritmética, então, sim, 2*x - xnem sempre produziria x. Por exemplo, com significandos de quatro bits, poderíamos ter:

    Expressão Valor/Cálculo
    x 1.001•2 0 (9)
    2*x 1.001•2 1 (18)
    2*x - x 1,001•2 1 − 1,001•2 0
    = 1,001•2 1 − 0,100•2 1 (operando deslocado para a direita e perdido um bit)
    = 0,101•2 1 = 1,010•2 0 (10).

    No entanto, não é assim que as implementações de ponto flutuante funcionam. Para obter os resultados corretos, elas usam mais dígitos internamente ou algoritmos mais sofisticados ou ambos. O IEEE-754 especifica que o resultado de uma operação elementar é o valor que você obteria ao calcular o resultado aritmético exato do número real sem erro ou arredondamento ou limitações em dígitos e, em seguida, arredondar esse número real para o valor mais próximo representável no formato de destino, usando a regra de arredondamento em vigor para a operação. (Mais comumente, essa regra de arredondamento é arredondar para o valor mais próximo, desempatando em favor daquele com um dígito baixo par em seu significando.)

    Uma consequência desse requisito é que, se o resultado matemático for representável no formato, o resultado computado deve ser esse resultado matemático. Quando o resultado matemático é representável, nunca há erro de arredondamento em uma operação elementar implementada corretamente.

    • 4

  3. Sejam x e y os valores reais representados pelos floats xe 2*x. Multiplicar por 2 é exato: a mantissa permanece a mesma, apenas o expoente aumenta em 1. Então y = 2x. Então você subtrai. A subtração de float nem sempre pode resultar na diferença real, pois isso pode não ser representável como float. Mas é especificado para dar o valor mais próximo que é representável como float (ou um mais próximo em caso de empate). E aqui, a diferença real é yx = 2x-x = x, e isso é representável como float, pois é com isso xque começamos.

    No seu outro caso 4*x - 3*x, multiplicar por 4 é novamente exato (o expoente simplesmente é aumentado em 2). Mas multiplicar por 3 geralmente não é. Quando a mantissa é ímpar, multiplicar por 3 exigiria mais um bit na nova mantissa. Esse bit é perdido, você obtém um float cujo valor é ligeiramente menor ou ligeiramente maior que 3 vezes o valor de x. Então, quando você subtrai, um dos dois valores pode já ser "impreciso". A subtração também pode levar a um resultado geral "impreciso", ou a subtração pode ser imprecisa também e cancelar a imprecisão anterior, de modo que você obtém exatamente x. Mas o problema é o 3*x, não a subtração. Quando 3*xtambém é exato, então, assim como no 2*x - xcaso, todas as operações são exatas e o resultado geral é exatamente x.

    Como a subtração é capaz de fazer o cálculo para que o resultado seja o valor mais próximo representável por float? Eu acho que geralmente com alguns bits extras ou inteligência durante o cálculo. Mas eu não acho que o padrão defina como as implementações devem calcular o resultado corrigido, ele só se importa com *que" elas o façam.

    • 0

relate perguntas