0
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ Which book? Which section / page in the book? That may help others who have the book answer with reference to that method... $\endgroup$ – ShreevatsaR Sep 5 '18 at 1:24
  • 1
    $\begingroup$ 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 $\endgroup$ – Bulat Sep 7 '18 at 11:38
  • $\begingroup$ 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 $\endgroup$ – Bulat Sep 7 '18 at 11:50
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.