Como lidar com a multiplicação de números próximos de 1

StackOverflow https://stackoverflow.com/questions/717994

Pergunta

Eu tenho vários números de ponto flutuante (duplas de Java), a maioria dos quais está muito próxima de 1, e preciso multiplicá-los como parte de um cálculo maior.eu tenho que fazer isso bastante.

O problema é que, embora o Java duplique, não há problema com um número como:

0.0000000000000000000000000000000001 (1.0E-34)

eles não podem representar algo como:

1.0000000000000000000000000000000001

Conseqüentemente, perco a precisão rapidamente (o limite parece estar em torno de 1,00000000000001 para as duplas do Java).

Considerei apenas armazenar os números com 1 subtraído, então, por exemplo, 1,0001 seria armazenado como 0,0001 - mas o problema é que para multiplicá-los novamente tenho que somar 1 e neste ponto perco a precisão.

Para resolver isso, eu poderia usar BigDecimals para realizar o cálculo (converter para BigDecimal, adicionar 1,0 e multiplicar) e depois converter novamente para doubles, mas tenho sérias preocupações sobre as implicações disso no desempenho.

Alguém consegue ver uma maneira de fazer isso que evite o uso do BigDecimal?

Edite para maior clareza:Isto é para um filtro colaborativo em grande escala, que emprega um algoritmo de otimização de gradiente descendente.A precisão é um problema porque muitas vezes o filtro colaborativo lida com números muito pequenos (como a probabilidade de uma pessoa clicar no anúncio de um produto, que pode ser 1 em 1.000 ou 1 em 10.000).

A velocidade é um problema porque o filtro colaborativo deve ser treinado em dezenas de milhões de pontos de dados, se não mais.

Foi útil?

Solução

Sim: Porque

(1 + x) * (1 + y) = 1 + x + y + x*y

No seu caso, x e y são muito pequenos, então x*y vai ser distante menor - muito pequeno para influenciar os resultados do seu cálculo. Então, no que diz respeito a você,

(1 + x) * (1 + y) = 1 + x + y

Isso significa que você pode armazenar os números com 1 subtraído e, em vez de multiplicar, basta adicioná -los. Desde que os resultados sejam sempre muito menores que 1, eles estarão próximos o suficiente dos resultados matematicamente precisos que você não se importará com a diferença.

EDITAR: Só notei: você diz a maioria deles estão muito próximos de 1. Obviamente, essa técnica não funcionará para números que não estão próximos de 1 - ou seja, se x e y são grandes. Mas se um é grande e um é pequeno, ainda pode funcionar; Você só se importa com a magnitude do produto x*y. (E se ambos os números não estiverem próximos de 1, você poderá usar Java regular double multiplicação...)

Outras dicas

Talvez você possa usar logaritmos?

Os logaritmos reduzem convenientemente a multiplicação para a adição.

Além disso, para cuidar da perda de precisão inicial, existe o log1p da função (pelo menos, existe em C/C ++), que retorna log (1+x) sem perda de precisão. (por exemplo, log1p (1e-30) retorna 1e-30 para mim)

Em seguida, você pode usar o EXPM1 para obter a parte decimal do resultado real.

Não é esse tipo de situação exatamente para que serve o BigDecimal?

Editado para adicionar:

"De acordo com o parágrafo do segundo eixo, eu preferiria evitar conceitos fiéis, se possível, por motivos de desempenho". - Sanidade

"Otimização prematura é a raiz de todo o mal" - Knuth

Existe uma solução simples praticamente feita sob encomenda para o seu problema. Você está preocupado, pode não ser rápido o suficiente, então você quer fazer algo complicado que você acho será mais rápido. A citação de Knuth às vezes é usada em excesso, mas essa é exatamente a situação contra a qual ele estava alertando. Escreva da maneira simples. Teste-o. Perfil IT. Veja se é muito lento. Se for então Comece a pensar em maneiras de torná -lo mais rápido. Não adicione todo esse código adicional complexo e propenso a bugs até saber que é necessário.

Dependendo de onde os números vêm e como você os usa, você pode querer usar racionais em vez de flutuantes.Não é a resposta certa para todos os casos, mas quando é a resposta certa não há outra.

Se os racionais não se encaixarem, eu endossaria a resposta dos logaritmos.

Edite em resposta à sua edição:

Se você estiver lidando com números que representam baixas taxas de resposta, faça o que os cientistas fazem:

  • Represente-os como excesso/déficit (normalize a parte 1,0)
  • Dimensione-os.Pense em termos de “partes por milhão” ou o que for apropriado.

Isso deixará você lidando com números razoáveis ​​para cálculos.

Vale a pena notar que você está testando os limites do seu hardware em vez de Java. O Java usa o ponto flutuante de 64 bits na sua CPU.

Sugiro que você teste o desempenho do BigDecimal antes de assumir que não será rápido o suficiente para você. Você ainda pode fazer dezenas de milhares de cálculos por segundo com BigDecimal.

Como David aponta, você pode simplesmente adicionar as compensações.

(1 + x) * (1 + y) = 1 + x + y + x * y

No entanto, parece arriscado optar por abandonar o último período. Não. Por exemplo, tente o seguinte:

x = 1e-8 y = 2e-6 z = 3e-7 w = 4e-5

O que é (1+x)(1+y)(1+z)*(1+w)? Em dupla precisão, eu entendo:

(1+x)(1+y)(1+z)*(1+w)

Ans =

      1.00004231009302

No entanto, veja o que acontece se apenas fizermos a aproximação aditiva simples.

1+(x+y+z+w)

Ans =

            1.00004231

Perdemos os bits de baixa ordem que podem ter sido importantes. Isso é apenas um problema se algumas das diferenças de 1 no produto forem pelo menos SQRT (EPS), onde o EPS é a precisão em que você está trabalhando.

Tente isso em vez disso:

f = @(u, v) u + v + u*v;

resultado = f (x, y);

resultado = f (resultado, z);

resultado = f (resultado, w);

1+resultado

Ans =

      1.00004231009302

Como você pode ver, isso nos leva de volta ao resultado de dupla precisão. De fato, é um pouco mais preciso, pois o valor interno do resultado é 4.23100930230249E-05.

Se você realmente precisar da precisão, precisará usar algo como BigDecimal, mesmo que seja mais lento que o dobro.

Se você realmente não precisa da precisão, talvez possa ir com a resposta de David. Mas mesmo se você usar muito multiplicações, pode ser uma otimização prematura, então BigDecimal pode ser o caminho a seguir de qualquer maneira

Quando você diz "a maioria dos quais está muito próxima de 1", quantos, exatamente?

Talvez você possa ter uma compensação implícita de 1 em todos os seus números e apenas trabalhar com as frações.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top