• Some Guru (unregistered)

    From the words of the master himself:

    Law RNG3: One should not use a random method to generate random numbers. - Donald Knuth

    http://www.cs.utsa.edu/~wagner/laws/rng.html

  • An Old Hacker (unregistered) in reply to Randy Waterhouse

    Easy: "This code is unbreakable"

  • (cs) in reply to Janis
    Janis:
    Only case where I'd suggest to call rand() multiple times: is that if you need 64bit number, but rand() generated 32bit number (or any other case where rand() generates less than you need). And do something like this a = rand() b = rand() result = a shl 32 + b

    Or you have better solution for this? (Without writing my own prng)

    Well, technically, a 32bit number fits just fine into a 64bit number, so you could just do result = rand() ;)

  • (cs) in reply to Grimoire
    Grimoire:
    Janis:
    Only case where I'd suggest to call rand() multiple times: is that if you need 64bit number, but rand() generated 32bit number (or any other case where rand() generates less than you need). And do something like this a = rand() b = rand() result = a shl 32 + b

    Or you have better solution for this? (Without writing my own prng)

    Well, technically, a 32bit number fits just fine into a 64bit number, so you could just do result = rand() ;)

    Yes, but if I need 64bit number with something else than 0 in first 32bits, then it will not help me :)

  • Crabs (unregistered) in reply to Janis
    Janis:
    Only case where I'd suggest to call rand() multiple times: is that if you need 64bit number, but rand() generated 32bit number (or any other case where rand() generates less than you need). And do something like this a = rand() b = rand() result = a shl 32 + b

    Or you have better solution for this? (Without writing my own prng)

    That's getting 2 random numbers, which is entirely valid. In fact, the prng is doing this when it gives you a 32 bit integer, as it's probably actually producing random bits, so it ends up using your method 32 times before you've used it once. This is valid. Seeding rand() with another rand(), or xoring rand()s and expecting more random results actually produces the opposite.

  • Engywuck (unregistered) in reply to JanisO
    JanisO:
    Grimoire:
    Janis:
    Only case where I'd suggest to call rand() multiple times: is that if you need 64bit number, but rand() generated 32bit number (or any other case where rand() generates less than you need). And do something like this a = rand() b = rand() result = a shl 32 + b

    Or you have better solution for this? (Without writing my own prng)

    Well, technically, a 32bit number fits just fine into a 64bit number, so you could just do result = rand() ;)

    Yes, but if I need 64bit number with something else than 0 in first 32bits, then it will not help me :)

    Oh, just expand it by adding a random number of 0's at random positions in between the 32 bits

  • Bernie (unregistered) in reply to TheRider
    TheRider:
    Bernie:
    Cloud computing sounds random to me; we should obviously hit the network whenever we need a random value.
    Now you're talking. Hit Google with a random query and hash the results html page. This should give you a truly random number.
    My ISP blocks Google since Google's home page is so large. Got any other ideas? Perhaps it is time to upgrade from my 300 baud modem to one of those new-fangled full-duplex modems.
  • Aleks (unregistered)

    Want something truly random and fun at the same time? Ready your webcam and have a look at:

    http://findarticles.com/p/articles/mi_m1200/is_n6_v152/ai_19680954/print?tag=artBody;col1

    or

    http://www.lavarnd.org/news/lavadiff.html

    P.S. You may want to test whether the randomness increases if you make funnier faces in front of the webcam...

  • Mikeh (unregistered) in reply to GettinSadda
    GettinSadda:
    Carlos92:
    The worst thing is that if you happen to run code that tries to increase randomness in an environment where you have a hardware-entropy based random number generator, the code actually *consumes* the entropy!
    For this reason when I do any form of randomizing in code that may be included in such a system I add ^rand() to the new seed as this factors back in the original randomness

    If you look at the source code for libc's rand(), it's already doing that. You're only making it LESS random.

  • Steve (unregistered)

    The interesting thing to me is that there's a teeny, tiny, microscopic kernel of truth to the reasoning. rand() is a pretty awful random number generator. There's a test in Knuth somewhere (I'm too lazy to get up to my bookcase and pull down the book) that shows that the distribution is anything but uniform.

    drand48() and random() are much better, I believe, but it's been a long time since I tested them to be sure.

    I remember getting badly bitten by rand() some (random) number of years ago.

    None of that, of course, is by way of justification for the truly Byzantine code in the article, of course.

  • smasher (unregistered) in reply to TheRider
    TheRider:
    DaveAronson:
    There are assorted tests for how random a RNG/PRNG's output is.
    Yes. And these tests usually involve the statistical analysis of a set of values generated from the randomizer under scrutiny.

    Statistical analysis will tell you how evenly deistributed the results are, but can it tell you whether the process deterministic or non-deterministic?

    An algorithm that produces the same 3000 even distributed integers every time is not what we're looking for.

  • jkupski (unregistered) in reply to Thief^
    Thief^:
    Taking a stupidly extreme example, a prng that only produces the following two numbers in never-ending sequence when given the seed "42": 6 9 6 9 6 9 6 9...

    The above would be an epic win, but nobody writes jokes in base 13. :)

  • (cs) in reply to smasher
    smasher:
    TheRider:
    DaveAronson:
    There are assorted tests for how random a RNG/PRNG's output is.
    Yes. And these tests usually involve the statistical analysis of a set of values generated from the randomizer under scrutiny.

    Statistical analysis will tell you how evenly deistributed the results are, but can it tell you whether the process deterministic or non-deterministic?

    An algorithm that produces the same 3000 even distributed integers every time is not what we're looking for.

    int rand() { static int current_rand = 0; current_rand = (current_rand + 1) % RAND_MAX; return current_rand; }

    \o/

  • Dan (unregistered) in reply to bnt
    bnt:
    There were some well-publicised problems with random-number generators in the past - e.g. this - but I hardly think this is the answer..! If your compiler's rand() function doesn't generate sufficiently-random numbers, get a better compiler.
    I didn't know the compiler generated randomness. I thought rand() was a library function...

    Seriously though, I still have yet to find a satisfying randomizer. Even for the simple task of randomly choosing a song to play, no matter which generator I try (Mersenne(sp?), random.org, etc), it still hits on the same one way too often, and it shows a lot of periodicity (hitting on songs in a certain cluster quite regularly, sometimes twice in a row). The closest I've gotten is to shuffle beforehand using an algorithm where the songs are divided between different hats and then you draw a number from each hat for each round. Not perfect, but at least you don't hear the same song over and over again.

  • (cs) in reply to JanisO
    JanisO:
    Grimoire:
    Janis:
    Only case where I'd suggest to call rand() multiple times: is that if you need 64bit number, but rand() generated 32bit number (or any other case where rand() generates less than you need). And do something like this a = rand() b = rand() result = a shl 32 + b

    Or you have better solution for this? (Without writing my own prng)

    Well, technically, a 32bit number fits just fine into a 64bit number, so you could just do result = rand() ;)

    Yes, but if I need 64bit number with something else than 0 in first 32bits, then it will not help me :)

    Man, getting picky, aren't ya?

    result = 0xffffffff00000000 + rand();

    There, something other than 0 in the first 32bits.

  • (cs) in reply to Thief^
    Thief^:
    Whatever you do, don't try to make a prng of your own without a degree in number theory.

    That is advice to live by. You may think you're the man, you may believe that you know the answer, but don't try to apply that amateur understanding to crypto. It is NOT intuitive, and it is too complex for many many people to fully understand.

    Adhere to best practices, and watch how the pros do it. The true beauty of crypto is that just because two people are using the same exact method, doesn't make it any less secure.

  • (cs) in reply to Dan
    Dan:
    bnt:
    There were some well-publicised problems with random-number generators in the past - e.g. this - but I hardly think this is the answer..! If your compiler's rand() function doesn't generate sufficiently-random numbers, get a better compiler.
    I didn't know the compiler generated randomness. I thought rand() was a library function...

    Seriously though, I still have yet to find a satisfying randomizer. Even for the simple task of randomly choosing a song to play, no matter which generator I try (Mersenne(sp?), random.org, etc), it still hits on the same one way too often, and it shows a lot of periodicity (hitting on songs in a certain cluster quite regularly, sometimes twice in a row). The closest I've gotten is to shuffle beforehand using an algorithm where the songs are divided between different hats and then you draw a number from each hat for each round. Not perfect, but at least you don't hear the same song over and over again.

    Is it actually hitting the same songs too often, or is it your own bias? "Man, this song kinda sucks. It always seems to play it!"

    The problem is that there will always be clusters of the same value in a random set. That's randomness for ya. It is only even distributed for a very large set. Roll a 6 sided die 20 or so times, are you are almost certainly likely to roll the same number 3 times in a row. Not very evenly distributed, but still random.

    What it sounds like you want is a more even distribution of random-like numbers. Take a look at quasi random number generators (such as the Sobol sequence). They may provide the behaviour you are looking for.

  • Mihail Minkov (unregistered)

    And just to top it all off - the code doesn't even run correctly :)

    i<(rand() & 16)

    This will only ever enter the loop if rand() is exactly 16. And then it will randomize 16 times. Hell yeah :)

  • PC Paul (unregistered) in reply to Grimoire
    Grimoire:
    JanisO:
    Grimoire:
    Well, technically, a 32bit number fits just fine into a 64bit number, so you could just do result = rand() ;)

    Yes, but if I need 64bit number with something else than 0 in first 32bits, then it will not help me :)

    Man, getting picky, aren't ya?

    result = 0xffffffff00000000 + rand();

    There, something other than 0 in the first 32bits.

    Cyclewaster.

    result = -rand();

  • paul (unregistered) in reply to Thief^
    Thief^:
    Whatever you do, don't try to make a prng of your own without a degree in number theory.
    Agreed. The best random-number-generation advice you will hear all day.
  • Kasper (unregistered) in reply to Thief^
    Whatever you do, don't try to make a prng of your own without a degree in number theory.
    Speaking of which... Did anybody ever take a look on the prng that GBDE uses to generate crypto keys? It takes a 2176 bit master key together with a sector number and apply a prng to produce a 128 bit sector key. On a first look the algorithm may look sensible. But if you look very carefully, you will realize, that the output is absolutely not uniform.

    It takes 128 random bits together with a sector number and apply MD5 to generate 128 supposedly random bits. Those are used as 16 8-bit integers to lookup 16 8-bit integers in an array of random numbers. The result is 128 random bits....

    Well, random but not uniformly random. The problem is, that there are two different ways two bytes could end up identical. You could have two indexes which happened to be the same, or you could have two different indexes selecting two values from two different places in the array, that happened to contain the same value.

    The result is, that the probability of having two identical bytes in the 128 bit string is twice as high as it would have been if the values had been uniformly random.

    The final step of that prng is to apply MD5 again, which of course doesn't add any entropy, so there are still values, which are about twice as likely as they should have been.

  • Rishu73 (unregistered)

    Why not just do the following:

    1d% A dice roller bubble from the Trouble board game A web cam mounted above so the dice can be read A dice recognition program done by my boss' 15-year old nephew done by Excel VBA.

    I think that is an adequately WTFed solution.

  • (cs) in reply to JanisO
    JanisO:
    Grimoire:
    Janis:
    Only case where I'd suggest to call rand() multiple times: is that if you need 64bit number, but rand() generated 32bit number (or any other case where rand() generates less than you need). And do something like this a = rand() b = rand() result = a shl 32 + b

    Or you have better solution for this? (Without writing my own prng)

    Well, technically, a 32bit number fits just fine into a 64bit number, so you could just do result = rand() ;)

    Yes, but if I need 64bit number with something else than 0 in first 32bits, then it will not help me :)

    Pseudo code: Bit64 bigRandomNum = rand()<<32 | rand();

  • moz (unregistered) in reply to Mihail Minkov
    Mihail Minkov:
    And just to top it all off - the code doesn't even run correctly :)

    i<(rand() & 16)

    This will only ever enter the loop if rand() is exactly 16. And then it will randomize 16 times. Hell yeah :)

    No, as (a) 17&16=16, and (b) rand() is not a constant. If rand() was perfectly random (and there's nothing in the code to identify a specific problem), the number of calls would follow Pascal's distribution, with an average of 1.

  • Havard (unregistered)

    I was working on a dice roll function for Ada. So I had it initialize the random number generator every time it's called... Not exactly ideal when it's seeded from the clock. Stupidly, I put bunches of delay's in there to get it out of the 1ms hole before I realized I could simply move the prng state from the function to the package. Yeah, I did my on wtf.

  • Leahn (unregistered) in reply to Thief^

    You ruined random numbers to me. :D

  • h (unregistered) in reply to Thief^
    Thief^:
    Or you could just implement or use an existing implementation of the mersenne twister prng, with it's 2^19937 − 1 long number sequence and 64-bit output. Or another, if you need to. Whatever you do, don't try to make a prng of your own without a degree in number theory.
    Yes! And don't try to do anything else with a degree in number theory. :)
  • frustrati (unregistered) in reply to Carlos92
    Carlos92:
    The worst thing is that if you happen to run code that tries to increase randomness in an environment where you have a hardware-entropy based random number generator, the code actually *consumes* the entropy!
    Will that make time go backwards?
  • pta (unregistered)

    for(i=0;i<(rand() & 16);i++)

    Well. This it clever Maybe s/16/15/ ?

  • foo (unregistered) in reply to pta
    pta:
    for(i=0;i<(rand() & 16);i++)

    Well. This it clever Maybe s/16/15/ ?

    but nobody has mentioned his cleverness on this line:

    Val[i]=(char)(( rand() >> 7) & 0x00FF);

    Please everyone, always make sure to AND your 32-bit number with the 16-bit value 0x00FF before trying to stuff it into an 8-bit char. Otherwise your CPU will asplode from the dreaded Integer Overflow Error (IOE).

  • (cs) in reply to Steve
    Steve:
    rand() is a pretty awful random number generator.

    I don't believe that any of the ISO C, POSIX or SuS specifications make any mention of the method that should be used by rand(): different platforms may produce totally different results.

  • (cs) in reply to Goofy McCheese
    Goofy McCheese:
    If you really want to increase the entropy: http://www.fourmilab.ch/hotbits/
    Offensive anti-creationist gibberish.

    If you really want to increase the entropy, just wait around a bit. It's fool-proof. It'll only take a Poincaré recurrence time for the quantum state of a hypothetical box containing a black hole with the estimated mass of the entire universe, which is apparently 10^10^10^10^10^1.1 years, or thereabouts. Now, that's random, baby.

    I wouldn't buy life insurance in the mean time, however.

  • CoyneT (unregistered) in reply to Thief^

    Pseudo-randomization has all kinds of nasty effects and pitfalls if you know where to look for them.

    Suppose you have 1,000,000 objects and want to select one at random. Try this?

      n = int(rand() * 1,000,0000) + 1

    Nope. Most (non-cryptographic) random number generators can produce 32,767 or 65,535 distinct random numbers. So (assuming the larger number) there are 65,535 of the 1,000,000 objects this can select randomly and the remaining 934,465 can never be selected, no matter how many times you try.

    Okay, so try?

      n1 = int(rand() * 1,000)
  n2 = int(rand() * 1,000)
  n = n1 * 1000 + n2 + 1

    Nope. Pseudo-random numbers chain. That is:

      seed0 --> random1,seed1
  seed1 --> random2,seed2
  seed2 --> random3,seed3
  seed3 --> random4,seed4
    ...and so on.

    So if the generator offers 65,535 different distinct values, that means that each of the n1 values is selected by one of about 65 distinct rand() results (because of 65,536/1000). Since the random that generates n2 is a direct consequence of the random that generated n1, if there were 65 values that can select a given n1 then there are exactly 65 values that will be returned for the succeeding n2. Or, restated, are 935 of 1,000 values of n2 that aren't possible for that given value of n1.

    I've been chasing this because I'm looking for an algorithm to select jurors...from a very large pool (1 million+). Either of the above approaches would mean a lot of citizens get called repeatedly and a lot can never be called, which is really undesirable behavior. (This second attempt is actually just as bad as the first attempt.)

    One approach that works (need 150 jurors from 1,000,000 citizens):

      randomize;

  for i = 1 to 150
     citizen[i] = int(rand() * 1000)
  next i

  randomize;

  for i = 1 to 150
     citizen[i] = citizen[i] * 1000 + int(rand() * 1000) + 1
  next i

    But, no doubt, a quite a few programmers reading this would think it was a WTF.

  • (cs) in reply to Rishu73
    Rishu73:
    Why not just do the following:

    1d% A dice roller bubble from the Trouble board game A web cam mounted above so the dice can be read A dice recognition program done by my boss' 15-year old nephew done by Excel VBA.

    I think that is an adequately WTFed solution.

    Hopelessly inadequate, I'm afraid. No wooden table, no Irish Girl, not even a Cthulhu. XML would help, if only because, although it won't increase the entropy, it will most certainly feel like it.

    For a secure randomiser, you would also need a Faraday cage. We haven't covered this topic yet (it may well be due in the next semeseter), but I believe the easy-to-follow, WTF-proof instructions to do so are as follows:

    (a) Take one Faraday. (b) Make a cage out of it. (c) ??? (d) Paula!!!!

  • Jeltz (unregistered)

    I see many mentioning the mersenne twister but forgetting to mention that it should not be used in cryptography. Sure it is fast and has good randomness but it is not secure.

    Which PRNG you should use depends on the application.

    But what you never should do is try to add entropy to an already existing algorithm. It does not work. Inventing or modifying algorthms to make them better is hard. Either you get the same entropy or worse.

  • Pseudo-Bovine (unregistered) in reply to Anonymous Cow-Herd
    Anonymous Cow-Herd:
    According to Debian, there are only 32766 random numbers.

    I'd say there's only one random number - but it changes every time you look at it.

  • (cs) in reply to Pseudo-Bovine
    Pseudo-Bovine:
    Anonymous Cow-Herd:
    According to Debian, there are only 32766 random numbers.

    I'd say there's only one random number - but it changes every time you look at it.

    Not truly random, then, is it?

  • hi (unregistered) in reply to Thief^
    Thief^:
    take a 1024 element array of numbers and use the value from shitty-prng to step through it (using that primes trick to make sure that you go through all the numbers no matter what the step number is).

    Which primes trick? Can somebody explain it please?

  • (cs) in reply to real_aardvark
    real_aardvark:
    Pseudo-Bovine:
    Anonymous Cow-Herd:
    According to Debian, there are only 32766 random numbers.

    I'd say there's only one random number - but it changes every time you look at it.

    Not truly random, then, is it?
    According to the many-worlds model of quantum physics, there exists a universe in which you got the joke.

  • (cs)

    Actually pseudo-randomizing a pseudo-randomizer does increase randomness (as defined by tests of randomness of a pseudo-random sequence, for example correlation of subsequent random numbers etc.) by using algorith invented by Ulam (if I remember correctly) for Manhattan Project: fission simulations, namely having small array of pseudo-random numbers, and using second random number generator to choose an element of this array (and first random number generator to fill the item we did empty). And I think that can be proven mathematically.

  • Steve (unregistered)

    int RandomNumberBetweenOneAndOneInclusive() { return 1; }

  • VoiceOfUnreason (unregistered)

    Heads!

  • (cs) in reply to Pseudo-Bovine
    Pseudo-Bovine:
    Anonymous Cow-Herd:
    According to Debian, there are only 32766 random numbers.

    I'd say there's only one random number - but it changes every time you look at it.

    Schrödinger's cat is my RNG's input. Not just true randomness, its quantum randomness!!!

  • Michael Spencer (unregistered) in reply to CoyneT
    CoyneT:
    ... Suppose you have 1,000,000 objects and want to select one at random. Try this? 
      n = int(rand() * 1,000,0000) + 1

    Nope. ...

    Correct.

    CoyneT:
    ... One approach that works (need 150 jurors from 1,000,000 citizens): ...

    Assuming DISTINCT_VALUES = 65,536

    The major and obvious problem with this is that the resulting indices would have a range of [1, (RAND_MAX * 1000 * 1000) + (RAND_MAX * 1000) + 1]. Which on my machine (besides being an integer overflow) is... 2,149,631,130,647,001. Additionally, you still only have two meaningful calls to rand. Thus only DISTINCT_VALUES * 2 out of 1,000,000 can be selected.

    Now the proper way would be (assuming real numbers converted to an int at the end).

    rand_calls = 1,000,000 / DISTINCT_VALUES;
max = RAND_MAX * rand_calls;
index = 0;
for(int i = 0; i < rand_calls; ++i)
    index += rand();
index /= (max / 1,000,000); // Shift back to [0, 1,000,000].

    Not only can this get every index. It also has no more bias than created from the original rand function.

    (Beware of bugs in the above code. Not only have I not proven it correct, but I'ave yet to even test it :P).

  • more randomer than you (unregistered) in reply to Mee
    Mee:
    donniel:
    TheRider:
    Bernie:
    Cloud computing sounds random to me; we should obviously hit the network whenever we need a random value.
    Now you're talking. Hit Google with a random query and hash the results html page. This should give you a truly random number.

    Where do you get the query from? Obviously it has to be a dictionary word, since nonsense will always fetch the same result page (No results found).

    Then you'll have to account for events like network or service outages...

    ...Or maybe you were kidding...

    At a minimum, the page will always be different because it includes your original string in the "No Results Found for X" - so it will always be slightly different, which should make a difference when hashed.

    Or maybe you were kidding too.

    So, you generate a random string, enter this into google and hash the result.

    99.9% of the time, your random string will be something which returns no reults. Hence, your "random generator" will almost always be ouputting a value based on the hash of the random string you created. Hence, the strength of your generator is only as strong as the strength of whatever you use to create the random string.

    What were you hoping to achieve? May as well have just said "pick a random number and add 10"

  • Lynn (unregistered) in reply to Thief^

    Whatever you do, don't try to make a prng of your own without a degree in number theory.

    Or, an external entropy source like a thermometer with a high degree of accuracy (8-10 decimal places should do) that you can chop some numbers off of the front of and use as a seed....

    -- Captcha (how fitting): damnum (heh)

  • Medicine Storm (unregistered)

    So... we need a USB device that contains a small quantity of a radioactive isotope that generates random numbers based on particle decay.

  • (cs)

    Nahhh, all we need is a small physics simulation of rolling a cube and coming up with which side faces up...

  • Tepsifüles (unregistered) in reply to Michael Spencer
    Michael Spencer:
    Not only can this get every index. It also has no more bias than created from the original rand function.

    (Beware of bugs in the above code. Not only have I not proven it correct, but I'ave yet to even test it :P).

    Seeing how you are scaling an asymptotically normal distribution, I'd say it has far more bias towards the middle range of its possible values than rand() does ;)

    smasher:
    Statistical analysis will tell you how *evenly deistributed* the results are, but can it tell you whether the process deterministic or non-deterministic?

    An algorithm that produces the same 3000 even distributed integers every time is not what we're looking for.

    If you are generating your random numbers by an algorithm (and have no "true" entropy source), that's by definition deterministic. What you probably meant is an algorithm that just caches the previous returned value and returns a function thereof; this kind of thing can do well on the simple checks, but the distribution of consecutive value pairs is about the worst one can get, so statistical analysis picks it up easily.

    In conclusion, I'd like to echo the sentiment mentioned above a couple of times: friends don't let friends roll their own PRNG. Only you can stop the WTFs!

  • Eskil (unregistered) in reply to CoyneT
    CoyneT:
    Pseudo-randomization has all kinds of nasty effects and pitfalls if you know where to look for them.

    Suppose you have 1,000,000 objects and want to select one at random. Try this?

      n = int(rand() * 1,000,0000) + 1

    and so on...

    Isn't this why the man page on many systems says ;

    In Numerical Recipes in C: The Art of Scientific Computing (William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling; New York: Cambridge University Press, 1992 (2nd ed., p. 277)), the following comments are made: 
           "If you want to generate a random integer between 1 and 10, you should always do it by using high-order bits, as in

           j = 1 + (int) (10.0 * (rand() / (RAND_MAX + 1.0)));

       and never by anything resembling

           j = 1 + (rand() % 10);

       (which uses lower-order bits)."

   Random-number  generation is a complex topic.  The Numerical Recipes in C book (see reference above) provides an excellent discussion of practical random-number generation  issues in Chapter 7 (Random Numbers).

   For  a  more  theoretical discussion which also covers many practical issues in depth, see Chapter 3 (Random Numbers) in Donald E. Knuth’s The Art of Computer Programming, volume  2 (Seminumerical  Algorithms),  2nd  ed.;  Reading, Massachusetts: Addison-Wesley Publishing Company, 1981.

Leave a comment on “More Entropy, Please”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article