The following code comment comes from PHP, a free and open source project. I have done my own research and I cannot find any evidence to support the argument made in this code comment. Thus the only tool to support such this statement is mathematics.
Prove or disprove that that taking the modulus of a random number n
for any value of M
such that M<n
decreases entropy. Or to clarify the operation is: n mod M
and the constraint is for any value where: M<n
, M>0
. The 2nd part of the proof is to show that n' = a + n(b-a+1)/(M+1)
does not decrease entropy under the same constraint: Where n is any random value and M is any value smaller than n and M greater than zero.
Or to put it another way how is the value produced by n' = a + n(b-a+1)/(M+1)
more random than the value produced by n mod M
for the same values of n and M such that M<n
.
Any helpful information on this topic will earn you a +1 by me. Proving that n mod M
skews the distribution of random values over a range, would be a HUGE accomplishment in my humble opinion.
Thank you for your time.
/*
* A bit of tricky math here. We want to avoid using a modulus because
* that simply tosses the high-order bits and might skew the distribution
* of random values over the range. Instead we map the range directly.
*
*
* We need to map the range from 0...M evenly to the range a...b
* Let n = the random number and n' = the mapped random number
*
* Then we have: n' = a + n(b-a)/M
*
* We have a problem here in that only n==M will get mapped to b which
*
* means the chances of getting b is much much less than getting any of
* the other values in the range. We can fix this by increasing our range
* artifically and using:
*
* n' = a + n(b-a+1)/M
*
*
* Now we only have a problem if n==M which would cause us to produce a
* number of b+1 which would be bad. So we bump M up by one to make sure
* this will never happen, and the final algorithm looks like this:
*
*
* n' = a + n(b-a+1)/(M+1)
*
* -RL
*/