hice algunas pruebas con C++
hypot()
y Java
Math.hypot
. Ambos parecen ser significativamente más lentos que sqrt(a*a + b*b)
. ¿Es eso por una mejor precisión? ¿Qué método utiliza para calcular la función hipotenusa hypot
? Sorprendentemente, no pude encontrar ninguna indicación de bajo rendimiento en la documentación.¿Por qué la función hypot() es tan lenta?
Respuesta
No es una función simple de sqrt. Usted debe verificar este enlace para la implementación del algoritmo: http://www.koders.com/c/fid7D3C8841ADC384A5F8DE0D081C88331E3909BF3A.aspx
Tiene bucle while para comprobar si hay convergencia
/* Slower but safer algorithm due to Moler and Morrison. Never
produces any intermediate result greater than roughly the
larger of X and Y. Should converge to machine-precision
accuracy in 3 iterations. */
double r = ratio*ratio, t, s, p = abig, q = asmall;
do {
t = 4. + r;
if (t == 4.)
break;
s = r/t;
p += 2. * s * p;
q *= s;
r = (q/p) * (q/p);
} while (1);
EDITAR (Actualización de JM):
Here es el original Moler-Morrison papel, y here es un buen seguimiento debido a Dubrulle.
Sería bueno dar ejemplos donde esta función es mejor que el enfoque 'sqrt'. – schnaader
@schnaader - lea la página vinculada, el motivo está en la parte superior (versión corta, el método ingenuo puede desbordarse cuando no debería) – Nir
Esto es importante para valores muy grandes de xey. Por ejemplo, si xey son tales que x^2 + y^2 es mayor que MAX_DOUBLE, la versión sqrt (x^2 + y^2) fallará. Sin embargo, dado que este método nunca produce un valor que sea mucho mayor que xoy, debería ser seguro en esas situaciones. – pfhayes
Aquí es una implementación más rápida, lo que los resultados son también más cerca java.lang.Math.hypot: (NB: para la implementación de Delorie, necesita añadir el manejo de NaN y + -INFINITY entradas)
private static final double TWO_POW_450 = Double.longBitsToDouble(0x5C10000000000000L);
private static final double TWO_POW_N450 = Double.longBitsToDouble(0x23D0000000000000L);
private static final double TWO_POW_750 = Double.longBitsToDouble(0x6ED0000000000000L);
private static final double TWO_POW_N750 = Double.longBitsToDouble(0x1110000000000000L);
public static double hypot(double x, double y) {
x = Math.abs(x);
y = Math.abs(y);
if (y < x) {
double a = x;
x = y;
y = a;
} else if (!(y >= x)) { // Testing if we have some NaN.
if ((x == Double.POSITIVE_INFINITY) || (y == Double.POSITIVE_INFINITY)) {
return Double.POSITIVE_INFINITY;
} else {
return Double.NaN;
}
}
if (y-x == y) { // x too small to substract from y
return y;
} else {
double factor;
if (x > TWO_POW_450) { // 2^450 < x < y
x *= TWO_POW_N750;
y *= TWO_POW_N750;
factor = TWO_POW_750;
} else if (y < TWO_POW_N450) { // x < y < 2^-450
x *= TWO_POW_750;
y *= TWO_POW_750;
factor = TWO_POW_N750;
} else {
factor = 1.0;
}
return factor * Math.sqrt(x*x+y*y);
}
}
http://steve.hollasch.net/cgindex/math/pythag-root.txt
sugiere que la aplicación usando sqrt más rápido() es cuadrática vs cúbico para Moler & Morrison, con aproximadamente las mismas características de desbordamiento.
Encontré que Math.hypot() era abismalmente lento. Descubrí que podía codificar una versión rápida de Java utilizando el mismo algoritmo que produce resultados idénticos. Esto puede usarse para reemplazarlo.
/**
* <b>hypot</b>
* @param x
* @param y
* @return sqrt(x*x +y*y) without intermediate overflow or underflow.
* @Note {@link Math#hypot} is unnecessarily slow. This returns the identical result to
* Math.hypot with reasonable run times (~40 nsec vs. 800 nsec).
* <p>The logic for computing z is copied from "Freely Distributable Math Library"
* fdlibm's e_hypot.c. This minimizes rounding error to provide 1 ulb accuracy.
*/
public static double hypot(double x, double y) {
if (Double.isInfinite(x) || Double.isInfinite(y)) return Double.POSITIVE_INFINITY;
if (Double.isNaN(x) || Double.isNaN(y)) return Double.NaN;
x = Math.abs(x);
y = Math.abs(y);
if (x < y) {
double d = x;
x = y;
y = d;
}
int xi = Math.getExponent(x);
int yi = Math.getExponent(y);
if (xi > yi + 27) return x;
int bias = 0;
if (xi > 510 || xi < -511) {
bias = xi;
x = Math.scalb(x, -bias);
y = Math.scalb(y, -bias);
}
// translated from "Freely Distributable Math Library" e_hypot.c to minimize rounding errors
double z = 0;
if (x > 2*y) {
double x1 = Double.longBitsToDouble(Double.doubleToLongBits(x) & 0xffffffff00000000L);
double x2 = x - x1;
z = Math.sqrt(x1*x1 + (y*y + x2*(x+x1)));
} else {
double t = 2 * x;
double t1 = Double.longBitsToDouble(Double.doubleToLongBits(t) & 0xffffffff00000000L);
double t2 = t - t1;
double y1 = Double.longBitsToDouble(Double.doubleToLongBits(y) & 0xffffffff00000000L);
double y2 = y - y1;
double x_y = x - y;
z = Math.sqrt(t1*y1 + (x_y*x_y + (t1*y2 + t2*y))); // Note: 2*x*y <= x*x + y*y
}
if (bias == 0) {
return z;
} else {
return Math.scalb(z, bias);
}
}
- 1. ¿Por qué la salida de la consola es tan lenta?
- 2. ¿Por qué la modificación concurrente de matrices es tan lenta?
- 3. ¿Por qué la importación de SQL es tan lenta?
- 4. ¿Por qué la conexión al servidor MySQL es tan lenta?
- 5. ¿Por qué esta simple consulta de MySQL es tan lenta?
- 6. ¿Por qué mi llamada mongodb es tan lenta?
- 7. ¿Por qué esta expresión de Haskell es tan lenta?
- 8. ¿Por qué la desasignación es lenta?
- 9. ¿Por qué PhotoImage es lenta?
- 10. ¿Por qué la reflexión es lenta?
- 11. ¿Por qué es tan lenta la fecha en un vector de caracteres?
- 12. ¿Por qué llamar a una función tan lenta (como strlen, count, etc.) en un valor referenciado?
- 13. CodedUI: ¿Por qué la búsqueda de una celda es tan lenta?
- 14. ¿Por qué la inserción de entidades en EF 4.1 es tan lenta en comparación con ObjectContext?
- 15. ¿Por qué la detección de movimiento de WxPythons es tan lenta?
- 16. ¿Por qué la impresión en stdout es tan lenta? ¿Se puede acelerar?
- 17. ¿Por qué la multiplicación de matrices en .NET es tan lenta?
- 18. ¿Por qué la consola de administración de Glassfish es tan lenta?
- 19. ¿Por qué la depuración en eclipse/pydev es tan lenta para mi programa python?
- 20. ¿Por qué Dictionary.First() es tan lento?
- 21. ¿Por qué mi aplicación de codificación de imágenes basada en QTKit es tan lenta?
- 22. ¿Por qué una conexión TCP no bloqueante() ocasionalmente es tan lenta en Linux?
- 23. ¿La indexación de Data.Vector.Unboxed.Mutable.MVector es realmente tan lenta?
- 24. ¿Por qué es lenta la primera llamada de cliente WCF?
- 25. ¿Qué tan lenta es la aritmética de NaN en la FPU Intel x64?
- 26. ¿Por qué la sintaxis de C++ es tan complicada?
- 27. ¿Por qué es tan simple este algoritmo haskell tan lento?
- 28. ¿Por qué TestComplete es tan lento?
- 29. ¿Por qué es EXC_BAD_ACCESS tan inútil?
- 30. ¿Por qué numpy.array es tan lento?
¿Qué es 'significativamente más lento'? ¿Puedes cuantificar este valor? ¿Usaste un perfilador? ¿Cuántas veces hiciste las pruebas? ¿Puedes describir tu experimento (DOE)? – linuxuser27
En Java fue más lento por un factor de ~ 7, en C++ ~ 10. Lo encontramos de forma independiente con mi colega al probar uno de los problemas de programación para el próximo concurso de programación en una universidad. – Leonid
@ linuxuser27: y las dos personas que votaron en contra de su comentario, verifican Ravi Gummadi +9 respuesta votada para la iluminación. – SyntaxT3rr0r