0

浮動小数点数のモジュラスを取るための高速な方法はありますか?

整数では、メルセンヌ素数のトリックがあるため、除算を必要とせずに y = x MOD 2^31-1 を計算できます。 整数トリック

浮動小数点数に同様のトリックを適用できますか?

できれば、ベクトル/SIMD 演算に変換できる方法、または GPGPU コードに移動できる方法で。これにより、浮動小数点データでの整数計算の使用が除外されます。

私が興味を持っている素数は 2^7-1 と 2^31-1 ですが、浮動小数点数に対してより効率的な素数があれば、それらは大歓迎です。

このアルゴリズムの使用目的の 1 つは、入力浮動小数点数がアルゴリズムに読み込まれるときに、実行中の「チェックサム」を計算することです。計算機能を使いすぎないようにするために、これを軽量に保ちたいと思います。

どうやら、同様の手法がより大きな数、特に 2^127 - 1 に使用されているようです。残念ながら、この論文の数学は私には理解できず、それをより小さな素数に変換する方法を理解できませんでした。
浮動小数点の例 MOD 2^127 - 1 - HASH127

4

1 に答える 1

1

私は djb の論文を見ましたが、31 ビットは 53 ビット精度の倍精度仮数部に問題なく収まるので、簡単です。チェックサムが Z/(2**31 - 1) に対するいくつかのリング演算で構成されていると仮定すると、x mod Z/(2**31 - 1); 最後に、整数演算を使用して正規のものを見つけることができます。これは遅いですが、あまり頻繁に発生するべきではありません。

基本的な削減手順は、整数 x = y + 2**31 * z を y + z に置き換えることです。djb が使用するトリックは、w = (x + L) - L を計算することです。ここで、L は、z = 2**-31 * w のような方法で丸めを誘発するために慎重に選択された大きな整数です。次に、y = x - w を計算し、最大 2**32 の大きさを持つ y + z を出力します。(この操作が十分でない場合はお詫びします。そうである場合は、チェックサム アルゴリズムを投稿してください。)

L の選択には、仮数の精度を知ることが含まれます。モジュラス 2**31 - 1 の場合、最小精度の単位 (ulp) を 2**31 にする必要があります。範囲 [1.0, 2.0) の double の場合、ulp は 2**-52 であるため、L は 2**52 * 2**31 になります。モジュラス 2**7 - 1 でこれを行う場合、L = 2**52 * 2**7 となります。djb が指摘しているように、このトリックは、中間結果がより高い精度で計算されないことに大きく依存しています。

于 2010-03-24T23:35:19.703 に答える