égalité des points flottants en Python et en général
j'ai un morceau de code qui se comporte différemment selon que je passe par un dictionnaire pour obtenir des facteurs de conversion ou si je les utilise directement.
le code suivant s'affichera 1.0 == 1.0 -> False
Mais si vous remplacez factors[units_from]10.0 et factors[units_to ]1.0 / 2.54 il va print 1.0 == 1.0 -> True
#!/usr/bin/env python
base = 'cm'
factors = {
'cm' : 1.0,
'mm' : 10.0,
'm' : 0.01,
'km' : 1.0e-5,
'in' : 1.0 / 2.54,
'ft' : 1.0 / 2.54 / 12.0,
'yd' : 1.0 / 2.54 / 12.0 / 3.0,
'mile' : 1.0 / 2.54 / 12.0 / 5280,
'lightyear' : 1.0 / 2.54 / 12.0 / 5280 / 5.87849981e12,
}
# convert 25.4 mm to inches
val = 25.4
units_from = 'mm'
units_to = 'in'
base_value = val / factors[units_from]
ret = base_value * factors[units_to ]
print ret, '==', 1.0, '->', ret == 1.0
Permettez-moi d'abord de dire que je suis assez sûr de ce qui se passe ici. Je l'ai déjà vu en C, mais jamais en Python. mis en œuvre en C, nous le voyons.
je sais que les nombres à virgule flottante vont changer les valeurs allant d'un registre CPU à cache et retour. Je sais que la comparaison de ce qui devrait être deux variables égales retournera false si l'un d'eux a été bipé tandis que l'autre est resté résident dans un registre.
Questions
- Quelle est la meilleure façon d'éviter ce type de problèmes?... En Python ou en général.
- est-ce que je fais quelque chose complètement tort?
Note
Cela fait évidemment partie d'un exemple dépouillé, mais ce que j'essaie de faire est de venir avec des classes de longueur, de volume, etc. qui peuvent comparer avec d'autres objets de la même classe, mais avec des unités différentes.
Questions Rhétoriques
- S'il s'agit d'un problème potentiellement dangereux puisqu'il fait se comporter les programmes dans une matière non étermanistique, devrait les compilateurs avertissent ou d'erreur quand ils détectent que vous vérifiez l'égalité des flotteurs
- les compilateurs devraient-ils prendre en charge une option pour remplacer tous les contrôles d'égalité des flotteurs par une fonction "assez proche"?
- est-ce que les compilateurs le font déjà et je n'arrive pas à trouver l'information.
8 réponses
Comme l'a montré la comparaison de deux flotteurs (ou doubles, etc) peut être problématique. En général, au lieu de les comparer pour obtenir l'égalité exacte, il faudrait les comparer à une limite d'erreur. Si elles sont comprises dans la limite d'erreur, elles sont considérées comme égales.
C'est beaucoup plus facile à dire qu'à faire. La nature de la virgule flottante rend une limite d'erreur fixe Sans valeur. Une petite limite d'erreur (comme 2 * float_epsilon) fonctionne bien lorsque les valeurs sont proches de 0.0, mais échouera si la valeur est proche de 1000. Un limite d'erreur pour des valeurs aussi grandes que 1.000.000.0 sera beaucoup trop laxiste pour des valeurs proches de 0.0.
la meilleure solution est de connaître le domaine de vos mathématiques et de choisir un approriate err lié sur une base de cas par cas.
Lorsque cela est impossible ou si vous êtes paresseux, Unités dans la Dernière Place (ULPs) est une solution très nouvelle et robuste. Les détails complets sont assez impliqués, vous pouvez lire plus ici.
L'idée de base est cela, un flottant nombre a deux pièces, mantissa et exposant. Généralement, les erreurs d'arrondi seulement changer la mantisse par quelques mesures. Lorsque la valeur est proche de 0.0 ceux mesures sont exactement float_epsilon. Lorsque la valeur de la virgule flottante est plus proche de 1 000 000, Les Pas seront presque aussi grands que 1.
Google test utilise ULP pour comparez les nombres à virgule flottante. Ils ont choisi un défaut de 4 ULPs pour deux nombres à virgule flottante à comparer égal. Vous pouvez également utiliser leur code comme référence pour construire votre propre comparateur flottant de style ULP.
La différence est que si vous remplacez factors[units_to ]1.0 / 2.54, vous êtes en train de faire:
(base_value * 1.0) / 2.54
avec le dictionnaire, vous faites:
base_value * (1.0 / 2.54)
l'ordre d'arrondissement est important. C'est plus facile de voir si vous n':
>>> print (((25.4 / 10.0) * 1.0) / 2.54).__repr__()
1.0
>>> print ((25.4 / 10.0) * (1.0 / 2.54)).__repr__()
0.99999999999999989
notez qu'il n'y a pas de comportement non-déterministe ou non défini. Il existe une norme, IEEE-754, à laquelle les implémentations doivent se conformer (pour ne pas prétendre qu'elles sont toujours ).
je ne pense pas qu'il devrait y avoir un automatique remplacement assez proche. C'est souvent un moyen efficace de traiter le problème, mais il devrait être au programmeur de décider si et comment l'utiliser.
enfin, il y a bien sûr des options pour l'arithmétique de précision arbitraire, y compris python-gmp et décimal. Pense que si vous avez réellement besoin ces, parce qu'ils ont un impact significatif sur les performances.
Il n'y a pas de problème avec déplacement entre les registres réguliers et le cache. Vous pensez peut-être aux 80 bits de x86!--28-->précision étendue.
laissez-moi d'abord répondre en disant que vous devriez lire le classique de David Goldberg Ce Que Tout Informaticien Devez Savoir À Propos De L'Arithmétique À Virgule Flottante.
comme d'autres commentateurs l'ont déjà dit, la divergence que vous remarquez est intrinsèquement due au modèle à virgule flottante et n'a rien à voir avec les registres, le cache ou la mémoire.
selon le modèle à virgule flottante, 2,54 est en fait représenté comme
>>> 2859785763380265 * 2 ** -50
2.54
ce la représentation, cependant, n'est pas exacte:
>>> from fractions import Fraction
>>> float(Fraction(2859785763380265, 2 ** 50) - Fraction(254, 100))
3.552713678800501e-17
Maintenant, l'expression d'évaluation est:
>>> 25.4 / 10 * (1/2.54)
0.99999999999999989
le problème réside dans Le 1/2.54:
>>> Fraction.from_float(1/2.54)
Fraction(1773070719437203, 4503599627370496)
Mais ce que vous attendez est
>>> 1/Fraction.from_float(2.54)
Fraction(1125899906842624, 2859785763380265)
Pour répondre à tes questions:
- un problème difficile, mais clairement déterministe,rien de mystérieux.
- Vous ne pouvez pas remplacer automatiquement l'égalité avec un assez comparaison. Dans ce dernier cas, vous devez spécifier une tolérance, qui dépend du problème en question, c'est-à-dire du type de précision que vous attendez de vos résultats. Il ya aussi beaucoup de situations où vous voulez vraiment l'égalité pas un assez comparaison.
Merci pour vos réponses. La plupart étaient très bons et ont fourni de bons liens donc je vais juste dire cela et répondre à ma propre question.
Caspin a posté ceci lien.
il a également mentionné que Google Tests utilisé la comparaison ULP et quand j'ai regardé le code google, j'ai vu qu'ils ont mentionné le même lien exact à cygnus-software.
j'ai fini par implémenter certains des algorithmes en C comme extension Python et j'ai découvert plus tard que je pouvais le faire en pur Python. Le code est affiché en dessous.
à la fin, je vais probablement juste finir par ajouter des différences ULP à mon sac de trucs.
il était intéressant de voir combien de points flottants se situent entre ce qui devrait être deux nombres égaux qui n'ont jamais quitté la mémoire. Un des articles ou le code google que j'ai lu dit que 4 était un bon nombre... mais ici, j'ai réussi à en atteindre 10.
>>> f1 = 25.4
>>> f2 = f1
>>>
>>> for i in xrange(1, 11):
... f2 /= 10.0 # to cm
... f2 *= (1.0 / 2.54) # to in
... f2 *= 25.4 # back to mm
... print 'after %2d loops there are %2d doubles between them' % (i, dulpdiff(f1, f2))
...
after 1 loops there are 1 doubles between them
after 2 loops there are 2 doubles between them
after 3 loops there are 3 doubles between them
after 4 loops there are 4 doubles between them
after 5 loops there are 6 doubles between them
after 6 loops there are 7 doubles between them
after 7 loops there are 8 doubles between them
after 8 loops there are 10 doubles between them
after 9 loops there are 10 doubles between them
after 10 loops there are 10 doubles between them
il est également intéressant de noter le nombre de points flottants entre des nombres égaux quand l'un d'eux est écrit en tant que chaîne et lu en arrière dedans.
>>> # 0 degrees Fahrenheit is -32 / 1.8 degrees Celsius
... f = -32 / 1.8
>>> s = str(f)
>>> s
'-17.7777777778'
>>> # floats between them...
... fulpdiff(f, float(s))
0
>>> # doubles between them...
... dulpdiff(f, float(s))
6255L
import struct
from functools import partial
# (c) 2010 Eric L. Frederich
#
# Python implementation of algorithms detailed here...
# from http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm
def c_mem_cast(x, f=None, t=None):
'''
do a c-style memory cast
In Python...
x = 12.34
y = c_mem_cast(x, 'd', 'l')
... should be equivilent to the following in c...
double x = 12.34;
long y = *(long*)&x;
'''
return struct.unpack(t, struct.pack(f, x))[0]
dbl_to_lng = partial(c_mem_cast, f='d', t='l')
lng_to_dbl = partial(c_mem_cast, f='l', t='d')
flt_to_int = partial(c_mem_cast, f='f', t='i')
int_to_flt = partial(c_mem_cast, f='i', t='f')
def ulp_diff_maker(converter, negative_zero):
'''
Getting the ulp difference of floats and doubles is similar.
Only difference if the offset and converter.
'''
def the_diff(a, b):
# Make a integer lexicographically ordered as a twos-complement int
ai = converter(a)
if ai < 0:
ai = negative_zero - ai
# Make b integer lexicographically ordered as a twos-complement int
bi = converter(b)
if bi < 0:
bi = negative_zero - bi
return abs(ai - bi)
return the_diff
# double ULP difference
dulpdiff = ulp_diff_maker(dbl_to_lng, 0x8000000000000000)
# float ULP difference
fulpdiff = ulp_diff_maker(flt_to_int, 0x80000000 )
# default to double ULP difference
ulpdiff = dulpdiff
ulpdiff.__doc__ = '''
Get the number of doubles between two doubles.
'''
si je lance ce
x = 0.3+0.3+0.3
if (x != 0.9): print "not equal"
if (x == 0.9): print "equal"
il imprime "pas égal" ce qui est faux mais comme
x-0.9
donne le flotteur d'erreur comme -1.11022302 e-16 je viens de faire quelque chose comme ceci:
if (x - 0.9 < 10**-8): print "equal (almost)"
sinon vous pouvez convertir les deux en chaînes, je suppose:
if (str(x) == str(0.9)): print "equal (strings)"
Quelle est la meilleure façon d'éviter les problèmes de cette façon?... En Python ou en général.
quel problème? Vous travaillez avec des mesures physiques. Sauf si vous avez quelques vraiment équipement sophistiqué, l'erreur dans vos mesures va être de plusieurs ordres de grandeur supérieure à virgule flottante epsilon. Alors pourquoi écrire un code qui dépend de nombres exacts à 16 chiffres significatifs?
les compilateurs devraient-ils prendre en charge une option pour remplacer toutes flottent des vérifications d'égalité avec une fonction "assez proche"?
Si il l'a fait, vous devez obtenir certains résultats étranges:
>>> float.tolerance = 1e-8 # hypothetical "close enough" definition
>>> a = 1.23456789
>>> b = 1.23456790
>>> c = 1.23456791
>>> a == b
True
>>> b == c
True
>>> a == c
False
Si vous pensez que c'est assez dur pour stocker flotte dans un dictionnaire maintenant, essayez avec un non-transitive == opérateur de! Et la performance serait nulle, parce que le seul moyen de garantir x == y→ hash(x) == hash(y) pour chaque flotteur d'avoir le même code de hachage. Et ce serait incompatible avec l'ints.
afin de comparer les flotteurs, en général, de comparer la valeur absolue de la différence des flotteurs d'un delta qui est assez petit pour s'adapter à vos besoins.
Questions Rhétoriques
- C' **EST un problème dangereux ** comme il pourrait cacher des erreurs ou de générer une boucle infinie si une telle comparaison est utilisé comme critère d'arrêt.
- Moderne compilateurs C/C++ avertir pour la comparaison des flotteurs pour l'égalité
- tous les vérificateurs de code statique que je connais seront les erreurs de sortie pour les langues que j'utilise
je suppose que c'est la même chose pour python, comme le delta à utiliser pour la comparaison peut varier, il doit être à l'opérateur de choisir. Ce qui signifie qu'aucune bonne transformation par défaut ne peut être fournie entièrement automatiquement.
aussi intéressant est le nombre de points flottants là sont entre un nombre égal quand l'un d'eux est écrit comme un string et de lire de nouveau.
c'est sans doute un bug Python. Ce numéro a été écrit avec de douze chiffres. Deux identifient de façon unique un double 64 bits (type float de Python) vous avez besoin de dix-sept chiffres de mantissa. Si Python a imprimé ses nombres avec 17 chiffres de précision alors vous seriez garanti de revenir exactement le même valeur.
la question de la précision est discutée à: http://randomascii.wordpress.com/2012/03/08/float-precisionfrom-zero-to-100-digits-2/
l'accent est mis sur flotteur 32 bits (qui nécessite neuf chiffres de mantissa pour identifier chaque numéro de façon unique) mais il mentionne brièvement double, et le fait qu'il nécessite 17 chiffres de mantissa.