c++ - C++ で double sqrt(double x) を実装する

Question

double sqrt(double x)std ライブラリを使用せずに C++ で実装します。

これは、私がここで見た Facebook のインタビューの質問です。http://www.glassdoor.com/Interview/Implement-double-sqrt-double-x-in-C-QTN_87210.htm これについて他に良いアイデアはありますか?...

!!!Edited.!!! (標準ライブラリを使用せずに。)

Answer 1

ここを見てください。この CodeProject の記事では、平方根を計算するための 14 の異なる方法を比較しています。

Answer 2

これは、ウィキペディアで見つけることができる最も天才的なsqrt実装の1つです。これは最も正確ではありませんが、非常に高速です。

float fast_sqrt(float number) {
   long i;
   float x2, y;
   const float threehalfs = 1.5F;

   x2 = number * 0.5F;
   y  = number;
   i  = * ( long * ) &y;                     // floating point bit level hacking [sic]
   i  = 0x5f3759df - ( i >> 1 );             // Newton's approximation
   y  = * ( float * ) &i;
   y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
   y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration
   y  = y * ( threehalfs - ( x2 * y * y ) ); // 3rd iteration

   return 1/y;
}

Answer 3

2つの明白な答えは、二分法（半低速）とニュートン-ラフソン/ライプニッツ反復（通常は高速）です。誰かの楽しみを台無しにしないために、質問に対してreinterpret_castを実行します。これは、ニュートンラプソン法を使用した8086アセンブリ言語での整数平方根の実装です。

isqrt proc uses di, number:word
;
; uses bx, cx, dx
;
    mov di,number
    mov ax,255
start_loop:
    mov bx,ax
    xor dx,dx
    mov ax,di
    div bx
    add ax,bx
    shr ax,1
    mov cx,ax
    sub cx,bx
    cmp cx,2
    ja  start_loop
    ret
isqrt endp

これは、いくらかの改善の余地があります-sqrt（x）での最初の推測としてx/2を使用します。386以上の命令を使用すると、log ₂bsr xの大まかな近似値を取得するために設定された最上位ビットを見つけ、それを2で割って初期近似値を取得できます。

OTOH、これは本当に古代のプロセッサでのみ意味がありました。浮動小数点ハードウェアが組み込まれている486（またはそれ以上）以降のすべての場合、FSQRT命令がこれ（またはあなたが書くことができる他のほとんどすべて）を打ち負かすことはほぼ確実です。