Comment gérer la multiplication des nombres proches de 1

Question

J'ai un tas de nombres à virgule flottante (Java double), dont la plupart sont très proches de 1, et je dois les multiplier ensemble dans le cadre d'un calcul plus. Je dois le faire beaucoup .

Le problème est que si Java doubles ont pas de problème avec un certain nombre comme:

0.0000000000000000000000000000000001 (1.0E-34)

ils ne peuvent pas représenter quelque chose comme:

1.0000000000000000000000000000000001

En conséquence de cela, je perds la précision rapidement (la limite semble être autour 1,000000000000001 pour les doubles de Java).

J'ai considérais juste comme un stockage des nombres avec 1 soustrait, donc par exemple 1,0001 seraient stockés sous forme 0,0001 - mais le problème est que de les multiplier à nouveau ensemble, je dois ajouter 1 et à ce moment je perds la précision

Pour répondre à ce que je pourrais utiliser BigDecimals pour effectuer le calcul (convertir en BigDecimal, ajouter 1,0, puis multiplier), puis reconvertir en double par la suite, mais j'avoir de graves préoccupations au sujet des conséquences sur les performances de ce sujet.

Quelqu'un peut-il voir une façon de faire qui évite d'utiliser BigDecimal?

Modifier pour plus de clarté : Ceci est un filtre de collaboration à grande échelle, qui utilise un algorithme d'optimisation de descente de gradient. La précision est un problème parce que souvent le filtre collaboratif traite un très petit nombre (comme la probabilité d'une personne en cliquant sur une annonce pour un produit, qui peut être 1 en 1000, ou 1 à 10000).

La vitesse est un problème parce que le filtre de collaboration doit être formé sur des dizaines de millions de points de données, sinon plus.

Answer 1

Eh oui: parce que

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

Dans votre cas, x et y sont très petites, donc x*y va être far plus petit - trop faible pour influencer les résultats de votre calcul. Donc, en ce qui vous concerne,

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

Cela signifie que vous pouvez enregistrer les numéros avec 1 soustraites, et au lieu de multiplier, il suffit de les additionner. Tant que les résultats sont toujours beaucoup moins que 1, ils seront assez proches des résultats mathématiquement précis que vous ne se soucient pas la différence.

EDIT : Il suffit de remarquer: vous dites plus d'entre eux sont très proches de 1. Il est évident que cette technique ne fonctionnera pas pour les numéros qui ne sont pas près de 1 - que est, si x et y sont grandes. Mais si l'on est grand et on est petit, il pourrait encore travailler; vous ne vous préoccupez l'ampleur du x*y produit. (Et si les deux chiffres ne sont pas près de 1, vous pouvez simplement utiliser la multiplication régulière Java double ...)

Answer 2

Peut-être que vous pouvez utiliser logarithmes?

logarithmes réduire facilement la multiplication à l'addition.

En outre, prendre soin de la perte de précision initiale, il y a la fonction log1p (au moins, il existe en C / C ++), qui retourne log (1 + x) sans perte de précision. (Par exemple log1p (1E-30) renvoie 1E-30 pour moi)

Ensuite, vous pouvez utiliser expm1 pour obtenir la partie décimale du résultat réel.

Answer 3

est-ce pas ce genre de situation exactement ce que BigDecimal est pour?

Sous la direction d'ajouter:

« Par le deuxième dernier paragraphe, je préférerais éviter BigDecimals si possible pour des raisons de performance. » - santé mentale

"L'optimisation prématurée est la racine de tous les maux" - Knuth

Il y a une solution simple pratiquement sur commande pour votre problème. Vous êtes préoccupé par cela pourrait ne pas être assez rapide, de sorte que vous voulez faire quelque chose de compliqué que vous penser sera plus rapide. La citation Knuth se galvaudé parfois, mais c'est exactement la situation dans laquelle il a mis en garde contre. Écrire la manière simple. Essaye-le. Profil il. Voir si elle est trop lent. S'il est puis commencer à réfléchir sur les moyens de le rendre plus rapide. Ne pas ajouter tout ce complexe supplémentaire, code sujettes aux bugs jusqu'à ce que vous savez qu'il est nécessaire.

Answer 4

Selon l'endroit où les chiffres viennent et comment vous les utilisez, vous pouvez utiliser à la place de flotteurs rationals. Pas la bonne réponse pour tous les cas, mais quand il est la bonne réponse il n'y a vraiment pas d'autre.

Si rationals ne correspondent pas, je souscris à la réponse logarithmes.

Modifier en réponse à votre edit:

Si vous traitez avec des chiffres représentant un faible taux de réponse, font ce que font les scientifiques:

• représentent les comme l'excédent / déficit (normaliser la partie 1.0)
• les échelle. Pensez en termes de « parties par million » ou tout ce qui est approprié.

Cela vous laissera jongler avec les chiffres raisonnables pour les calculs.

Answer 5

Il vaut la peine de noter que vous testez les limites de votre matériel plutôt que Java. Java utilise le virgule flottante 64 bits dans votre CPU.

Je vous suggère de tester les performances de BigDecimal avant de supposer qu'il ne sera pas assez rapide pour vous. Vous pouvez toujours faire des dizaines de milliers de calculs par seconde avec BigDecimal.

Answer 6

Comme le souligne David, vous pouvez simplement ajouter les décalages vers le haut.

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

Cependant, il semble risqué de choisir d'abandonner le dernier terme. Ne pas. Par exemple, essayez ceci:

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

Ce qui est (1 + x) (1 + y) (1 + z) * (1 + w)? En double précision, je reçois:

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

ans =

      1.00004231009302

Cependant, voir ce qui se passe si nous faisons tout simple approximation additif.

1 + (x + y + z + w)

ans =

            1.00004231

Nous avons perdu les bits de poids faible qui peuvent avoir été importants. Ceci est un problème que si certaines des différences de 1 dans le produit sont au moins sqrt (EPS), où la précision est eps vous travaillez.

Essayez ceci:

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

result = f (x, y);

result = f (résultat, z);

result = f (résultat, w);

1 + Résultat

ans =

      1.00004231009302

Comme vous pouvez le voir, cela nous ramène au résultat double précision. En fait, il est un peu plus précis, puisque la valeur interne du résultat est 4.23100930230249e-05.

Answer 7

Si vous avez vraiment besoin de la précision, vous devrez utiliser quelque chose comme BigDecimal, même si elle est plus lent que le double.

Si vous n'avez pas vraiment besoin de la précision, vous pourriez peut-être aller avec la réponse de David. Mais même si vous utilisez multiplications beaucoup, il est peut-être une certaine optimisation prématurée, donc BIGDECIMAL pourrait être le moyen d'aller de toute façon

Answer 8

Quand vous dites « dont la plupart sont très proches de 1 », combien exactement?

Peut-être que vous pourriez avoir un décalage de 1 implicite dans tous vos numéros et juste travailler avec les fractions.