0

実行時に次の計算を実行する C 関数を作成しようとしています。

分子/分母

どこ：

分子は前の計算結果であり、常に正であり、分母より大きい

と、

分母は (1 <= 分母 <= 64) です。

実行時の計算は高速である必要があります。つまり、最小サイクルである必要があるため、除算演算子は問題外です。再帰減算とビットごとの長い除算を調べましたが、別の解決策を見つけようとしています。

ヘルプはありますか？

4

2 に答える 2

1

これは、1 つの乗算と 1 つのシフトを使用する 1 つのアイデアです。したがって、ほとんどのシステムで除算よりも高速になります。分子が 768,000,000 ~= 30 ビットで最高になるので、32 ビット ワードには十分なスペースが残っていないため、64 ビットの乗算を使用する必要があります。

主なアイデアは、次の事実を利用することです。

x / y == (x * k) / (y * k)

2 の累乗で割ることは、単純で高速なビット シフトです。

したがって、特定の例を選ぶために、 and を仮定x = 700,000,000しy = 47ます (したがって、正しい商は 14,893,617 です)。丸め誤差を避けるために、シフトは可能な限り最大の分子のサイズである 30 ビットにほぼ等しい必要があります。kに最も近い近似値を与えるy * k = 2^30の値を見つけますk = 22845571。この場合です。それからx * k = 0x38D08C4CE6F500。これを 30 ビットシフトする0xE34231 = 14,893,617と、予想される商が得られます。商で 1 ずれることが許容されない限り、丸めの目的で分子/分母のいくつかの組み合わせに対して 1 ～ 2 ビットを追加する必要がある可能性があります。

次に、可能な分母ごとに適切な乗数を使用してルックアップ テーブルを作成します。

編集: 以下のコメントで指摘されているように、k = (2^30 + y - 1) / y単にk = round(2^30 / y).

于 2013-06-12T15:52:29.510 に答える
0

大きい @ss テーブルは、小さい数の場合に機能します。

unsigned int divTable[kMaxNumerator][64] = {...}

可能な各分割の値をそこに入れる場所。特定のサイズを超えるとあまり実用的ではありませんが、含まれているケースでは機能し、昔はテクスチャ マッピングの一般的な解決策でした:)それからあなたのコメントを読んで、あなたが 768,000,000 の範囲にいることがわかりました。かなりの精度の低下を処理できます。

于 2013-06-12T16:00:40.280 に答える