Tại sao hàm hypot() quá chậm?

Question

Tôi đã thực hiện một số thử nghiệm với C++hypot() và JavaMath.hypot. Cả hai dường như chậm hơn đáng kể so với sqrt(a*a + b*b). Đó có phải là do độ chính xác cao hơn không? Phương pháp nào để tính toán sử dụng chức năng lạm dụng hypot? Đáng ngạc nhiên là tôi không thể tìm thấy bất kỳ dấu hiệu nào về hiệu suất kém trong tài liệu.

Answer 1

Đây không phải là chức năng sqrt đơn giản. Bạn nên kiểm tra liên kết này để thực hiện các thuật toán: http://www.koders.com/c/fid7D3C8841ADC384A5F8DE0D081C88331E3909BF3A.aspx

Nó có khi vòng lặp để kiểm tra tụ

/* 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); 

EDIT (Update từ JM):

Here là bản gốc Moler còn-Morrison giấy, và here là một sự theo dõi tốt đẹp do Dubrulle.

Answer 2

Đây là một thực hiện nhanh hơn, mà kết quả là cũng gần gũi hơn với java.lang.Math.hypot: (NB: để thực hiện Delorie của, cần thêm xử lý NaN và + vô cực đầu vào)

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

Answer 3

http://steve.hollasch.net/cgindex/math/pythag-root.txt

cho thấy triển khai nhanh hơn bằng sqrt() là bậc hai so với khối cho Moler & Morrison, với cùng một đặc điểm tràn.

Answer 4

Tôi đã tìm thấy Math.hypot() rất chậm. Tôi tìm thấy tôi có thể mã một phiên bản java nhanh chóng bằng cách sử dụng cùng một thuật toán tạo ra kết quả giống hệt nhau. Điều này có thể được sử dụng để thay thế nó.

/** 
* <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); 
    } 
}