17

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.

Andreas Rejbrand
  • 105,602
  • 8
  • 282
  • 384
psihodelia
  • 29,566
  • 35
  • 108
  • 157
  • No `time()`, or trig functions? – FrustratedWithFormsDesigner Jun 17 '10 at 14:50
  • 24
    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). – Patrick Jun 17 '10 at 15:03
  • 1
    return (3); (that's just as random as anything is, in this context of interview question) – KevinDTimm Jun 17 '10 at 15:06
  • @Kevin: This function must give new random result on every call. – psihodelia Jun 17 '10 at 15:07
  • 2
    #1, it's a joke. #2, who is to say that returning the same number is not random? – KevinDTimm Jun 17 '10 at 15:10
  • 7
    And it should be pointed out that 3 is well distributed on the range (3). – LanceH Jun 17 '10 at 15:13
  • 4
    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 – whatsisname Jun 17 '10 at 16:41
  • 2
    @Patrick 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... – AakashM Jun 17 '10 at 16:44
  • 1
    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. – Peter G. Jun 25 '10 at 18:50
  • 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). – Kuba hasn't forgotten Monica Feb 04 '13 at 20:20

8 Answers8

57

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.

Chris Morgan
  • 86,207
  • 24
  • 208
  • 215
Jack
  • 131,802
  • 30
  • 241
  • 343
  • 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). – Konrad Rudolph Jun 17 '10 at 14:57
  • 2
    @psihodelia - what is 'int seed = 123456789;' then? – KevinDTimm Jun 17 '10 at 15:09
  • 1
    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. – Nick Johnson Jun 17 '10 at 15:25
  • 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' – KevinDTimm Jun 17 '10 at 16:00
  • 2
    one of the oldest, simplest and definitely badest. – Alexandre C. Jun 24 '10 at 16:19
  • 2
    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(). – std''OrgnlDave Apr 03 '12 at 23:19
  • 4
    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. – Atul Jul 01 '14 at 18:50
  • 1
    Note that this will generate **cyclic** mod n sequences of {0, 1 ,..., n-1} **if modded with a power of 2**, as @Atul mentions. – Mateen Ulhaq Aug 19 '16 at 09:47
  • Wikipedia article lists ANSI C as using m = 2^31 – scx Jun 24 '18 at 18:23
  • 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 May 04 '19 at 13:46
12
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

misioptysio
  • 153
  • 1
  • 6
  • where is the "randomness" in this solution? – Gian Paolo Nov 27 '15 at 13:25
  • 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 Nov 28 '15 at 20:23
  • ... and this type of solution seems cheaper in terms of CPU cycles: no multiplication, no dividing - might be useful for intensive generating. – misioptysio Nov 30 '15 at 11:09
  • I understand now (if I'm not wrong) that x here is the previous generated random number, ain't it? – Gian Paolo Nov 30 '15 at 11:15
  • 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. – misioptysio Dec 09 '15 at 13:52
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.

phimuemue
  • 34,669
  • 9
  • 84
  • 115
0

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

andand
  • 17,134
  • 11
  • 53
  • 79
0

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

ShinTakezou
  • 9,432
  • 1
  • 29
  • 39
0

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));
  }
}
raoof
  • 538
  • 1
  • 6
  • 12
-1

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

int rand()
{
  static int random = 0;
  return random++;
}
Bill
  • 14,257
  • 4
  • 43
  • 55
  • Not entirely random, however. =P Although I suppose it's exactly as random as any other psuedorandom generator. – Erik Forbes Jun 17 '10 at 15:24
  • 4
    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). – ShinTakezou Jun 17 '10 at 15:53
  • it produces all outputs with an equal probability = random – Martin Beckett Jun 17 '10 at 16:38
  • 7
    @Shin: I never claimed it was a *good* PRNG, just that it was a PRNG. :P – Bill Jun 17 '10 at 17:26
  • 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: http://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) – ShinTakezou Jun 17 '10 at 17:53
  • 1
    @Shin: The OP was asking for a solution to an interview question, and the only requirement I saw was a uniform distribution. :) – Bill Jun 17 '10 at 18:38
  • 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) – ShinTakezou Jun 17 '10 at 18:48
  • 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. – caf Jun 18 '10 at 05:50
  • 2
    @Shin: How are you planning to prove that any particular solution is the "most random possible" solution? – Bill Jun 18 '10 at 16:39
  • @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 Jun 20 '10 at 14:16
  • 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 http://en.wikipedia.org/wiki/Randomness – ShinTakezou Jun 20 '10 at 14:28
  • 3
    @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 Feb 04 '13 at 20:26
  • 3
    @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". – Kuba hasn't forgotten Monica Feb 04 '13 at 20:28
  • @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:https://en.wikipedia.org/wiki/Random_sequence – ShinTakezou Feb 05 '13 at 13:10
  • 1
    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. – Thorham May 04 '19 at 13:47
-3

I use this

SUBROUTINE GNA(iiseed)
    USE Variaveis
    parameter (ia=843314861,ib=453816693,m=1073741824, r231=1./2147483648.)
    INTEGER :: iiseed

    iiseed = ib + ia*iiseed
    if (iiseed.lt.0) iiseed = (iiseed+m) + m
    RndNum = iiseed*r231

END SUBROUTINE GNA

A big gain of randomness can be achieved without spending more computational time creating a random number generator for each call the random number generator made in the program.

This is a very good trick!

Denis da Mata
  • 43
  • 6