c = 2^N + -1のためにmod cを素早く計算する

Question

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

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

しかし、私は特別なトリックCが（2^N）-1または（2^N）+1の形式で、64ビット演算やBigIntライブラリを使用せず、かなり効率的なa * b mod Cを効率的に計算するためには、任意のモジュラス評価を行い、中間乗算を含める場合は32ビット整数をオーバーフローさせるケースも適切に計算します。

このような特殊なケースには高速な評価方法があると聞いていましたが、実際にはこのメソッドの説明は見つかりませんでした。 「クヌスにはないの？」 "それはウィキペディアのどこかではないのですか？"私は聞いたことがあります。

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

だから私は専門家に尋ねます。この巧妙な特別なケースは私が何の議論も見つけることができないmodメソッドと掛け合っていますか？

Answer 1

私は、トリックは、以下の

あなたがa*b mod 10000-1を乗算しているとし、かつ

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

（私はそれが簡単だが、原理は保持する必要がありますので、ベース10でそれをするつもりです）だと思います今 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 

x * 10000 ≡ x (mod 10000-1)以来[1]、T

彼の最初と最後の言葉は648 + 1088になります。 2番目と3番目の用語は、「トリック」が入る場所です。注：

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

これは本質的に循環シフトです。 648 + 3618 + 8403 + 1088の結果を与え、また、すべてのケースでは、逓倍数であることに注意してください< 10000（以降< 100とB < 100）、これは計算可能であるならば一緒にあなただけでし複数の2桁の数字、それらを追加します。

バイナリでも同様に動作します。

aとbで始まり、両方とも32ビットです。 mod 2^31 - 1を乗算したいとしますが、あなたは16ビットの乗数（32ビットを与える）しか持っていません。アルゴリズムは次のようなものになります。

これはおそらく動作しません。私は原則として正しいと思う。誰かがこれを正しくするためにこれを編集することを自由に感じます。

巻かれていないが、これは、私が推測しているどのようなPRNGを使用しているだけでなく、非常に高速です。

[1]: x*10000 ≡ x*(9999+1) ≡ 9999*x + x ≡ x (mod 9999)

Answer 2

クイック検索がhttp://home.pipeline.com/~hbaker1/AB-mod-N.pdfとなっています。残念ながら、簡略化された数式を書くだけの十分な感覚を覚えるのは時期尚早ですが、恐らくその論文のどこかにあるでしょう。

Answer 3

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

a*b mod 2^N-1 = p+q mod 2^N-12^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で除算がありません。

Answer 4

各ステップでモジュラ減算を行うのではなく、Montgomery reduction（他にもdescriptionsがあります）を使用して、乗算の計算コストを削減できます。これは、Nのプラス/マイナス2の累乗の性質をまだ使用していません。

Answer 5

あなたが探しているのアイデンティティはN = 2^q + c、cは任意の整数（ただし、通常は±1）であることを考えると、x mod N = (x mod 2^q)- c*floor(x/2^q)です。 で「特別な形式のモジュライ」「素数：計算の視点」リチャード・クランドールとカール・ポメランスによって

あなたはセクション9.2.3を読むことをお勧めします。理論に加えて、それは上記の関係を実現するアルゴリズムの擬似コードを含む。

Answer 6

この非常にトピックでは、rather extensive pageが見つかりました。アルゴリズムだけでなく、具体的なの履歴の問題と解決方法、そして人々が解決策を使用した方法についても議論しました。