7

私は現在、高速の32.32固定小数点数学ライブラリを作成しています。足し算、引き算、掛け算は正しく動作するようになりましたが、除算にかなりこだわっています。

思い出せない人へのちょっとした注意：32.32固定小数点数は、32ビットの整数部分と32ビットの小数部分を持つ数です。

私が思いついた最高のアルゴリズムには、96ビットの整数除算が必要です。これは、コンパイラーには通常組み込まれていないものです。

とにかく、ここに行きます：

G = 2^32

notation: x is the 64-bit fixed-point number, x1 is its low nibble and x2 is its high

G*(a/b) = ((a1 + a2*G) / (b1 + b2*G))*G      // Decompose this

G*(a/b) = (a1*G) / (b1*G + b2) + (a2*G*G) / (b1*G + b2)

ご覧のとおり、(a2*G*G)は通常の64ビット整数よりも大きいことが保証されています。uint128_tが実際にコンパイラでサポートされている場合は、次のようにします。

((uint128_t)x << 32) / y)

そうではなく、解決策が必要です。ご協力ありがとうございました。

4

4 に答える 4

7

より大きな除算を、より少ないビットで除算を行う複数のチャンクに分解できます。すでに述べた別のポスターとして、アルゴリズムはクヌースのTAOCPにあります。

ただし、本を購入する必要はありません。

Cのアルゴリズムを実装するハッカーズデライトのWebサイトにコードがあります。これは、32ビット演算のみを使用して64ビットの符号なし除算を行うように記述されているため、コードを直接カットアンドペーストすることはできません。64ビットから128ビットにするには、すべてのタイプ、マスク、およびコンスタンスを2つ広げる必要があります。たとえば、shortはintになり、a0xffffは0xffffffffllectになります。

この簡単で簡単な変更の後、128ビットの分割を実行できるようになります。

コードはGitHubにミラーリングされていますが、元々はHackersdelight.orgに投稿されていました（元のリンクにはアクセスできなくなりました）。

最大値は96ビットしか必要としないため、64ビット除算の1つは常にゼロを返すため、コードを少し単純化することもできます。

ああ-そして私がこれを忘れる前に：コードは符号なしの値でのみ機能します。符号付きから符号なしの除算に変換するには、次のようにします（擬似コードスタイル）。

fixpoint Divide (fixpoint a, fixpoint b)
{
    // check if the integers are of different sign:
    fixpoint sign_difference = a ^ b; 
    
    // do unsigned division:
    fixpoint x = unsigned_divide (abs(a), abs(b));
    
    // if the signs have been different: negate the result.
    if (sign_difference < 0)
    {
       x = -x;
    }
    
    return x;
}

ウェブサイト自体もチェックする価値があります：http：//www.hackersdelight.org/

ちなみに、あなたが取り組んでいる素晴らしいタスクです。固定小数点ライブラリが必要なものについて教えていただけませんか。

ちなみに、除算の通常のシフトおよび減算アルゴリズムも機能します。

x86をターゲットにする場合は、MMXまたはSSE組み込み関数を使用して実装できます。このアルゴリズムはプリミティブ操作のみに依存しているため、非常に高速に実行できます。

于 2009-06-08T09:43:53.127 に答える
1

より良い自己調整の答え：答え
のC＃主義を許しますが、以下はすべての場合に機能するはずです。より速く使用するための正しいシフトを見つける可能性のある解決策がある可能性がありますが、私は今よりもはるかに深く考える必要があります。ただし、これはかなり効率的です。

int upshift = 32;
ulong mask = 0xFFFFFFFF00000000;
ulong mod = x % y;
while ((mod & mask) != 0)
{
     // Current upshift of the remainder would overflow... so adjust
     y >>= 1;
     mask <<= 1;
     upshift--;

     mod = x % y;
}
ulong div = ((x / y) << upshift) + (mod << upshift) / y;

単純だが安全でない答え：
この計算では、x % y残りのビットが上位32ビットに設定されている場合、残りのアップシフトでオーバーフローが発生し、誤った答えが生じる可能性があります。

((x / y) << 32) + ((x % y) << 32) / y

最初の部分は整数除算を使用し、答えの上位ビットを提供します（それらを元に戻します）。

2番目の部分は、上位ビット除算の余り（これ以上除算できなかったビット）から下位ビットを計算し、上にシフトしてから除算します。

于 2009-06-08T08:01:19.947 に答える
0

おそらく最高のNilsの答えが好きです。数字が底10ではなく底2^32であることを除いて、私たちが小学校で学んだように、それは単なる長い除算です.

ただし、除算にニュートンの近似法を使用することも検討してください。

  x := x (N + N - N * D * x)

ここで、N は分子、D は分母です。

これは、すでに持っている乗算と加算を使用するだけで、約 1 ULP の精度に非常に迅速に収束します。一方で、すべてのケースで正確な 0.5-ULP の答えを達成できるわけではありません。

いずれにせよ、トリッキーなビットは、オーバーフローの検出と処理です。

于 2009-06-08T18:37:26.510 に答える
0

クイック-n-ダーティ。

倍精度浮動小数点で A/B 除算を行います。これにより、C~=A/B が得られます。浮動小数点の精度と仮数部が 53 ビットであるため、概算にすぎません。

C を固定小数点システムで表現可能な数値に丸めます。

次に、(固定小数点を使用して) D=AC*B を計算します。これは、A よりも大幅に小さいはずです。

を繰り返し、D/B を浮動小数点で計算します。繰り返しますが、答えを整数に丸めます。あなたが行くように、各部門の結果を一緒に追加します。丸め後に浮動小数点除算が 0 を返すほど余りが小さい場合は、停止できます。

あなたはまだ終わっていません。これで答えにかなり近づきましたが、分割は正確ではありませんでした。最後に、バイナリ検索を実行する必要があります。（非常に良い）最初の見積もりを使用して、それを増やすとエラーが改善されるかどうかを確認します。基本的には、適切な答えを括弧で囲み、新しいテストで範囲を半分に分割し続けます。

はい、ここでニュートン反復を実行できますが、既存の 32.32 精度ツールキットを使用して単純な乗算と加算のみが必要なため、二分探索の方が簡単です。

これは最も効率的な方法ではありませんが、コーディングが最も簡単です。

于 2009-06-08T19:00:47.307 に答える