# Efficient way to compute mod(w +1) or mod(w - 1) where w= 2^p

Knuth in his book provides a method of how to efficiently calculate mod(w +1) or mod(w-1) where w is a power of 2. I am not sure I could understand his assembly language completely.

Could you explain how to efficiently calculate those mod operations through mod(2^w) and can we extend it to a more common case of mod(w +/- c)?

Another question if we mod by a constant primary number in many places they mention different tricks compilers can do to avoid expensive division operation. Any ideas about those tricks?

• Which book? Which section / page in the book? That may help others who have the book answer with reference to that method... – ShreevatsaR Sep 5 '18 at 1:24
• I suggest to make separate question about division by constant. It may be a large topic. github.com/Bulat-Ziganshin/FastECC/blob/… for the starter – Bulat Sep 7 '18 at 11:38
• Also make extremely attention to adding proper question tags (I proposed a few to this one). Many of us doesn't check every question here but subscribed to specific tags. Also, if you plan to use it for hashing - there are faster alternatives, f.e. you can multiply number by a constant to mix bits, and then compute h*K mod 2^N to get number in 0..K-1 range – Bulat Sep 7 '18 at 11:50

## 1 Answer

Mod(2^N-1) algo:

Split number into N-bit parts (i.e. extract digits in 2^N-ary system). Sum up these parts. If result is higher than 2^N-1 - reiterate. Because

256 mod 255 = 1
2*256 mod 255 = 2
256*256 mod 255 = 256 mod 255 = 1
...
A*2^N mod (2^N-1) = A
A*2^N*2^N mod (2^N-1) = A*2^N mod (2^N-1) = A
...


Mod(2^N+1) algo:

Split number into N-bit parts. Sum up these parts with changing signs. If result is higher than 2^N+1 - reiterate. Because

256 mod 257 = -1 mod 257
2*256 mod 257 = -2 mod 257
256*256 mod 257 = -1*256 mod 257 = 1
...
A*2^N = -A (modulo 2^N+1)
A*2^N*2^N = -A*2^N = A (both equations are modulo 2^N+1)
...


Mod(2^N-K) - multiply by K each next digit

Mod(2^N+K) - multiply by -K each next digit