5

私はそれについて聞いたばかりで、簡単だx mod (2^32-1)とx / (2^32-1)思いますが、どうすればいいですか?

式を計算するには:

x n = (x n-1 + x n-1 / b)mod b.

にとっb = 2^32て、それは簡単x%(2^32) == x & (2^32-1)です。とx / (2^32) == x >> 32。(ここの ^ は XOR ではありません)。b = 2^32 - 1 の場合の方法。

ページ内 https://en.wikipedia.org/wiki/Multiply-with-carry。彼らは「arithmetic for modulus 2^32 − 1 requires only a simple adjustment from that for 2^32」と言います。では「簡易調整」とは？

4

4 に答える 4

7

（この回答はmodケースのみを処理します。）

xのデータ型は 32 ビットを超えており (この回答は実際には任意の正の整数で機能します)、正であると仮定します(負の場合は単に です-(-x mod 2^32-1))。に

x mod (2^32-1) = 0 if x == 2^32-1, x otherwise
x / (2^32 - 1) = 1 if x == 2^32-1, 0 otherwise

x基数 2^32 で、数字x0, x1, ..., で書くことができますxn。そう

  x = x0 + 2^32 * x1 + (2^32)^2 * x2 + ... + (2^32)^n * xn

これにより、モジュラスを実行するときに答えがより明確になり2^32 == 1 mod 2^32-1ます。あれは

  x == x0 + 1 * x1 + 1^2 * x2 + ... + 1^n * xn (mod 2^32-1)
    == x0 + x1 + ... + xn (mod 2^32-1)

x mod 2^32-1基数の 2^32 桁の合計と同じです! (mod 2^32-1 はまだ削除できません)。現在、合計が 0 から 2^32-1 の間であるか、それより大きいかの 2 つのケースがあります。前者では完了です。後者では、0 と 2^32-1 の間になるまで繰り返すことができます。ビット単位の演算を使用できるため、基数 2^32 で数字を取得するのは高速です。Python の場合 (これは負の数を処理しません):

def mod_2to32sub1(x):
    s = 0 # the sum

    while x > 0: # get the digits
        s += x & (2**32-1)
        x >>= 32

    if s > 2**32-1:
        return mod_2to32sub1(s)
    elif s == 2**32-1:
        return 0
    else:
        return s

(これを一般化するのは非常に簡単です。実際、この回答x mod 2^n-1では 32 の出現を置き換えるだけです。)n

(編集:elifの無限ループを回避するための句を追加しましたmod_2to32sub1(2**32-1)。編集 2: に置き換え^ました**... おっと。)

于 2012-03-25T01:27:57.510 に答える
2

したがって、「ルール」 2 32 = 1 で計算します。一般に、2 32+x = 2 xです。32 を法とする指数を取ることで2 aを単純化できます。例: 2 66 = 2 2。

任意の数値を 2 進数で表現してから、指数を下げることができます。例: 数値 2 40 + 2 38 + 2 20 + 2 + 1 は、2 8 + 2 6 + 2 20 + 2 + 1に簡略化できます。

一般に、2 の 32 乗ごとに指数をグループ化し、32 を法とするすべての指数を「ダウングレード」できます。

64 ビット ワードの場合、数値は次のように表すことができます。

2 32 A+B

ここで、0 <= A、B <= 2 32 -1。A と B を取得するのは、ビット単位の操作で簡単です。

したがって、これを単純化して A + B にすることができます。これははるかに小さく、最大で 2 33です。次に、この数が少なくとも 2 32 -1 であるかどうかを確認し、その場合は 2 32 - 1を引きます。

これにより、コストのかかる直接除算が回避されます。

于 2012-03-25T01:19:15.010 に答える
1

モジュラスはすでに説明されていますが、要約してみましょう。

kモジュロの余りを見つけるには、次の2^n-1ように記述します。

k = a + 2^n*b,  0 <= a < 2^n

それで

k = a + ((2^n-1) + 1) * b
  = (a + b) + (2^n-1)*b
  ≡ (a + b) (mod 2^n-1)

の場合a + b >= 2^n、余りが。未満になるまで繰り返し、それ2^nがにつながる場合はa + b = 2^n-1、それを0に置き換えます。「右にシフトnして最後のnビットに追加」するたびに、最初のセットのビットが右に移動するnか、n-1配置されます（k < 2^(2*n-1)最初のセットの場合を除く）シフトアンドアドの後のビットが2^nビットである可能性があります）。したがって、タイプの幅がに比べて大きい場合n、これには多くのシフトが必要になります。128ビットタイプを検討してください。n = 3大きいk場合は、40シフト以上が必要になります。必要なシフト数を減らすために、次の事実を利用できます。

2^(m*n) - 1 = (2^n - 1) * (2^((m-1)*n) + 2^((m-2)*n) + ... + 2^(2*n) + 2^n + 1),

そのうち、すべてに2^n - 1分割するものだけを使用します。次に、その倍数だけシフトします。これは、そのステップで値が持つことができる最大ビット長の約半分です。上記の128ビットタイプの例と7（）を法とする剰余の場合、3から128/2の最も近い倍数は63と66であり、最初に63ビットシフトします。2^(m*n) - 1m > 0n2^3 - 1

r_1 = (k & (2^63 - 1)) + (k >> 63) // r_1 < 2^63 + 2^(128-63) < 2^66

最大66ビットの数値を取得するには、66/2=33ビットシフトします。

r_2 = (r_1 & (2^33 - 1)) + (r_1 >> 33) // r_2 < 2^33 + 2^(66-33) = 2^34

最大34ビットに到達します。次に18ビットシフトし、次に9、6、3

r_3 = (r_2 & (2^18 - 1)) + (r_2 >> 18) // r_3 < 2^18 + 2^(34-18) < 2^19
r_4 = (r_3 & (2^9 - 1)) + (r_3 >> 9)   // r_4 < 2^9 + 2^(19-9) < 2^11
r_5 = (r_4 & (2^6 - 1)) + (r_4 >> 6)   // r_5 < 2^6 + 2^(11-6) < 2^7
r_6 = (r_5 & (2^3 - 1)) + (r_5 >> 3)   // r_6 < 2^3 + 2^(7-3) < 2^5
r_7 = (r_6 & (2^3 - 1)) + (r_6 >> 3)   // r_7 < 2^3 + 2^(5-3) < 2^4

十分であれば、1回の減算になりますr_7 >= 2^3 - 1。k % (2^n -1)bビットタイプで計算するには、O（log 2（b / n））シフトが必要です。

商も同様に得られます。

k = a + 2^n*b,  0 <= a < 2^n
  = a + ((2^n-1) + 1)*b
  = (2^n-1)*b + (a+b),

そうk/(2^n-1) = b + (a+b)/(2^n-1)、そして私たちはしながら続けa+b > 2^n-1ます。ここでは残念ながら、幅の約半分をシフトしてマスキングしても作業を減らすことができないため、この方法はn、タイプの幅よりもそれほど小さくない場合にのみ効率的です。

n小さすぎない高速ケースのコード：

unsigned long long modulus_2n1(unsigned n, unsigned long long k) {
    unsigned long long mask = (1ULL << n) - 1ULL;
    while(k > mask) {
        k = (k & mask) + (k >> n);
    }
    return k == mask ? 0 : k;
}

unsigned long long quotient_2n1(unsigned n, unsigned long long k) {
    unsigned long long mask = (1ULL << n) - 1ULL, quotient = 0;
    while(k > mask) {
        quotient += k >> n;
        k = (k & mask) + (k >> n);
    }
    return k == mask ? quotient + 1 : quotient;
}

が型の半分の幅である特殊なケースでnは、ループは最大2回実行されるため、分岐が高価な場合は、ループを展開して無条件にループ本体を2回実行する方がよい場合があります。

于 2012-03-25T13:13:58.033 に答える
0

そうではない。x mod 2^n と x/2^n の方が簡単です。x/2^n は x>>n として実行でき、x mod 2^n は x&(1<<n-1) を実行します。

于 2012-03-25T01:10:40.530 に答える