6

x86アセンブリで64ビット整数の平方根を取得する方法を誰かが探していた別の質問(ここ)を見ていました。

これは非常に単純であることがわかります。解決策は、浮動小数点数に変換し、平方根を計算してから元に戻すことです。

Cで非常に似たようなことをする必要がありますが、同等のものを調べると少し行き詰まります。double を取る sqrt 関数しか見つかりません。double には、重大な丸め誤差を導入せずに大きな 64 ビット整数を格納する精度がありません。

long doublesqrt関数を持つ、使用できる一般的な数学ライブラリはありますか?

4

6 に答える 6

5

sqrtl()を取る関数long doubleは C99 の一部です。

long doubleコンパイル プラットフォームは、80 ビット拡張精度として実装する必要がないことに注意してください。と同じ幅であることが必要なだけdoubleで、Visual Studio ではプレーンな として実装されますdouble。GCC と Clang はlong double、Intel プロセッサで 80 ビットの拡張精度にコンパイルされます。

于 2013-08-28T22:46:33.297 に答える
2

ここでは、解決策に到達するためにいくつかの観測を収集します。

  1. 標準 C >= 1999 では、基数 2 の数値に期待されるように、非負の整数がビット単位で表現されることが保証されています。
    -> したがって、このタイプの数値のビット操作を信頼できます。
  2. が符号なし整数型の場合x、tnenx >> 1 == x / 2およびx << 1 == x * 2.
    (!) ただし: ビット操作は、対応する算術演算よりも高速に実行される可能性が非常に高くなります。
  3. sqrt(x)は と数学的に同等exp(log(x)/2.0)です。
  4. 切り捨てられた対数と整数の基数2 の指数を考慮すると、次IntExp2( IntLog2(x) / 2) "==" IntSqrtDn(x)の公正な推定値を得ることができます。 "="
  5. と書くIntExp2( IntLog2(x) / 2 + 1) "==" IntSqrtUp(x)と、整数平方根の「上の」近似が得られます。
  6. (4.) と (5.) で得られた近似は少し大雑把です (2 の連続した 2 乗の間に sqrt(x) の真の値を囲んでいます) が、これらは、の角屋根用x
  7. 平方根のニュートン アルゴリズムは、実際の解に対する適切な最初の近似があれば、整数に対してうまく機能する可能性があります。

http://en.wikipedia.org/wiki/Integer_square_root

最終的なアルゴリズムは、常に適切に動作することを十分に確認するために、いくつかの数学的計算を必要としますが、今は実行しません... 代わりに、最終的なプログラムを示します。

    #include <stdio.h>   /* For printf()...  */
    #include <stdint.h>  /* For uintmax_t... */
    #include <math.h>    /* For sqrt() ....  */

    int IntLog2(uintmax_t n) {
        if (n == 0) return -1; /* Error */
        int L;
        for (L = 0; n >>= 1; L++)
           ;
        return L; /* It takes < 64 steps for long long */
    }

    uintmax_t IntExp2(int n) {
        if (n < 0)
           return 0; /* Error */            
        uintmax_t E;
        for (E = 1; n-- > 0; E <<= 1)
            ;
        return E; /* It takes < 64 steps for long long */
    }

    uintmax_t IntSqrtDn(uintmax_t n) { return IntExp2(IntLog2(n) / 2); }

    uintmax_t IntSqrtUp(uintmax_t n) { return IntExp2(IntLog2(n) / 2 + 1); }

    int main(void) {
        uintmax_t N = 947612934;  /* Try here your number! */

        uintmax_t sqrtn  = IntSqrtDn(N),  /* 1st approx. to sqrt(N) by below */
                  sqrtn0 = IntSqrtUp(N);  /* 1st approx. to sqrt(N) by above */

        /* The following means while( abs(sqrt-sqrt0) > 1) { stuff... } */
        /* However, we take care of subtractions on unsigned arithmetic, just in case... */
        while ( (sqrtn > sqrtn0 + 1) ||  (sqrtn0 > sqrtn+1) )
           sqrtn0 = sqrtn, sqrtn = (sqrtn0  + N/sqrtn0) / 2; /* Newton iteration */

        printf("N==%llu, sqrt(N)==%g, IntSqrtDn(N)==%llu, IntSqrtUp(N)==%llu, sqrtn==%llu, sqrtn*sqrtn==%llu\n\n",  
                N,            sqrt(N),       IntSqrtDn(N),       IntSqrtUp(N),      sqrtn,       sqrtn*sqrtn);

        return 0;
    }

に格納された最後の値sqrtnは、 の整数平方根ですN
プログラムの最後の行には、すべての値が表示されます。
したがって、さまざまな値を試して、N何が起こるかを確認できます。

while ループ内にカウンターを追加すると、数回の繰り返ししか発生しないことがわかります。

備考:abs(sqrtn-sqrtn0)<=1整数値設定で作業する場合は、必ず条件が成立することを確認する必要があります。そうでない場合は、アルゴリズムを修正する必要があります。

注意 2:初期化文では、次のことに注意してsqrtn0 == sqrtn * 2 == sqrtn << 1ください。これにより、いくつかの計算が回避されます。

于 2013-08-30T00:17:12.660 に答える