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.

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

Solution 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

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

Comments

[Konrad Rudolph]

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

[KevinDTimm]

@psihodelia - what is 'int seed = 123456789;' then?

[Erik Forbes]

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

[Nick Johnson]

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

[ShinTakezou]

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

[KevinDTimm]

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'

[Martin Beckett]

it produces all outputs with an equal probability = random

[Bill]

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

[ShinTakezou]

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_tes‌​ts 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)

[Bill]

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

[ShinTakezou]

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)

[caf]

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.

[Bill]

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

[ShinTakezou]

@Bill 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)

[ShinTakezou]

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

[Alexandre C.]

one of the oldest, simplest and definitely badest.

[std''OrgnlDave]

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

[Kuba hasn't forgotten Monica]

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

[Kuba hasn't forgotten Monica]

@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".

[ShinTakezou]

@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

[Atul]

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.

[Gian Paolo]

where is the "randomness" in this solution?

[misioptysio]

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.

[misioptysio]

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

[Gian Paolo]

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

[misioptysio]

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.

[Mateen Ulhaq]

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

[scx]

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

[Thorham]

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.

[Thorham]

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.