ruby - raiz - math.sqrt python

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

Question

Me pregunto si esto es cierto: cuando tomo la raíz cuadrada de un entero al cuadrado, como en

f = Math.sqrt(123*123)

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

Como el floor(122.999999999999999999) es 122, debería obtener 122 en lugar de 123. Por lo tanto, espero que el 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

La secuencia de comandos anterior nunca imprime nada. ¿Por qué es así?

ACTUALIZACIÓN: Gracias por la respuesta rápida, esta parece ser la solución: según wikipedia

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

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

Answer 1

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

Debido a la precisión de representación en coma flotante, esto podría ser algo así 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 punto 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 también lo es 123*123 (también lo son todos los enteros de tamaño modesto). Por lo tanto, no se produce un error de redondeo cuando convierte 123*123 en un tipo de coma flotante. El resultado es exactamente 15129 .

La raíz cuadrada es una operación redondeada correctamente , 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. Dado que está tomando la raíz cuadrada de exactamente 15129 , que es exactamente 123 , ese es exactamente el resultado que obtiene de la función de 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 enteros de hasta 2 ^ 53. Por lo tanto, siempre que 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 todo lo que sea más pequeño que 94906265 , sabemos que el cálculo será exacto.

¡Pero lo intentaste i más grande que eso! ¿Qué esta pasando?

Para el mayor i que probé, i*i apenas supera 2 ^ 53 ( 1.1102... * 2^53 , en realidad). Como 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, como i*i tiene 54 bits de ancho, el redondeo ocurrirá en el bit más bajo. Por lo tanto, sabemos que:

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

donde el rounding es -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 . Usando una expansión de la serie Taylor, el valor infinitamente preciso (no redondeado) de esta raíz cuadrada es:

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

Ahora esto es un poco complicado para ver si no has hecho ningún análisis de error de punto flotante antes, pero si usas el hecho de que i^2 > 2^53 , puedes ver que:

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

el término es menor que 2 ^ -54, lo que significa que (dado que la raíz cuadrada está redondeada correctamente, y por lo tanto su error de redondeo debe ser menor que 2 ^ 54), el resultado redondeado de la función sqrt es exactamente i .

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

Answer 2

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

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

Answer 3

Para enteros "pequeños", generalmente hay una representación exacta de coma flotante.

Answer 4

Ruby''s Float es un número de punto flotante de precisión doble, lo que significa que puede representar números con precisión (regla general) 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.

Puedes encontrar más información aquí:

Lo que todos los científicos deberían saber sobre la aritmética de coma flotante: http://docs.sun.com/source/819-3693/ncg_goldberg.html