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.

Levenson

No time(), or trig functions? – Disaccustom

This is a worthless interview-question. It asks for something that you know (or might know, or you might just have read in a magazine), not something that you can (or can deduct, or can reason about). – Earthaearthborn

return (3); (that's just as random as anything is, in this context of interview question) – Affirm

@Kevin: This function must give new random result on every call. – Levenson

#1, it's a joke. #2, who is to say that returning the same number is not random? – Affirm

And it should be pointed out that 3 is well distributed on the range (3). – Desexualize

A good random number generator is a very, very difficult problem. Unless the candidate already has lots of experience with them and the math behind them, they aren't going to come up with anything reasonable. "The generation of random numbers is too important to be left to chance." - Robert R. Coveyou – Leavitt

@Earthaearthborn it might be used to find out how the candidate reacts to poor questions - after all, no job involves being asked nothing but well-posed questions... – Barman

I follow Kevin's line. Using only the allowed constructs, myrandom will be deterministic no matter how hard you try. Tell the interviewer about difference between randomn and pseudo-random random numbers. – Carmencarmena

Patrick: It wouldn't be a worthless question for an interview with a cryptoanalyst. For a general programming or software engineering job, the correct answer is: everything depends on your definition of "most random possible", so a general answer is impossible unless you give a bunch of math to describe what you really want (or an example of an application). – Abrams

Answer 1

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.

Eyesight

Worth noting that m = 2^32 won’t work in your above code … for such a value, the % m operation can just be removed (and that’s indeed the reason for choosing it). – Increment

@Levenson - what is 'int seed = 123456789;' then? – Affirm

He means that it's not supposed to have a seed. @Levenson 'seed' is the static variable you are allowed. It has to have an initial value of some sort. – Udall

Nick, the solution moved seed from inside the function call to outside the function call (after renaming it from 'x'). psi can claim there is no seed, but, by definition, 'static int x' is always going to be valued at 0, therefore being no different from 'int seed = 123456789' – Affirm

one of the oldest, simplest and definitely badest. – Tomlinson

I come here indirectly, and so for future readers, I'd like to add that this is quite close to the reference implementation of rand(). – Digestant

I tried this algorithm with proposed values of m, a and c. For any seed it generates alternate odd and even numbers. If I do random%2 to generate random sequence of flags I simply ended up getting 1,0,1,0,1,0 and so on. – Krohn

Note that this will generate cyclic mod n sequences of {0, 1 ,..., n-1} if modded with a power of 2, as @Krohn mentions. – Revolting

Wikipedia article lists ANSI C as using m = 2^31 – Bearer

The low order bits generated by an LCG are crap quality. Only return the higher order bits. With 64bit ints you could XOR the top 32 bits over the bottom 32 bits an massively improve the quality. LCGs have a bad reputation precisely because people use the low order bits. For example, a 128bit LCG passes the Practrand test suite if you ditch the low order bits. – Turnpike

Answer 2

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

Opprobrious

where is the "randomness" in this solution? – Bold

The "randomness" is in XOR operation flipping shifted bits "randomly" :). For this purpose we need at least one bit set, that's why the seed cannot be zero. – Opprobrious

... and this type of solution seems cheaper in terms of CPU cycles: no multiplication, no dividing - might be useful for intensive generating. – Opprobrious

I understand now (if I'm not wrong) that x here is the previous generated random number, ain't it? – Bold

Sorry for the delay. Yes, that x is a seed / previously generated number, so according to the generation rules, next value is obtained from the previous one using simple arithmetic operations. – Opprobrious

Answer 3

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.

Kulseth

Answer 4

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

Precedence

Answer 5

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

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

Tinstone

Not entirely random, however. =P Although I suppose it's exactly as random as any other psuedorandom generator. – Decennary

not random: it is easily recognizable how it is produced (the rule of production), so this qualifies it as not random (and very bad pseudorandom). – Charisecharisma

it produces all outputs with an equal probability = random – Cheviot

@Shin: I never claimed it was a good PRNG, just that it was a PRNG. :P – Tinstone

the OPer was asking for a good PRNG, or at least for a not so bad PRNG;; @Maring Beckett, it is simply false, it is not random: en.wikipedia.org/wiki/Randomness#Randomness_measures_and_tests i.e., even though it follows the statistics, that sequence can't be generated by not-related stochasting "events", so it can be demonstrated that it is not random (for all the fields where randomness is required; of course you can insist that this rand() generates random numbers, but noone will use that "random" generator if s/he needs randomness) – Charisecharisma

@Shin: The OP was asking for a solution to an interview question, and the only requirement I saw was a uniform distribution. :) – Tinstone

s/he says "This number must be most random as possible (according to uniform distribution)". Even though it is not so precisely expressed, it is obviously not considerable a solution like yours, since the "simple-worded" requirement "most random as possible" rules out your generator (that as explained already, can't be used to have a source of randomness) – Charisecharisma

There is absolutely no reason why that sequence couldn't be generated by independent random events. It is vanishingly unlikely, but so is any particular sequence, a priori. – Mandel

@Shin: How are you planning to prove that any particular solution is the "most random possible" solution? – Tinstone

@Tinstone I don't need to prove it. You instead have to prove that 1 2...n-1 n n+1... is a random seq,and that can be considered a "real" good random seq;and (@caf)it'd change the theory if it'd be produced by independent stochastic events:we should conclude they are not indenpendent.There's a reason why even the simpler PRG does not work that way and try to generate a sequence that looks random (even though further analysis would prove it is not,and this is about doing good PRGs:making harder to recognize its pseudorandomness,longer the seq needed to recognize it) – Charisecharisma

Moreover(@caf)your reasoning is about the "classical" simplistic vision of many statistics-acquainted persons,and I've already treated indirectly this before your comments,so you have not deepened the complex argument of randomness.Not saying wikipedia has the full answer,but it is a starting point easy to be shared (instead of lifting my back going to search books where I first have seen the argument treated)and that already has most of the needed "pointers", keywords and clues en.wikipedia.org/wiki/Randomness – Charisecharisma

@Shin: A perfectly good source of random numbers (a physics-based generator) will produce all sequences of such rising numbers! The longer the sequence, the longer you'll have to wait to see it, but just try it for yourself. Get any random number source you consider decent, and start looking for increasing sequences in it. Prepeare to be amazed :) Hint: The probability of getting a rising sequence of arbitrary length is non-zero. That's it. And that's also how you can differentiate between a PRNG and a real RNG. A PRNG will never generate some sequences, the real one will. – Abrams

@Shin: In fact, a simple way (usually) of telling if you're dealing with a PRNG is to chose an arbitrary sequence of numbers, and check if you're getting it on average "sufficiently often". As your sequence length goes up, eventually you'll hit sequences that a PRNG will never produce, whereas a real random number source will indeed produce them as expected from theory. I suspect you've never really looked at truly random sequences of numbers. At short lengths they appear quite "nonrandom". – Abrams

@KubaOber I've seen enough and I'm not surprised,but I've not an infinite time to prove you are right and I'm wrong.What I know,is that after a while(depending on the pace the generator is triggered at)I can bet on the next "event"this amazingly taunting PRNG will give,and I'll win with a probability of 1.Not true,since the int will overflow.If the pace is fast,I can observe it while alive and learn how to predict and bet on overflow too.That's not PRNG.I suggest another reading you can learn by,as starting point:en.wikipedia.org/wiki/Random_sequence – Charisecharisma

What a load of nonsense. A counter that gets incremented by one isn't any kind of PRNG by any stretch of the imagination. Not even a bad one. It just isn't. – Turnpike

@Kuba You don't always need a perfect RNG with uncorrelated sequences. And when you don't, simple RNG's will do the job just fine. It all depends on the application. Also, remember the words of Knuth: the number of tests that can be applied to an RNG is endless. (I don't know if that means countable.) – Ie

Answer 6

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

Charisecharisma

Answer 7

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));
  }
}

Scuff

Answer 8

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.

Ie