Recently I had some difficulties to generate pseudo-random numbers in C by using Lehmer’s method. Lehmer random number generator is an easy-to-implement algorithm that provides random number stream. Basically you have a multiplier (a) and modulus (m) which you use in a basic arithmetic to get next number. Let we have the initial seed $$s$$, than the following numbers can be obtained as
$$ s = ( sa ) \pmod{m} $$
and if you want to get uniform numbers between zero and one, then you can divide $$s$$ to $$m$$. The major problem is, when $$m$$ is a big number (like $$2^{31} -1$$) then you may get some very big numbers for $$s$$. Later when I need to multiply big numbers, like $$s=65467721$$, multiplying this number with my multiplier $$a=48271$$ was leading to overflow. Let’s try the following code:
|
1 2 3 4 |
int s1 = 65467721; printf("s1: %d\n", s1); s1 = ( (s1) * 48271L) % 2147483647; printf("s1: %d\n", s1); |
The output is
|
1 2 |
s1: 65467721 s1: -903569465 |
As you see our multiplication leaded overflow thus returned a negative number, which has no value. A quick fix to this problem is adding “unsigned long long” in front of $$s$$. Consider the following code:
|
1 2 3 4 |
int s2 = 65467721; printf("s2: %d\n", s2); s2 = ( (unsigned long long) (s2) * 48271L) % 2147483647; printf("s2: %d\n", s2); |
which gives
|
1 2 |
s2: 65467721 s2: 1243915654 |
It was actually a bug in the latest project I’m coding. After driving me nuts for 2 weeks, I finally get rid of the problem once and for all.
