• Tuxo (unregistered)
    TheRaider:
    Does a higher entropy mean more ordered? or less ordered?
    Entropy not always means "order", it could be information distribution.
    Brompot:
    The interesting thing is, if you give it the same seed, it will produce the same 'random' number each time. Now for a randomizer for the seed ;-)
    smasher:
    Statistical analysis will tell you how *evenly deistributed* the results are, but can it tell you whether the process deterministic or non-deterministic?

    When doing numerical simulations for some systems, and using perturbation theory it is important to be able to repeat some calculations with slightly different initial conditions, therefore we need the same random series. Another fact is the impossibility to have a true random number generator due to the computer deterministic nature.

    What it is very important to understand is that from physics point of view random and chaos are not the same, that is why we talk about "deterministic chaos", meaning we can repeat simulations and get the same results. There are methods that allow us to cope with limited PRNG.

    A similar missconception arises when people uses to say a double precision number is a real number. It is a good approximation to a real number. For the same reason it is impossible to have irrational numbers.

    On the other hand, quantum systems appears to be chaotic (that is one way how we have quantum chaos), even it is possible to use some techniques from classical caos for analysing quantum systems, but under certain circumstances, while classical systems get stable, quantum systems remain chaotic, that means quantum effects are stronger than random effects, therefore quantum chaos in fact does not exist in the same sense as classical chaos.

    Quantum systems appears to be nondeterministic, therefore the importance for the existence of a quantum computer (among other factors like world domination). There is a caveat: quantum systems can exist only on well defined states (that is why we talk about discrete energy spectrum), so if you measure it, it will aquire a valid state.

  • phx (unregistered)

    I see your lack of entropy and raise you:

    When faced with the (apparant) need to generate a unique message ID, the developer of a custom (for "performance") messaging system at work decided that a PRNG wouldn't be enough. We needed to use the crytographically strong RNG!

    Of course this eventually drained the Windows entropy pool until getting the next random number blocked, for hilarious results.

  • 35% Genius (unregistered) in reply to Dan
    Dan:
    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.

    http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

    If you shuffle the total list beforehand every song will only play once.

  • (cs) in reply to jkupski
    jkupski:
    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. :)
    At last a kindred spirit! Do your colleagues look at you askance when you say this, as mine do, or am I just unlucky with my not-quite-peers?
  • pedant (unregistered) in reply to Randy Waterhouse
    Randy Waterhouse:
    EAGCI CAQCK HYCUC PEXBU BXIUK GJRGT KKTRN CUNSW YAVBV YQZWS UYPCS AJCRP VCAPT NROBK KALGB GESGA KAYAC RAMUS CQUCF OPXCR HNSST TZXMF YXFXY IOYUI RWYLZ EZPBC GJPYC JSBHF GFCMC AURZP AQMZC LDCAF EHOUG REZSL EZRGL UHFLG VMXHL ZTPBT VGBKA HBEGT QLSHS EBZJN GEZEM LDFAF ZWLAG MIHRO BHAUP SYQSI EZMDD YOHEP MDLYD SKLZC ABKAV ZTUQL CUKPY NONVS DHVPF ZHQKH TLIDM EDFZU QBPBR NPFBK XESTT YSAPD IIPQL BVPGU JXWYZ NMOSN ZQRRK LQDMF HUNWL ZXGOE BYBYW ALJPE WOVOG GZWJL BRGPO ROLYD QABSY YSKII PEXKT DRTAB FBSLQ GCFSB IIBKA AJTKR CZWZK PCBIC CNEVZ VBBAT DJCEU CFEWP VYPSX AIABQ DEEIZ DDAFE UIOWN IZTNW IIUYB SYJTA AWEEF DIIEO NYWBV KKVDX RMGML IFKRZ KRWOW BREKV SXUPZ PAKLE IDRPQ CXVMO UXGQL CSDHC YAATQ ZJRKU VSXNH NQFJC UEZAV LDNOL QNLQG BPPTZ KOSHB ZVSFF UZKUZ FGDTU OJHZZ OBPEU POJHW LHSDM XYLHT LNZOG UCQCC QQEFU ZVJIC FUKXY WVWID QTQPI XJLOL NECSK XRFGA ILUSJ TPEQX HGRYW ZWGKK SYOUR YRIEX IMJDE SXTXN RETID PIZVT JNRYI IXARB XAOHE SABMX OEBIM FYVET OOHGM PPKPG LNHAV LTVNG SCKUK XZISE CGSKM FABQQ ICEPC ZBVVO BNQLI BIIKB NMHGW ULWVB NEERT GQUBL JCZZO IBXQL YDXFJ UAVRW XEABV UHMPJ YYMXY AFZYW LWZIC JDCFV YDAYE VTMII WGGID FJJEH FPDFY GPCIU YGXYF CUYPC HLJNT NSDWX KCNOH MUXPC RNJPL PSFOH IVSRJ MECPB AADNO

    That's easy for you to say...

  • baronzemm (unregistered) in reply to Thief^

    At a company I worked at we decided that the best way to get good entropy would be to just hook up those motion capture balls to the intern and record the results all day every day... the intern... aka.. me.

  • DKO (unregistered) in reply to Vanders
    Vanders:
    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.

    The ISO 9899:1999 standard suggests a simple linear congruential generator in case you are not able to create your own PRNG:

    // RAND_MAX assumed to be 32767
int rand(void)
{
      next = next * 1103515245 + 12345;
      return (unsigned int)(next/65536) % 32768;
}

    According to Wikipedia this is used by a few platforms; but others usually change some constants.

  • DKO (unregistered) in reply to CoyneT
    CoyneT:
    I've been chasing this because I'm looking for an algorithm to select jurors...

    For anything but toy programs you need a real PSRN. Like Boost.Random. You shouldn't expect the standard library to be able to tackle everything.

    See http://www.boost.org/doc/libs/1_35_0/libs/random/random-generators.html. There's also a class for true random numbers, that feeds from /dev/urandom, /dev/random, or whatever you have to feed it with real entropy.

  • Engywuck (unregistered) in reply to CoyneT

    I probably would have done something like the following

    MAXRAND := 65536;

    num_cit := get_number_of_citizens_from_somewhere();

    bucket_size := Ceil(num_cit / MAXRAND);

    choose_bucket := random(num_cit/bucket_size);

    choose_person_in_bucket := choose_bucket*bucket_size+random(bucket_size);

    (do you notice I haven't programmed in a while? ;-) So please shout WTF when you read an error )

    If you have to choose from more than MAXRAND*MAXRAND than you'd need a second recursion of course... but I somewhat doubt that you need to choose jurors out of the whole world population :)

  • (cs) in reply to hi
    hi:
    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?

    It's something like taking the current index, adding 1 to it, multiplying it by a seed number (between 1 (inclusive) and the higher prime I mention below (not inclusive)), multiplying that by a prime number below the size of the array, wrapping it by a prime above the size of the array, then subtracting 1. Repeating the process if outside the bounds of the array. Because the primes aren't factors of each other it has to step through every index. It is essentially a pseudo-random number generator that generates numbers in the range 0 to high prime - 2. e.g. for a 10 element array, starting at index 0, step seed = 4, low prime = 7, high prime = 11: (0+1)47 = 28, % 11 = 6, - 1 = 5 (5+1)47 = 168, % 11 = 3, - 1 = 2 (2+1)47 = 84, % 11 = 7, - 1 = 6 (6+1)47 = 196, % 11 = 9, - 1 = 8 (8+1)47 = 252, % 11 = 10, - 1 = 9 (9+1)47 = 280, % 11 = 5, - 1 = 4 (4+1)47 = 140, % 11 = 8, - 1 = 7 (7+1)47 = 224, % 11 = 4, - 1 = 3 (3+1)47 = 112, % 11 = 2, - 1 = 1 (1+1)47 = 56, % 11 = 1, - 1 = 0 A version of this with two very large prime numbers is what powers most implementations of C++'s rand(). Though they usually use the seed you give them as the initial index, and leave off what I've called the seed here. That means that C++'s rand generates the exact same sequence every time, the seed just makes it start at a different point. They often use a 32-bit number internally and only return 16 bits of it to make it look more random.

    Essentially you'd be using another (really simple) random number generator over the top to cover up the flaw in the "42" one I described.

    Addendum (2008-08-12 09:43): Actually, I don't think there is any real limit on what prime is used for what I called the "low prime", as long as it isn't really tiny and isn't the same as what I called the "high prime". It can safely be larger.

  • (cs) in reply to SenTree
    SenTree:
    jkupski:
    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. :)
    At last a kindred spirit! Do your colleagues look at you askance when you say this, as mine do, or am I just unlucky with my not-quite-peers?
    "Six by Nine? Forty-two? ... I always said there was something fundamentally wrong with the universe..."

    You need better peers, obviously ;^)

  • Rushyo (unregistered)

    rand(rand(rand(rand(rand(rand(rand(rand(rand(rand(rand()*rand()+rand(rand()-rand())))))))))))

  • SQL Ninja (unregistered) in reply to Vollhorst

    Hay guyz, am I too late for the XKCD reference?

  • Onni (unregistered)

    (rand() & 16)

    WTF?

    Doesn't that return 16 or 0?

  • adriyel (unregistered)

    I'd just like to comment that true randomness isn't possible physically, literally, or computationally.

    Just saying. You can achieve 'effective' randomness "for your purposes", but there's no actual such thing.

  • smasher (unregistered) in reply to Tepsifüles
    Tepsifüles:
    smasher:
    Statistical analysis will tell you how *evenly distributed* 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!

    Yes, the orginal question I replied to was about whether the result of the next roll could be guessed by looking at the results of previous rolls. That's not a problem with distribution or results - it's a problem with determinism and lack of entropy. Other posters suggested getting real entropy using temperature-sensitve resistors or radioactive decay.

    This problem crops up in crypto, but also in gambling machines. I remember a news story about a Keno machine at a casino that was being shut down every night, and restarted ever morning; whereupon it would give the same set of numbers that it gave the day before. Eventually the casino noticed, but not before some patrons took advantage of the pattern.

    That's a WTF indeed, and a worse one that the original post. The author of that code (or the library used) was apparently seeding with the current time since power on, which was always the same since the time it took for the machine to boot was constant! (Seeding with "time since Jan 1 1970" would have helped, if the system knows the current date. Not all embedded systems do. Even better, a simple "press button A to continue" before seeding would have made the machine less predictable! )

  • Roger Wolff (unregistered) in reply to Grimoire
    Grimoire:
    If you want something better, either implement your own (such as the previously mentioned Mersenne Twister) or use the OS supplied crypto quality PRNG.
    Read "the art of computer programming" by Donald Knuth. IIRC, volume 2, chapter 3.

    Implement your own is strongly advised against.

  • Multiple Times Randomer (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 :)
    Then try result = rand() << 32; ;-)
  • CoyneT (unregistered) in reply to Michael Spencer
    CoyneT:
    ... One approach that works (need 150 jurors from 1,000,000 citizens): ...
    Michael Spencer:
    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).

    Yes, this should work as well. I agree that the bias should disappear. Clever.

  • CoyneT (unregistered) in reply to Eskil
    Eskil:
    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

    Most of the random generators I have used return numbers in the range [0 <= rand() < 1]. When using the method I used, rand() * 10 yields [0.0 <= (rand() * 10) < 10.0]. At this point, the number is real, with the lower order bits as fractional. Taking the integer of this, in effect, "clips off" the low-order bits, meeting the requirement above.

    The problem I was discussion arises only because, despite the float range, there are still only 32,767 or 65,536 distinct float values that can be returned, so that if the multiplier is large, values get skipped at semi-regular intervals. Especially if the multiplier is larger than the distinct value set.

  • CoyneT (unregistered) in reply to Engywuck
    Engywuck:
    I probably would have done something like the following

    MAXRAND := 65536;

    num_cit := get_number_of_citizens_from_somewhere();

    bucket_size := Ceil(num_cit / MAXRAND);

    choose_bucket := random(num_cit/bucket_size);

    choose_person_in_bucket := choose_bucket*bucket_size+random(bucket_size);

    (do you notice I haven't programmed in a while? ;-) So please shout WTF when you read an error )

    If you have to choose from more than MAXRAND*MAXRAND than you'd need a second recursion of course... but I somewhat doubt that you need to choose jurors out of the whole world population :)

    This falls afoul of the same problem as rolling two dice together and counting the spots. Statistically, for the dice, getting exactly 7 spots is 12 times as likely as getting 2 spots or 12 spots. Over a large number of rolls, the spots form a nice bell curve.

    So the above would tend to choose jurors in the range surrounding the halfway mark (500,000 in the range of 1 to 1,000,000) much more often than those near 1 or 1,000,000; which would be undesirable.

  • Paul Koning (unregistered)

    This is a joke, right?

    Because clearly the premise in the article is complete nonsense. The output of a PRNG is predictable; the output of nested PRNGs is EXACTLY as predictable as the output of a single one. The entropy of either approach is zero.

    As Knuth points out (in Volume Two): "Random numbers should not be generated with a method chosen at random" -- such as the one described in this article.

    For those who want to read a technically sound discussion of random numbers and how to generate them, go read RFC 1750

  • (cs)

    I once discovered the following code to create a checksum based upon a string value:

    function CalculateCRC(const GUIDStr: string): string; var I: Integer; CRC: LongInt; begin CRC := 0; for I := 1 to Length(GUIDStr) do if (GUIDStr[I] in ['0'..'9']) then CRC := CRC + (Ord(GUIDStr[I]) * 256 + 5); Result := IntToHex(CRC, 5); end;

    The purpose of this code was to create an unique value by calculating a checksum over some random string value. Of course, a GUID was used to create this random string that could be used as identifier and of course it only calculates with the numbers inside this GUID. Fortunately, it was made more unique again by appending the result of this function to the original GUID and then another checksum routine is used to calculate a second CRC. Finally the code that uses this "unique" CRC also used a timestamp to make it a bit more unique. Appending year, month, day, hours, minutes, seconds and milliseconds and there you are, with a nice and unique value...

    Yeah, I've suggested to replace it with just a GUID and they looked at me as cows look at oncoming trains...

  • Monkey Brains (unregistered) in reply to Dan
    Dan:
    Seriously though, I still have yet to find a satisfying randomizer. Even for the simple task of randomly choosing a song to play...

    We have an old saying from the country I'm from. If you're going to try to bang in screws with lots of different kinds of plyers, don't blame the plyers.

  • Kahawe Dawnstrider (unregistered) in reply to Thief^

    Yea, or you could just make it really really super ueber OMFG NO WAI lolcats random: http://random.org/

  • Dave (unregistered) in reply to more randomer than you

    Don't search for a random string. Just search for "marf" and pick a random word from the search results. Then search for that, if you want. The more searches you do, the more the fluctuations in the internet will improve on your entroy.

  • Frank Shook (unregistered)

    I'm not sure why this is such an issue.

    Worthwhile randomizers expect a 'seed'. Give it something different every time, and you'll get something fairly random. Try current time or maybe system clock ticks (UNIX and variants can provide this as an integer). On multiple random draws, wait a little while between seeds.

  • Frank Shook (unregistered)

    Almost forgot.

    For all you random number purists, check out http://www.lavarnd.com/

    I've noticed that the random Corporate Memo generator at http://www.lavarnd.com/cgi-bin/corpspeak.cgi does a scary job of emulating upper-echelon fatheads.

  • Engywuck (unregistered) in reply to CoyneT
    CoyneT:
    Engywuck:
    I probably would have done something like the following

    MAXRAND := 65536;

    num_cit := get_number_of_citizens_from_somewhere();

    bucket_size := Ceil(num_cit / MAXRAND);

    choose_bucket := random(num_cit/bucket_size);

    choose_person_in_bucket := choose_bucket*bucket_size+random(bucket_size);

    (do you notice I haven't programmed in a while? ;-) So please shout WTF when you read an error )

    If you have to choose from more than MAXRAND*MAXRAND than you'd need a second recursion of course... but I somewhat doubt that you need to choose jurors out of the whole world population :)

    This falls afoul of the same problem as rolling two dice together and counting the spots. Statistically, for the dice, getting exactly 7 spots is 12 times as likely as getting 2 spots or 12 spots. Over a large number of rolls, the spots form a nice bell curve.

    So the above would tend to choose jurors in the range surrounding the halfway mark (500,000 in the range of 1 to 1,000,000) much more often than those near 1 or 1,000,000; which would be undesirable.

    well, I thought the above code would remedy that by first choosing a "container" with several people in it and then one out of these. So the first random number chooses a bucket, the second chooses in the bucket...

    My last line choose_person_in_bucket := choose_bucket*bucket_size+random(bucket_size); just returns the "number" of the person chosen.

    Perhaps I write a small simulation tomorrow...

  • Engywuck (unregistered) in reply to Engywuck

    hmmm, how fast "tomorrow" comes ;-) my code gives the expected result:

    Implementation in freepascal:

    USES crt,math;

    CONST MAXRAND = 16; num_cit = 64; num_runs = 1000000;

    VAR bucket_size, chosen_bucket, chosen_person : word; results : ARRAY[1..num_cit] of Cardinal; i : Cardinal;

    begin randomize; bucket_size := ceil(num_cit / MAXRAND); for i:=1 to num_cit do results[i]:=0; for i:=1 to num_runs do begin chosen_bucket := random(ceil(num_cit/bucket_size)); chosen_person := chosen_bucket*bucket_size+random(bucket_size)+1; Inc(results[chosen_person]); end; for i:=1 to num_cit do write(results[i],' '); end.

    Result: 15746 15527 15417 15536 15648 15609 15796 15464 15485 15537 15449 15687 15778 15933 15790 15631 15693 15651 15592 15751 15629 15745 15632 15568 15649 16022 15558 15685 15570 15544 15674 15453 15472 15636 15599 15565 15785 15229 15444 15641 15888 15305 15537 15784 15682 15491 15604 15460 15702 15632 15815 15721 15638 15706 15672 15709 15606 15563 15582 15564 15555 15630 15713 15621

    Looks somewhat equal-distributed to me :)

    And now it's 5:25 AM... time to watch some anime, then go to sleep :)

  • (cs) in reply to JimM
    JimM:
    SenTree:
    jkupski:
    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. :)
    At last a kindred spirit! Do your colleagues look at you askance when you say this, as mine do, or am I just unlucky with my not-quite-peers?
    "Six by Nine? Forty-two? ... I always said there was something fundamentally wrong with the universe..."

    You need better peers, obviously ;^)

    My point exactly. Most of them get the H2G2 reference (except the younger ones), but the base-13 solution generally needs explaining. ;^(

  • Shinobu (unregistered)

    Old Slashdot post, but so on topic: Debian Bug Leaves Private SSL/SSH Keys Guessable Debian package maintainers tend to very often modify the source code of the package they are maintaining so that it better fits into the distribution itself. However, most of the time, their changes are not sent back to upstream for validation, which might cause some tension between upstream developers and Debian packagers. Today, a critical security advisory has been released: a Debian packager modified the source code of OpenSSL back in 2006 so as to remove the seeding of OpenSSL random number generator, which in turns makes cryptographic key material generated on a Debian system guessable. The solution? Upgrade OpenSSL and re-generate all your SSH and SSL keys. This problem not only affects Debian, but also all its derivatives, such as Ubuntu.

  • Engywuck (unregistered) in reply to Shinobu
    Shinobu:
    Old Slashdot post, but so on topic: Debian Bug Leaves Private SSL/SSH Keys Guessable Debian package maintainers tend to very often modify the source code of the package they are maintaining so that it better fits into the distribution itself. However, most of the time, their changes are not sent back to upstream for validation,

    If you followed this bug closely you'd have noticed that the debian developer making the faulty change asked in upstreams developer mailing list if this was OK and got some vague "yes, do so if it helps with debugging"... When mentioning this upstream the reaction was something like "what? this is not a mailing list our developers regularly read despite having -devel name and mentioning this would be the right place in the dosumentation... you should have asked elsewhere... and besides, that a person still now in the devel team told you so doesn't mean it's OK"

  • MattF (unregistered)

    Knuth's Comment: Do not select random number generating algorithms at random.

  • Lorum (unregistered) in reply to Vanders
    Vanders:
    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.

    ISO C states that using the same seed, rand() must always give the same sequence. Thus you can't make it provide good randomness, as it must be reproducible.

  • Some Art Guy (unregistered) in reply to Janis

    I'm not a programmer, so maybe I'm the WTF here, but that looks wrong to my untrained eyes. Wouldn't that algorithm bias you severely to the upper half of your numbers?

    I'm looking at that, and it seems that only 1 out of however many random numbers you can get would you ever get a number below half.

    Wouldn't you want to weave the bits together or something odd like that?

  • Engywuck (unregistered) in reply to Lorum
    Lorum:
    Vanders:
    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.

    ISO C states that using the same seed, rand() must always give the same sequence. Thus you can't make it provide good randomness, as it must be reproducible.

    Every PRNG (Pseudo-RNG) automatically has this property...

    Wikipedia (yeah, I know... biggest trash dump of the human mind ever...) says: "A PRNG can be started from an arbitrary starting state, using a seed state. It will always produce the same sequence thereafter when initialized with that state. The maximum length of the sequence before it begins to repeat is determined by the size of the state, measured in bits." (http://en.wikipedia.org/wiki/Pseudorandom_number_generator)

  • Lorum (unregistered) in reply to Engywuck
    Engywuck:
    Lorum:
    Vanders:
    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.

    ISO C states that using the same seed, rand() must always give the same sequence. Thus you can't make it provide good randomness, as it must be reproducible.

    Every PRNG (Pseudo-RNG) automatically has this property...

    Wikipedia (yeah, I know... biggest trash dump of the human mind ever...) says: "A PRNG can be started from an arbitrary starting state, using a seed state. It will always produce the same sequence thereafter when initialized with that state. The maximum length of the sequence before it begins to repeat is determined by the size of the state, measured in bits." (http://en.wikipedia.org/wiki/Pseudorandom_number_generator)

    You could get more entropy inside the rand() call by counting the number of change since last call, multiply by the number of process in the system and add the lower bits of the nanosecond count. (or just read /dev/random into it)

    The point is, it's still not random, but you would need to know the system state on each call, past and future to predict the next random number, as opposed to just discover the seed/internal state.

  • Neil Ferguson (unregistered)

    Compile this program in MS C++ version 13.00.9466:

    #include <stdio.h> #include <stdlib.h>

    int main() { int ix; for (ix = 0; ix < 100; ++ix) { srand(ix); printf("Called srand(%d): rand() = %d\n", ix, rand()); } return 0; }

    You get: Called srand(0): rand() = 38 Called srand(1): rand() = 41 Called srand(2): rand() = 45 Called srand(3): rand() = 48 Called srand(4): rand() = 51 Called srand(5): rand() = 54 Called srand(6): rand() = 58 Called srand(7): rand() = 61 Called srand(8): rand() = 64 Called srand(9): rand() = 68 Called srand(10): rand() = 71 Called srand(11): rand() = 74 etc.

    That doesn't seem right to me.

  • Lorum (unregistered) in reply to Neil Ferguson
    Neil Ferguson:
    Compile this program in MS C++ version 13.00.9466:

    That doesn't seem right to me.

    Seems they haven't changed the algorithm too much over time, since msvcrt.dll gives the same values.

    msvcrt.dll random algorithm is: signed long int rand_value; void srand(unsigned int seeed) { rand_value = seed; }

    int rand(void) { rand_value = rand_value*0x343FD + 0x269EC3; return (rand_value >> 16) & RAND_MAX; }

    (Additionally, its version is thread-safe by having rand_value into thread storage).

  • OBloodyhell (unregistered)

    As a dinosaur, I do recall the days when you really, truly could not trust the rand functions from, say, Applesoft Basic on the Apple ][, and thus implemented algorithms which were taught in classes for doing such (yes, they used to teach us how to do it).

    Being sensible, I always generated a Chi-Squared test with that to verify that it was doing what I expected it to be doing... but I did another test, which was suggested somewhere, and struck me as pretty effective -- it once showed a flaw which the Chi-Squared test hadn't caught.

    A visual test: Whatever the rez of your screen was, generate a pair of numbers within those bounds and plot a point. Repeat ad nauseum. With those old 1 mega hertz and less processors, this actually took time, so you would run it and just look up once in a while. If there was a real flaw in the generator, it usually would show up as a "hole" (or, alternately, an "organization", like a striping pattern) in the screen thus generated. A properly functioning RNG would look like static, and show no favorite areas... Ideally, if the system in question allowed you to read the color of an existing pixel, you could also add a third dimension to the test and increment the color so areas would shade differently, with hot spots being a sign of failure just like holes.

  • pieter (unregistered)

    Also, rand() & 16, a bitwise operation, can only evaluate to 0 or 16, since 16 = 0b10000.

  • nos (unregistered)

    Actually the worst failure of this snippet is it calls srand. You're pretty much bypassing the algorithm if you call srand everytime you want a random number.

  • Arua ROSE zuly (unregistered)

    Arua ROSE zuly is used to upgrade experience, you can point him food to plus use of blood is do not rose online zuly, more a task bar to complete the task can be a lot of rose online zulie subsidies and experience points, as long as the spend Rose zuly bought some food to the blood of drugs sufficient to meet those Xiaoguai. To transfer the time to consider a good career you want to turn, attribute point will come to Canada based on your job and your rose zulie.

  • Noah Body (unregistered)

    I was once forced into introducing a "better" random number generator than the "pseudo" random method of using rand and srand, as the unique identifier for DB tables. (Really, really stupid idea.)

    So, I dazzled them with my "BS" in Engr., a literally duct taped together copy of a college Calculus book, that included graphs of sinh and cosh. I fed these as the seed to srand with the current system time, and voila, came up with a "new" random number generator.

    So, being the early '90s, I named the algorithm, TAFKAP and the correlary algorithm TAFKAV.

    Those stand for the "The Artist Formerly Known As Prince", Sign(h) of the Time? And the "Artist Formerly Known As Vanity.

    About a year later, while working for a different job in the same company, I was asked to review some code from the previous project and found that not surprisingly, the unique id's were still not enough, so the new coder added a for loop to try seeding srand 10 times.

Leave a comment on “More Entropy, Please”

Log In or post as a guest

Replying to comment #:

Log Out

« Return to Article