9

32 ビット整数演算では、加算と乗算の基本的な演算は暗黙的に mod 2^32 で計算されます。つまり、結果は加算または乗算の最下位ビットになります。

異なるモジュラスで結果を計算したい場合は、異なる言語で任意の数の BigInt クラスを使用できます。値 a,b,c < 2^32 の場合、中間値を 64 ビット long int で計算し、組み込みの % 演算子を使用して正しい答えに減らすことができます。

しかし、C が (2^N)-1 または (2^N)+1 の形式の場合に a*b mod C を効率的に計算するための特別なトリックがあり、64 ビット演算またはBigInt ライブラリであり、任意のモジュラス評価よりも非常に効率的であり、中間乗算を含めた場合に通常 32 ビット int をオーバーフローするケースも適切に計算します。

残念ながら、そのような特殊なケースには迅速な評価方法があると聞いていますが、実際には方法の説明を見つけていません。「それはクヌースにありませんか？」「それはウィキペディアのどこかにありませんか？」私が聞いたつぶやきです。

2147483647 は 2^31 -1 に等しい素数であるため、これは a*b mod 2147483647 の乗算を行う乱数発生器では明らかに一般的な手法です。

そこで専門家に聞いてみます。私が議論を見つけることができないこの巧妙な特殊なケースの乗算と mod の方法は何ですか?

4

6 に答える 6

12

秘訣は次のとおりだと思います（10進数で行うのが簡単なので、原則は成り立つはずです）

乗算していると仮定a*b mod 10000-1し、

a = 1234 = 12 * 100 + 34
b = 5432 = 54 * 100 + 32

今a*b = 12 * 54 * 10000 + 34 * 54 * 100 + 12 * 32 * 100 + 34 * 32

12 * 54 * 10000 =  648 * 10000
34 * 54 * 100   = 1836 * 100
12 * 32 * 100   =  384 * 100
34 * 32         = 1088

[1]以降x * 10000 ≡ x (mod 10000-1)、最初と最後の項は648+1088になります。2番目と3番目の用語は、「トリック」の出番です。次の点に注意してください。

1836 = 18 * 100 + 36
1836 * 100 ≡ 18 * 10000 + 3600 ≡ 3618 (mod 10000-1).

これは本質的に循環シフトです。648 + 3618 + 8403 + 1088の結果を示します。また、すべての場合で、乗算された数値は<10000（a<100およびb<100であるため）であるため、2桁の数値を複数にまとめることができれば計算可能です。 、およびそれらを追加します。

バイナリでは、同様に機能します。

aとbから始めます。どちらも32ビットです。それらをmod2^ 31-1で乗算したいが、16ビットの乗算器（32ビットを与える）しかないとします。アルゴリズムは次のようになります。

 a = 0x12345678
 b = 0xfedbca98
 accumulator = 0
 for (x = 0; x < 32; x += 16)
     for (y = 0; y < 32; y += 16)
         // do the multiplication, 16-bit * 16-bit = 32-bit
         temp = ((a >> x) & 0xFFFF) * ((b >> y) & 0xFFFF)

         // add the bits to the accumulator, shifting over the right amount
         total_bits_shifted = x + y
         for (bits = 0; bits < total_bits_shifted + 32; bits += 31)
             accumulator += (temp >> (bits - total_bits_shifted)) & 0x7FFFFFFF

         // do modulus if it overflows
         if (accumulator > 0x7FFFFFFFF)
             accumulator = (accumulator >> 31) + (accumulator & 0x7FFFFFFF);

遅いので、そのアキュムレータ部分はおそらく機能しません。でも原則的には正しいと思います。誰かがこれを自由に編集して正しくすることができます。

展開すると、これもかなり高速です。これは、PRNGが使用しているものだと思います。

[1]：x *10000≡x*（9999 + 1）≡9999* x +x≡x（mod 9999）
于 2009-04-18T09:54:49.057 に答える
3

a*b を として計算できるとしますp*2^N+q。これには 64 ビットの計算が必要になる場合があります。または、a と b を 16 ビットの部分に分割して 32 ビットで計算することもできます。

それa*b mod 2^N-1 = p+q mod 2^N-1以来2^N mod 2^N-1 = 1。

そしてa*b mod 2^N+1 = -p+q mod 2^N+1以来2^N mod 2^N+1 = -1。

どちらの場合も、2^N-1またはによる除算はありません2^N+1。

于 2009-04-18T08:51:50.597 に答える
2

簡単な検索でこれが見つかりました: http://home.pipeline.com/~hbaker1/AB-mod-N.pdf。残念ながら、簡略化された式を書くだけで十分な意味を理解するには遅すぎますが、おそらくその論文のどこかにあるでしょう.

于 2009-04-18T08:40:12.947 に答える
1

各ステップでモジュラー リダクションを行うのではなく、モンゴメリ リダクション(他にも説明があります) を使用して、剰余乗算計算のコストを削減できます。ただし、これは N が 2 のプラス/マイナスの累乗であるというプロパティをまだ使用していません。

于 2009-04-18T08:54:32.790 に答える
1

および c が任意の整数 (通常は ±1) でx mod N = (x mod 2^q)- c*floor(x/2^q)あることを考えると、探している ID は です。N = 2^q + c

Richard Crandall と Carl Pomerance による"Prime Numbers: A Computational Perspective"のセクション 9.2.3: "Moduli of special form"を読むとよいでしょう。理論に加えて、上記の関係を実装するアルゴリズムの疑似コードが含まれています。

于 2009-04-18T11:25:06.017 に答える
0

アルゴリズムだけでなく、問題と解決策の特定の履歴、および人々が解決策をどのように使用したかについても説明している、このトピックに関するかなり広範なページを見つけました。

于 2009-04-23T06:22:48.073 に答える