0

I was reading about CMWC PRNG and found the claim that it is possible to compute a mod (2^32 - 1) without using slow modulo operation. My question is very similar to Is there any easy way to do modulus of 2^32 - 1 operation? but I found only while-loop-based solutions for the general case of large a that may be even larger than 2^64.

I tried to understand how the authors of CMWC implemented their algorithm (page 9) without loops and extracted crucial piece of it. I wrote it in python pseudocode to make it more clear when modulo division by 2^32 happens as C++ implementation hides it behind unsigned overflow. So the following fragment of code

c = (a // b) % b
x = (a + c) % b
if (x < c):
    x = (x + 1)
    c = (c + 1)

is equivalent to

x = a % (b - 1)
c = a // (b - 1)

It works for b = 2^32 and 0 <= a < 2^64 when a % (2^32 - 1) != 0 (such a seems to be never used in this PRNG). Actually, this pseudocode works correctly even in the general case of b > 3, 0 <= a < b^2, a % (b - 1) != 0.

So my question is how to explain that the pseudocode above works at all? I don't understand the reasoning behind it and wondering how I could come up with this simplification of division myself.

Curious
  • 507
  • 3
  • 16
  • Somebody just recognized a pattern that works up to `b^2 - 1`, but doesn't work when `a % (b-1) == 0`. To see the pattern for yourself, choose a smallish `b` like `b=8`. Then for each `a` from 0 to 63, print `a`, `a%7`, `a//7`. If `a%7` is not 0, print the raw `x` and `c` values from the first snippet, and the adjusted `x` and `c` values if `x < c`. Then ponder the results before you on the screen, and you'll understand it as well as anybody does. – user3386109 Jul 17 '21 at 00:25
  • if u need "to explain that the pseudocode" to ur self.. this should do.. but if u need a proving method (like writing a paper..) then here might not be the best place.. I think [math.se] SE suits this question better. – p._phidot_ Jul 17 '21 at 01:28

0 Answers0