¿Por qué Math.sqrt (i * i) .floor == i?

Question

Me pregunto si esto es cierto: Cuando tomo la raíz cuadrada de un número entero cuadrado, como en

f = Math.sqrt(123*123) 

voy a tener un número de coma flotante muy cerca de 123. Debido a la precisión de representación en coma flotante, esto podría ser algo así como 122.99999999999999999999 o 123.000000000000000000001.

Dado que floor(122.999999999999999999) es 122, debería obtener 122 en lugar de 123. Por lo tanto, espero que floor(sqrt(i*i)) == i-1 en aproximadamente el 50% de los casos. Extrañamente, para todos los números que he probado, floor(sqrt(i*i) == i. Aquí hay un pequeño script de ruby ​​para probar los primeros 100 millones de números:

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

El script anterior nunca imprime nada. ¿Por qué es así?

UPDATE: Gracias por la rápida respuesta, esto parece ser la solución: De acuerdo con wikipedia

Cualquier número entero con valor absoluto menor que o igual a 2^24 puede ser exactamente representado en el formato de precisión simple , y cualquier número entero con valor absoluto menor que o igual a 2^53 puede representarse exactamente en el formato de precisión doble.

Math.sqrt (i * i) comienza a comportarse como he esperaba que a partir de i = 9007199254740993, que es 2^53 + 1.

Answer 1

Para enteros "pequeñas", por lo general hay una representación exacta de coma flotante.

Answer 2

No es demasiado difícil encontrar casos en que esto se rompe como era de esperar: Flotador

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

Answer 3

de Ruby es un doble precisión el número de punto flotante, lo que significa que puede representar con precisión números con (regla del pulgar) alrededor de 16 dígitos decimales significativos. Para los números regulares de punto flotante de precisión simple, se trata de 7 dígitos significativos.

Puede encontrar más información aquí:

Lo que todo informático debe saber sobre Floating Point-Aritmética: http://docs.sun.com/source/819-3693/ncg_goldberg.html

Answer 4

Aquí está la esencia de su confusión:

Debido a punto flotante representación precisión, esto podría ser algo como 122.99999999999999999999 o 123.000000000000000000001.

Esto es falso. Siempre será exactamente 123 en un sistema compatible con IEEE-754, que es casi todos los sistemas en estos tiempos modernos. La aritmética de coma flotante no tiene "error aleatorio" o "ruido". Tiene un redondeo preciso y determinista, y muchos cómputos simples (como este) no incurren en ningún redondeo.

123 es exactamente representable en coma flotante, y así es 123*123 (también lo son todas las enteros modesta de tamaño). Por lo tanto, no se produce un error de redondeo cuando convierte 123*123 en un tipo de coma flotante. El resultado es exactamente15129.

La raíz cuadrada es correctamente redondeada operación, según el estándar IEEE-754. Esto significa que si hay una respuesta exacta, se requiere la función de raíz cuadrada para producirla. Puesto que usted está tomando la raíz cuadrada de exactamente15129, que es exactamente 123, eso es exactamente el resultado que se obtiene de la función raíz cuadrada. No se produce redondeo o aproximación.

Ahora, ¿para qué tan grande de un entero será esto cierto?

La precisión doble puede representar exactamente todos los números enteros de hasta 2^53. Por lo tanto, mientras i*i sea menor que 2^53, no se producirá ningún redondeo en su cálculo, y el resultado será exacto por esa razón. Esto significa que para todos i menor que 94906265, sabemos que el cálculo será exacto.

¡Pero usted intentó i más grande que eso! ¿Qué esta pasando?

Para el i más grande que haya probado, i*i es apenas más grande que 2^53 (1.1102... * 2^53, en realidad). Dado que las conversiones de entero a doble (o multiplicación en doble) también son operaciones redondeadas correctamente, i*i será el valor representable más cercano al cuadrado exacto de i. En este caso, dado que i*i tiene 54 bits de ancho, el redondeo ocurrirá en el bit más bajo. Así sabemos que:

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

donde es o bien -1,0, or 1. Si el redondeo es cero, entonces el cuadrado es exacto, por lo que la raíz cuadrada es exacta, por lo que ya sabemos que obtienes la respuesta correcta. Vamos a ignorar ese caso.

Así que ahora estamos viendo la raíz cuadrada de i*i +/- 1. El uso de un desarrollo en serie de Taylor, el valor infinitamente precisa (sin redondear) de esta raíz cuadrada es:

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

Ahora bien, esto es un poco más incómoda para ver si no se ha hecho ningún análisis de errores de punto flotante antes, pero si utilizar el hecho de que i^2 > 2^53, se puede ver que la: término

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

es menor que 2^-54, lo que significa que (desde la raíz cuadrada se completa correctamente, y de ahí su error de redondeo debe ser menor que 2^54), el redondeado resultado de la función sqrt es exactamente i.

Resulta que (con un análisis similar), para cualquier número x flotante exactamente representable, sqrt (x * x) es exactamente x (suponiendo que el cálculo intermedio de x*x no sobrepasa o subdesborda), por lo tanto, la única forma en que puede encontrar el redondeo para este tipo de cálculo es en la representación del x, por lo que puede verlo comenzando en 2^53 + 1 (el número entero más pequeño no representable).