Pourquoi Math.sqrt (i * i) .floor == i?

Question

Je me demande si cela est vrai: Quand je prends la racine carrée d'un nombre entier au carré, comme dans

f = Math.sqrt(123*123) 

je vais obtenir un nombre à virgule flottante très proche de 123. En raison de la précision de la représentation en virgule flottante, cela pourrait être quelque chose comme 122.99999999999999999999 ou 123.000000000000000000001. Comme floor(122.999999999999999999) est 122, je devrais obtenir 122 au lieu de 123. Donc je m'attends à ce que floor(sqrt(i*i)) == i-1 dans environ 50% des cas. Étrangement, pour tous les nombres que j'ai testés, floor(sqrt(i*i) == i. Voici un petit script ruby ​​pour tester les 100 premiers millions de nombres:

100_000_000.times do |i| 
    puts i if Math.sqrt(i*i).floor != i 
end 

Le script ci-dessus n'imprime jamais rien. Pourquoi est-ce si?

MISE À JOUR: Merci pour la réponse rapide, cela semble être la solution: Selon wikipedia

Tout entier ayant une valeur absolue inférieure inférieure ou égale à 2^24 peut être exactement représenté dans le format simple précision et tout nombre entier avec une valeur absolue inférieure ou égale à 2^53 peuvent être exactement représentés dans le format de précision double .

Math.sqrt (i * i) commence à se comporter comme je l'ai attendu à partir de ce i = 9007199254740993, qui est 2^53 + 1.

Answer 1

Pour les entiers "petits", il est généralement une représentation exacte en virgule flottante.

Answer 2

Il est pas trop difficile de trouver des cas où cela se décompose comme on peut s'y attendre:

Math.sqrt(94949493295293425**2).floor 
# => 94949493295293424 
Math.sqrt(94949493295293426**2).floor 
# => 94949493295293424 
Math.sqrt(94949493295293427**2).floor 
# => 94949493295293424 

Answer 3

Ruby Float est un nombre à virgule flottante double précision, ce qui signifie qu'il peut représenter avec précision le nombre avec (règle pouce) environ 16 chiffres décimaux significatifs. Pour les nombres à virgule flottante simple précision, il s'agit d'environ 7 chiffres significatifs.

Vous trouverez plus d'informations ici:

Ce que tout informaticien doit savoir sur Virgule flottante Arithmétique: http://docs.sun.com/source/819-3693/ncg_goldberg.html

Answer 4

est ici l'essence de votre confusion:

En raison de virgule flottante représentation précision, cela pourrait être quelque chose comme 122.99999999999999999999 ou 123.000000000000000000001.

Ceci est faux. Il sera toujours exactement 123 sur un système conforme à la norme IEEE-754, qui est presque tous les systèmes dans ces temps modernes. L'arithmétique à virgule flottante n'a pas «d'erreur aléatoire» ou de «bruit». Il a des arrondis précis et déterministes, et de nombreux calculs simples (comme celui-ci) n'entraînent aucun arrondi.

123 est exactement représentable en virgule flottante, et ainsi est 123*123 (donc tous sont entiers de taille modeste). Donc, aucune erreur d'arrondi ne se produit lorsque vous convertissez 123*123 en un type à virgule flottante. Le résultat est exactement15129.

La racine carrée est une opération correctement arrondie, conformément à la norme IEEE-754. Cela signifie que s'il y a une réponse exacte, la fonction racine carrée est nécessaire pour la produire. Puisque vous prenez la racine carrée de exactement15129, qui est exactement 123, c'est exactement le résultat que vous obtenez de la fonction de la racine carrée. Aucun arrondi ou approximation ne se produit.

Maintenant, pour quelle taille d'un nombre entier cela sera-t-il vrai? La double précision peut représenter exactement tous les entiers jusqu'à 2^53. Donc, tant que i*i est inférieur à 2^53, aucun arrondi ne se produira dans votre calcul, et le résultat sera exact pour cette raison. Cela signifie que pour tout i plus petit que 94906265, nous savons que le calcul sera exact.

Mais vous avez essayé i plus grand que ça! Que ce passe-t-il?

Pour le plus grand i que vous avez essayé, i*i est juste à peine plus grand que 2^53 (1.1102... * 2^53, en fait). Puisque les conversions d'entier en double (ou de multiplication en double) sont également correctement arrondies opérations, i*i sera la valeur représentable la plus proche du carré exact de i. Dans ce cas, puisque i*i a une largeur de 54 bits, l'arrondi se produira dans le bit le plus bas. Ainsi, nous savons que:

i*i as a double = the exact value of i*i + rounding 

où est soit -1,0, or 1. Si l'arrondi est nul, alors le carré est exact, donc la racine carrée est exacte, donc nous savons déjà que vous obtenez la bonne réponse. Ignorons ce cas.

Donc maintenant nous regardons la racine carrée de i*i +/- 1. En utilisant une valeur de cette racine carrée est l'expansion de Taylor, l'infiniment précis (unrounded):

i * (1 +/- 1/(2i^2) + O(1/i^4)) 

Maintenant, c'est un peu Checklist pour voir si vous ne l'avez pas fait une analyse d'erreur de virgule flottante avant, mais si vous utiliser le fait que i^2 > 2^53, vous pouvez voir que:

1/(2i^2) + O(1/i^4) 

terme est inférieur à 2^-54, ce qui signifie que (depuis la racine carrée est arrondie correctement, et donc son erreur d'arrondi doit être inférieur à 2^54), le résultat arrondi de la fonction sqrt est exactement i.

Il s'avère que (avec une analyse similaire), pour tout nombre à virgule flottante exactement représentable x, sqrt (x * x) est exactement x (en supposant que le calcul intermédiaire de x*x ne dépasse pas ou ne dépasse pas), La seule façon de contourner ce type de calcul est donc la représentation de x lui-même, c'est pourquoi vous le voyez à partir de 2^53 + 1 (le plus petit nombre non représentable).