Solutions aux erreurs d'arrondi à virgule flottante

18

En créant une application qui traite de nombreux calculs mathématiques, j'ai rencontré le problème que certains nombres provoquent des erreurs d'arrondi.

Bien que je comprenne que la virgule flottante n'est pas exacte , le problème est de savoir comment gérer les nombres exacts pour m'assurer que lorsque les calculs sont effectués sur eux, l'arrondi en virgule flottante ne pose aucun problème?

JNL
la source
2
Y a-t-il un problème spécifique auquel vous êtes confronté? Il existe de nombreuses façons de faire des tests, bien pour certains problèmes. Les questions qui peuvent avoir plusieurs réponses sont mal adaptées au format Q&R. Il serait préférable que vous puissiez définir le problème que vous rencontrez d'une manière qui pourrait avoir une bonne réponse plutôt que de jeter un filet d'idées et de recommandations.
Je construis une application logicielle avec beaucoup de calculs mathématiques. Je comprends que les tests NUNIT ou JUNIT seraient bons, mais j'aimerais avoir une idée sur la façon d'aborder les problèmes avec les calculs mathématiques.
JNL
1
Pouvez-vous donner un exemple de calcul que vous testeriez? Un ne serait généralement pas un test unitaire de mathématiques brutes (sauf si vous testez vos propres types numériques), mais tester quelque chose comme le distanceTraveled(startVel, duration, acceleration)serait.
Un exemple portera sur les décimales. Par exemple, disons que nous construisons un mur avec des paramètres spéciaux pour dist x-0 à x = 14,589, puis quelques dispositions de x = 14,589 à x = extrémité du mur. La distance .589 lors de la conversion en binaire n'est pas la même .... Surtout si nous ajoutons quelques distances ... comme 14,589 + 0,25 ne sera pas égal à 14,84 en binaire .... J'espère que ce n'est pas déroutant?
JNL
1
@MichaelT merci d'avoir édité la Question. Beaucoup aidé. Depuis que je suis nouveau dans ce domaine, pas trop bon sur la façon de formuler les questions. :) ... Mais ce sera bien bientôt.
JNL

Réponses:

22

Il existe trois approches fondamentales pour créer d'autres types numériques sans arrondi flottant. Le thème commun avec ceux-ci est qu'ils utilisent à la place des mathématiques entières de différentes manières.

Rationnels

Représentez le nombre dans sa totalité et un nombre rationnel avec un numérateur et un dénominateur. Le nombre 15.589serait représenté par w: 15; n: 589; d:1000.

Lorsqu'il est ajouté à 0,25 (qui est w: 0; n: 1; d: 4), cela implique de calculer le LCM, puis d'ajouter les deux nombres. Cela fonctionne bien dans de nombreuses situations, mais peut entraîner de très grands nombres lorsque vous travaillez avec de nombreux nombres rationnels relativement premiers les uns par rapport aux autres.

Un point fixe

Vous avez la partie entière et la partie décimale. Tous les nombres sont arrondis (il y a ce mot - mais vous savez où il se trouve) avec cette précision. Par exemple, vous pourriez avoir un point fixe avec 3 points décimaux. 15.589+ 0.250devient l'addition 589 + 250 % 1000pour la partie décimale (puis tout report à la partie entière). Cela fonctionne très bien avec les bases de données existantes. Comme mentionné, il y a un arrondi, mais vous savez où il se trouve et pouvez le spécifier de manière à ce qu'il soit plus précis que nécessaire (vous ne mesurez qu'à 3 décimales, alors faites-le fixe à 4).

Virgule fixe flottante

Stockez une valeur et la précision. 15.589est stocké comme 15589pour la valeur et 3pour la précision, tandis que 0.25est stocké comme 25et 2. Cela peut gérer une précision arbitraire. Je crois que c'est ce que les internes des utilisations BigDecimal de Java (ne l'ont pas examiné récemment) utilisent. À un moment donné, vous souhaiterez le retirer de ce format et l'afficher - et cela peut impliquer l'arrondi (encore une fois, vous contrôlez où il se trouve).


Une fois que vous avez déterminé le choix de la représentation, vous pouvez soit trouver des bibliothèques tierces existantes qui l'utilisent, soit écrire les vôtres. Lorsque vous écrivez le vôtre, assurez-vous de le tester à l'unité et assurez-vous de bien faire les calculs.


la source
2
C'est un bon début, mais bien sûr, cela ne résout pas complètement le problème d'arrondi. Les nombres irrationnels comme π, e et √2 n'ont pas de représentation strictement numérique; vous devez les représenter symboliquement si vous voulez une représentation exacte, ou les évaluer le plus tard possible si vous voulez juste minimiser l'erreur d'arrondi.
Caleb
@Caleb pour les irrationnels, il faudrait les évaluer au-delà de là où tout arrondi pourrait causer des problèmes. Par exemple, 22/7 est précis à 0,1% de pi, 355/113 est précis à 10 ^ -8. Si vous travaillez uniquement avec des nombres à 3 décimales, la présence de 3,141592653 devrait éviter toute erreur d'arrondi à 3 décimales.
@MichaelT: Pour ajouter des nombres rationnels, vous n'avez pas besoin de trouver le LCM et il est plus rapide de ne pas le faire (et plus rapide pour annuler les "zéros LSB" après, et ne simplifie que lorsque c'est absolument nécessaire). Pour les nombres rationnels en général, ce n'est généralement que "numérateur / dénominateur" seul, ou "numérateur / dénominateur << exposant" (et non "partie entière + numérateur / dénominateur"). Votre "virgule flottante fixe" est également une représentation en virgule flottante, et serait mieux décrit comme "virgule flottante de taille arbitraire" (pour le distinguer de "virgule flottante de taille fixe").
Brendan
une partie de votre terminologie est un peu incertaine - le point fixe flottant n'a pas de sens - je pense que vous essayez de dire décimal flottant.
jk.
10

Si les valeurs en virgule flottante ont des problèmes d'arrondi et que vous ne voulez pas avoir à rencontrer de problèmes d'arrondi, il s'ensuit logiquement que la seule solution consiste à ne pas utiliser de valeurs en virgule flottante.

Maintenant, la question devient, "comment puis-je faire des mathématiques impliquant des valeurs non entières sans variables à virgule flottante?" La réponse est avec des types de données de précision arbitraire . Les calculs sont plus lents car ils doivent être implémentés dans le logiciel plutôt que dans le matériel, mais ils sont précis. Vous n'avez pas dit quel langage vous utilisez, donc je ne peux pas recommander un package, mais il existe des bibliothèques de précision arbitraires disponibles pour les langages de programmation les plus populaires.

Mason Wheeler
la source
J'utilise VC ++ en ce moment ... Mais j'apprécierais également plus d'informations concernant d'autres langages de programmation.
JNL
Même sans valeurs à virgule flottante, vous rencontrerez toujours des problèmes d'arrondi.
Chad
2
@Chad True, mais le but n'est pas d'éliminer les problèmes d'arrondi (qui existeront toujours, car dans toute base que vous utilisez, il y a des nombres qui n'ont pas de représentation exacte, et vous n'avez pas de mémoire et de puissance de traitement infinies), c'est de réduisez-la au point qu'elle n'a aucun effet dans le calcul que vous essayez de faire.
Iker
@Iker Vous avez raison. Bien que vous, ni la personne posant la question, n'ayez spécifié quels calculs précis ils tentent de réaliser et quelle précision ils souhaitent. Il doit d'abord répondre à cette question avant de se lancer dans la théorie des nombres. Dire lot of mathematical calculationsn'est pas utile ni donner les réponses. Dans la grande majorité des cas (si vous ne traitez pas avec des devises), le flotteur devrait vraiment suffire.
Chad
@Chad c'est un bon point, il n'y a certainement pas assez de données de l'OP pour dire quel est exactement le niveau de précision dont ils ont besoin.
Iker
7

L'arithmétique en virgule flottante est généralement assez précise (15 chiffres décimaux pour a double) et assez flexible. Les problèmes surgissent lorsque vous faites des calculs, ce qui réduit considérablement le nombre de chiffres de précision. Voici quelques exemples:

  • Annulation à la soustraction:, le 1234567890.12345 - 1234567890.12300résultat 0.0045n'a que deux chiffres décimaux de précision. Cela se produit chaque fois que vous soustrayez deux nombres de magnitude similaire.

  • Avalage de précision: 1234567890.12345 + 0.123456789012345évalue à 1234567890.24691, les dix derniers chiffres du deuxième opérande sont perdus.

  • Multiplications: si vous multipliez deux nombres à 15 chiffres, le résultat contient 30 chiffres qui doivent être stockés. Mais vous ne pouvez pas les stocker, donc les 15 derniers bits sont perdus. Ceci est particulièrement gênant lorsqu'il est combiné avec un sqrt()(comme dans sqrt(x*x + y*y): Le résultat n'aura que 7,5 chiffres de précision.

Ce sont les principaux pièges dont vous devez être conscient. Et une fois que vous en êtes conscient, vous pouvez essayer de formuler vos mathématiques d'une manière qui les évite. Par exemple, si vous devez incrémenter une valeur encore et encore dans une boucle, évitez de faire ceci:

for(double f = f0; f < f1; f += df) {

Après quelques itérations, la plus grande favalera une partie de la précision de df. Pire encore, les erreurs s'additionneront, conduisant à la situation contre-intuitive qu'un plus petit dfpeut conduire à de moins bons résultats globaux. Mieux vaut écrire ceci:

for(int i = 0; i < (f1 - f0)/df; i++) {
    double f = f0 + i*df;

Étant donné que vous combinez les incréments en une seule multiplication, le résultat fsera précis à 15 chiffres décimaux.

Ceci n'est qu'un exemple, il existe d'autres façons d'éviter la perte de précision pour d'autres raisons. Mais cela aide déjà beaucoup à réfléchir à l'ampleur des valeurs impliquées et à imaginer ce qui se passerait si vous faisiez vos calculs avec un stylo et du papier, en arrondissant à un nombre fixe de chiffres après chaque étape.

cmaster - réintégrer monica
la source
2

Comment vous assurer que vous n'avez pas de problèmes: renseignez-vous sur les problèmes d'arithmétique à virgule flottante, ou embauchez quelqu'un qui en a, ou utilisez votre bon sens.

Le premier problème est la précision. Dans de nombreuses langues, vous avez "float" et "double" (double pour "double precision"), et dans de nombreux cas, "float" vous donne une précision d'environ 7 chiffres, tandis que double vous en donne 15. Le bon sens est que si vous avez un situation où la précision pourrait être un problème, 15 chiffres est bien mieux que 7 chiffres. Dans de nombreuses situations légèrement problématiques, l'utilisation de "double" signifie que vous vous en sortez, et "float" signifie que vous ne le faites pas. Disons que la capitalisation boursière d'une entreprise est de 700 milliards de dollars. Représentez cela en float, et le bit le plus bas est 65536 $. Représentez-le en double, et le bit le plus bas est d'environ 0,012 cent. Donc, à moins que vous ne sachiez vraiment, vraiment ce que vous faites, vous utilisez double, pas flottant.

Le deuxième problème est davantage une question de principe. Si vous effectuez deux calculs différents qui devraient donner le même résultat, ils ne le font souvent pas en raison d'erreurs d'arrondi. Deux résultats qui devraient être égaux seront "presque égaux". Si deux résultats sont proches, les valeurs réelles peuvent être égales. Ou ils pourraient ne pas l'être. Vous devez garder cela à l'esprit et devez écrire et utiliser des fonctions qui disent que "x est certainement supérieur à y" ou "x est certainement inférieur à y" ou "x et y peuvent être égaux".

Ce problème devient encore pire si vous utilisez l'arrondi, par exemple "arrondir x à l'entier le plus proche". Si vous multipliez 120 * 0,05, le résultat devrait être 6, mais ce que vous obtenez est "un nombre très proche de 6". Si vous "arrondissez à l'entier le plus proche", ce "nombre très proche de 6" peut être "légèrement inférieur à 6" et arrondi à 5. Et notez que la précision dont vous disposez n'a pas d'importance. Peu importe à quel point votre résultat est proche de 6, tant qu'il est inférieur à 6.

Et troisièmement, certains problèmes sont difficiles . Cela signifie qu'il n'y a pas de règle simple et rapide. Si votre compilateur prend en charge "long double" avec plus de précision, vous pouvez utiliser "long double" et voir si cela fait une différence. Si cela ne fait aucune différence, alors soit vous êtes OK, soit vous avez un vrai problème délicat. Si cela fait le genre de différence que vous attendez (comme un changement à la 12e décimale), alors vous êtes probablement d'accord. Si cela change vraiment vos résultats, vous avez un problème. Demander de l'aide.

gnasher729
la source
1
Il n'y a rien de "bon sens" dans les mathématiques à virgule flottante.
whatsisname
Apprenez-en plus.
gnasher729
0

La plupart des gens font l'erreur quand ils voient double, ils crient BigDecimal, alors qu'en fait ils viennent de déplacer le problème ailleurs. Double donne Bit de signe: 1 bit, Largeur d'exposant: 11 bits. Précision significative: 53 bits (52 explicitement stockés). En raison de la nature du double, plus le nombre entier est grand, plus vous perdez de précision relative. Pour calculer la précision relative que nous utilisons ici est ci-dessous.

Précision relative du double dans le calcul, nous utilisons la foluma suivante 2 ^ E <= abs (X) <2 ^ (E + 1)

epsilon = 2 ^ (E-10)% Pour un flottant de 16 bits (demi-précision)

 Accuracy Power | Accuracy -/+| Maximum Power | Max Interger Value
 2^-1           | 0.5         | 2^51          | 2.2518E+15
 2^-5           | 0.03125     | 2^47          | 1.40737E+14
 2^-10          | 0.000976563 | 2^42          | 4.39805E+12
 2^-15          | 3.05176E-05 | 2^37          | 1.37439E+11
 2^-20          | 9.53674E-07 | 2^32          | 4294967296
 2^-25          | 2.98023E-08 | 2^27          | 134217728
 2^-30          | 9.31323E-10 | 2^22          | 4194304
 2^-35          | 2.91038E-11 | 2^17          | 131072
 2^-40          | 9.09495E-13 | 2^12          | 4096
 2^-45          | 2.84217E-14 | 2^7           | 128
 2^-50          | 8.88178E-16 | 2^2           | 4

En d'autres termes, si vous souhaitez une précision de +/- 0,5 (ou 2 ^ -1), la taille maximale que le nombre peut être est de 2 ^ 52. Tout plus grand que cela et la distance entre les nombres à virgule flottante est supérieure à 0,5.

Si vous voulez une précision de +/- 0,0005 (environ 2 ^ -11), la taille maximale que le nombre peut être est 2 ^ 42. Tout plus grand que cela et la distance entre les nombres à virgule flottante est supérieure à 0,0005.

Je ne peux pas vraiment donner une meilleure réponse que cela. L'utilisateur devra déterminer la précision qu'il souhaite lors de l'exécution du calcul nécessaire et sa valeur unitaire (mètres, pieds, pouces, mm, cm). Pour la grande majorité des cas, float suffira pour des simulations simples selon l'échelle du monde que vous souhaitez simuler.

Bien que ce soit quelque chose à dire, si vous ne cherchez qu'à simuler un monde de 100 mètres par 100 mètres, vous aurez quelque part dans l'ordre de précision près de 2 ^ -45. Cela n'entre même pas dans la façon dont les FPU modernes à l'intérieur des processeurs feront des calculs en dehors de la taille du type natif et seulement une fois le calcul terminé, ils arrondiront (en fonction du mode d'arrondi du FPU) à la taille du type natif.

Tchad
la source