Linear congruent generator in C ++

Question

I wrote a simple program (actually trying to implement a linear congruent generator), but I'm not quite sure that it works as it should.

I wanted to create 250 numbers from [0,1] using my generator. However, it seems that instead of random numbers, I get equal values.

How to improve it / what have I done wrong?

Here is the code:

#include <iostream> #include <cmath> static const double A = 0.001342; static const double C = 0.00025194; static const double RAND_MAX = 1.0; double rand() { static double prev = 0; prev = A * prev + fmod(C, RAND_MAX); return prev; } int main(int argc, char **argv) { for(int i=0; i<6; i++) std::cout << rand() << "\n"; return 0; } 

And the conclusion:

 0.00025194 0.000252278 0.000252279 0.000252279 0.000252279 0.000252279 

Switching to int instead of double , however, gives good results:

 #include <iostream> #include <cmath> static const int A = 5; static const int C = 3; static const int RAND_MAX = 8; double rand() { static int prev = 1; prev = A * prev + (C % RAND_MAX); return prev; } int main(int argc, char **argv) { for(int i=0; i<100; i++) std::cout << rand() << "\n"; return 0; } 

Conclusion:

 8 43 218 1093 5468 27343 136718 683593 3.41797e+06 1.70898e+07 8.54492e+07 4.27246e+08 2.13623e+09 2.09122e+09 1.86615e+09 7.40836e+08 -5.90786e+08 1.34104e+09 ... 

But I need this to generate random double numbers, greater than or equal to 0 and less than or equal to 1: (

Answer 1

This is not a program, this is a choice of numbers.

prev at the beginning is zero, so the first number becomes C

Then prev is equal to C , which makes prev A*C + C However, A*C so small that when you add it as a floating point to the previous one, significant numbers are shifted, and you are left with what you had before.

You can learn more about What Every Computer Scientist Should Know About Floating-Point Arithmetic .

Answer 2

First, do not use floating point arithmetic for LCG. Floating point is inherently inaccurate and can lead to undesirable behavior, such as fixed-point convergence or alternating short sub-cycles. With integer arithmetic, number theory can tell you which parameters are guaranteed to achieve a complete cycle, i.e. Each value between 0 and M-1 (where M is your module) will be . See the LCG Wikipedia article for full cycle parameter requirements and a table of commonly used parameters.

Secondly, you misinterpreted the LCG formula. It should be:

 prev = (A * prev + C) % M; 

Thirdly, with your current choice of parameters, you will not come across this, but in general, your intermediate calculations should be performed using long to avoid overflow. The % operation will return an answer to int , but if you follow the arithmetic of int , then multiplying may not give a mathematically correct value, which ensures the full length of the loop and the correct distribution behavior.