2010-09-21 15 views
27

hice algunas pruebas con C++hypot() y JavaMath.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?

+5

¿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

+3

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

+1

@ linuxuser27: y las dos personas que votaron en contra de su comentario, verifican Ravi Gummadi +9 respuesta votada para la iluminación. – SyntaxT3rr0r

Respuesta

25

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.

+0

Sería bueno dar ejemplos donde esta función es mejor que el enfoque 'sqrt'. – schnaader

+2

@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

+2

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

3

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); 
    } 
} 
2

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); 
    } 
} 
Cuestiones relacionadas