Special simple random number generator

Question

How to create a function, which on every call generates a random integer number? This number must be most random as possible (according to uniform distribution). It is only allowed to use one static variable and at most 3 elementary steps, where each step consists of only one basic arithmetic operation of arity 1 or 2.

Example:

int myrandom(void){
  static int x;
  x = some_step1;
  x = some_step2;
  x = some_step3;
  return x;
}

Basic arithmetic operations are +,-,%,and, not, xor, or, left shift, right shift, multiplication and division. Of course, no rand(), random() or similar stuff is allowed.

Answer 1

the Linear Congruential Generator is one of the oldest and simplest method:

int seed = 123456789;

int rand()
{
  seed = (a * seed + c) % m;
  return seed;
}

Ony few instruction with basic arithmetic operations, that's what you needed.

Mind that this algorithm works fine just if a, c and m are chosen in a particular way!

To guarantee the longest possible period of this sequence c and m should be coprime, a-1 should be divisible by all prime factors of m and also for 4 if m is divisible by 4.

Some examples of values are shown in Wikipedia: for example ANSI C for some compilers proposes m = 2^32, a = 1103515245 and c = 12345

Answer 2

You might have a look at this. It's far from beeing a "perfect" random number generator, but it does fulfil your requirements as far as i can see.

Here you can find some additional information about random number generation.

Answer 3

Boost has a very nice random number library, and the source code is available, so you could try looking there and using what you need (i.e. cut and paste).

Answer 4

Here's a function with uniform distribution over the entire range of int:

int rand()
{
  static int random = 0;
  return random++;
}

Answer 5

If I write man rand, I can read a possible example, given in POSIX.1-2001, for implementing rand() and srand(). See e.g. here. If you need something more sophisticated, take a look at GNU Scientific Library; you can of course download the code and see the implementation(s).