Reputation: 30522

Special simple random number generator

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.

Upvotes: 16

Answers (8)

richard1941

Reputation: 151

I assume you are working with floating point numbers. Using Weyl's Theorem, pick any irrational number I. Pi and Phi are convenient on my computer, but it does not have to be transcendental, Sqrt(2), the oldest known irrational, will work OK. Pick any seed x between 0 and 1. The next random number is just x' = x + I modulo 1. In WP-34s code of my handheld, this would be

LBL 99
RCL 98
RCL+99
FRC
STO 99
RTN

The initial seed is pre-stored in register 99 and the addend is pre-stored in register 98. This code reflects the fact that on my computer things run faster when stack lift is minimized.

It is lightning fast and uses only two registers: one for the seed and one for the addend. XEQ 99 from the keyboard or in the code of your application will put a random number onto the stack. This code leaves the random number on the stack and does not lift the stack at all in computing the random number. Register 99 holds the seed and register 98 is pre-loaded with the irrational. (Yes, I know, the irrational is not exactly represented in computer memory, but it's close enough for gubbermint work). It is fast as lightning and uses only two registers out of the 99 in my computer. The last random number generated is always available in register 99 if you should need to re-use it. It is so simple, you can easily code it into the computer language of your choice. I use it in Excel VBA ***, for example.

The period is unknown, probably beyond the ability of my computer to measure. The distribution of resulting values is highly uniform. I have tested it with the chi square test 90 bins, and also the comb test with comb factor 1000 and 90 bins with Phi as the addend, and it gets ridiculously low chi square scores even with sample sizes in the bazillions.

Alas, you know what to expect when things are too good to be true! You can NOT use this to generate random pairs or triples, or higher order sets because each result is strongly dependent on its precursor. For higher dimensions, you must use a separate RNG for each dimension, and the addends must differ to avoid undesired correlations between successive random numbers. I have tested this for up to three dimensions, and found the triples from three independent RNG's to be highly independent and very uniform in the 3-cube.

Confession 1: I have done extensive testing and have still not broken the RAN# function that is built into my computer.

Confession 2: The exact set of random numbers you get depends on your platform due to differences in word length, number representation (binary or decimal), and other factors.

*** The creators of Excel VBA are to be awarded the Admiral Grace Brewster Hopper award for excellence in program language technology.

Upvotes: -1

raoof

Reputation: 572

I guess this is good enough for large range but I haven't used it yet. two number must be coprime.

u32 rand()
{
  static u32 seed = 3459173429;
  seed = 910230123 + seed ;
  return seed;
}

working example

int printf(char* , ...);

typedef unsigned int u32;
typedef   signed int i32;

u32 rand()
{
  static u32 seed = 3459173429;
  seed = 910230123 + seed ;
  return seed;
}

i32 randInt(i32 a, i32 b)
{
  return (rand() % (b - a)) + a;
}

void main()
{
  for(int i = 0 ; i < 10000 ; i += 1)
  {
    printf("%d\n", randInt(-50, 50));
  }
}

Upvotes: 0

Jack

Reputation: 133669

Linear congruential generators are one of the oldest and simplest methods:

int seed = 123456789;

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

Only a few instruction with basic arithmetic operations, that's all you need.

Mind that this algorithm works fine only 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 parameters are shown on Wikipedia: for example ANSI C for some compilers proposes m = 2 ³¹, a = 1103515245 and c = 12345.

Upvotes: 59

misioptysio

Reputation: 153

public long randomLong() {
  x ^= (x << 21);
  x ^= (x >>> 35);
  x ^= (x << 4);
  return x;
}

Seed cannot be 0. Source: http://www.javamex.com/tutorials/random_numbers/xorshift.shtml#.VlcaYzKwEV8

Additional info in wiki: https://en.wikipedia.org/wiki/Xorshift

Upvotes: 12

andand

Reputation: 17507

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).

Upvotes: 0

ShinTakezou

Reputation: 9681

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).

Upvotes: 0

Bill

Reputation: 14695

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

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

Upvotes: 0

phimuemue

Reputation: 36081

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.

Upvotes: 3

Special simple random number generator

Answers (8)

Related Questions