Here is some C++ code demonstrating iterating the following linear congruence:
x = (2*x) mod (2^32-5)
We do the computation with 32-bit arithmetic only. A naive implementation would overflow.
2^32-5 is a prime number that has 2 as a primitive root.
The key tricks are excerpted below:
// underflow wraps around to yield the value 2^32-5
const uint32_t modulus=-5;
const uint32_t mhalf=modulus/2;
//...
bool ishigh = (x > mhalf);
x *= 2; // overflow should truncate
if(ishigh){
x -= modulus; // underflow should wrap around
}
EmoticonEmoticon