[awsxfajy] Doubling mod 2^32-5

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
}