Is there an easy way to make a 2 ^ 32 - 1 module?

Question

I just heard that x mod (2^32-1) and x / (2^32-1) will be easy, but how?

to calculate the formula:

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

For b = 2^32 , its easy, x%(2^32) == x & (2^32-1) ; and x / (2^32) == x >> 32 . (there is no XOR here). How to do this when b = 2 ^ 32 - 1.

At https://en.wikipedia.org/wiki/Multiply-with-carry . They say " arithmetic for modulus 2^32 − 1 requires only a simple adjustment from that for 2^32 " So what is “easy setup”?

Answer 1

(This answer only handles the case of mod .)

I assume that the data type x is more than 32 bits (this answer will really work with any positive integer) and that it is positive (the negative case is just -(-x mod 2^32-1) ), because if it equal to most 32 bits, the question can be answered

 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 

We can write x in the base 2 ^ 32 with the numbers x0 , x1 , ..., xn . So

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

This makes the answer clearer when we execute the module, since 2^32 == 1 mod 2^32-1 . it

  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 matches the sum of the base 2 ^ 32 digits! (we cannot discard mod 2 ^ 32-1 yet). Now we have two cases: either the sum is between 0 and 2 ^ 32-1, or it is larger. In the first we are done; in the future we can simply return until we get from 0 to 2 ^ 32-1. Getting numbers in the base 2 ^ 32 is fast, since we can use bitwise operations. In Python (this does not handle negative numbers):

 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 

(This is very easy to generalize to x mod 2^n-1 , in fact you are simply replacing any 32 n event in this answer.)

(EDIT: added elif clause to avoid endless loop on mod_2to32sub1(2**32-1) . EDIT2: replaced ^ with ** ... oops.)

Answer 2

So, you calculate the "rule" 2 ³² = 1. In the general case, 2 ^{32 + x} = 2 ^x . You can simplify 2 ^{a by} taking the exponent modulo 32. Example: 2 ⁶⁶ = 2 ² .

You can express any number in binary format, and then lower the numbers. Example: the number 2 ⁴⁰ + 2 ³⁸ + 2 ²⁰ + 2 + 1 can be simplified to 2 ⁸ + 2 ⁶ + 2 ²⁰ + 2 + 1.

In general, you can group indicators every 32 degrees by 2 and “lower” all indicators modulo 32.

For 64-bit words, a number can be expressed as

2 ³² A + B

where 0 <= A, B <= 2 ³² -1. Getting A and B is carried out using bitwise operations.

So you can simplify this to A + B, which is much less: no more than 2 ³³ . Then check if this number is at least 2 ³² -1, and subtract 2 ³² - 1 in this case.

This avoids expensive direct separation.

Answer 3

The module has already been explained, however, we repeat.

To find the remainder k modulo 2^n-1 , write

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

Then

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

If a + b >= 2^n , repeat until the remainder is less than 2^n , and if this leads you to a + b = 2^n-1 , replace this with 0. Each "right shift by n and add to the last n bit "moves the first bit of the set to the right by n or n-1 places (if k < 2^(2*n-1) , when the first bit of the set after changing and adding can be bit 2^n ). Therefore, if the width of the type is large compared to n , this will require many shifts - consider a 128-bit type and n = 3 , for large k you will need more than 40 shifts. To reduce the number of shifts needed, you can use the fact that

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

we will only use the fact that 2^n - 1 divides 2^(m*n) - 1 for all m > 0 . Then you shift the multiples of n , which are about half the maximum bit length that the value in this step can make. For the above example of 128-bit type and residual modulo 7 ( 2^3 - 1 ), the closest multiples from 3 to 128/2 are 63 and 66, the first shift is 63 bits

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

to get a number with no more than 66 bits, then shift by 66/2 = 33 bits

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

to reach no more than 34 bits. The next shift is 18 bits, then 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 

Now there is one subtraction if r_7 >= 2^3 - 1 . To calculate k % (2^n -1) in a b-bit type, O (log ₂ (b / n)) is needed.

The result is similar, write again

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

so k/(2^n-1) = b + (a+b)/(2^n-1) , and we continue for now a+b > 2^n-1 . Here, unfortunately, we cannot reduce the work by shifting and masking about half the width, so the method is effective only when n not much less than the type width.

Code for quick cases when n not too small:

 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; } 

In the particular case when n is half the width of the type, the cycle is performed no more than two times, therefore, if the road branches, it may be better to expand the cycle and unconditionally execute the body of the cycle twice.

Answer 4

This is not true. What you heard is x mod 2 ^ n and x / 2 ^ n is simpler. x / 2 ^ n can be executed as x → n, and x mod 2 ^ n, do x & (1 <n-1)