Thread: random isn't really random?

  1. #61
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by shawnt View Post
    As for the original question that got me posting in this thread in the first place, i.e. whether or not calling srand() for each rand() in a loop actually DECREASEs randomness (lets now define that as decreasing the likelihood of each term of a distribution having equal probability of occurance; thats what i've been after all along), I think I will take your advice and do my own research into it, as I haven't gotten very convincing answers on that here. Would you like to chime in on this?
    If you look at the implementation posted by Elysia,
    Code:
            _ptiddata ptd = _getptd();
            return( ((ptd->_holdrand = ptd->_holdrand * 214013L
                + 2531011L) >> 16) & 0x7fff );
    and consider that srand() [in essence if not in fact] sets _holdrand to the value you pass in, then you'll see that it's perfectly possible to predict the outcome of the random number.

    So if you pass in a constant to srand(), you will get a constant value out every time. If you can provide a good random number as input, then it will provide a different number than the input, but directly related and predictable if we know the original number.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  2. #62
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Implementation of srand:
    Code:
    void __cdecl srand (
            unsigned int seed
            )
    {
            _getptd()->_holdrand = (unsigned long)seed;
    }
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #63
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by jEssYcAt View Post
    For a statistical simulation, it is more important that the distribution be even. An even distribution means that any given number in the range is as likely to be generated as any other given number in that range.
    Uniformity is important but obviously it's not the whole story. You can produce a perfectly uniform sequence of "random" values in the range [0, N] by simply generating 1, 2, 3, ..., N over and over again.

    I agree that MT is probably the best general choice. Seed it once using some entropy from somewhere (/dev/random on UNIX is a good choice) then forget about it.

  4. #64
    Registered User
    Join Date
    May 2008
    Posts
    81
    Quote Originally Posted by matsp View Post
    If you look at the implementation posted by Elysia,
    Code:
            _ptiddata ptd = _getptd();
            return( ((ptd->_holdrand = ptd->_holdrand * 214013L
                + 2531011L) >> 16) & 0x7fff );
    and consider that srand() [in essence if not in fact] sets _holdrand to the value you pass in, then you'll see that it's perfectly possible to predict the outcome of the random number.

    So if you pass in a constant to srand(), you will get a constant value out every time. If you can provide a good random number as input, then it will provide a different number than the input, but directly related and predictable if we know the original number.

    --
    Mats
    good point.

    i guess I should have clarified that I was unsure how seeding srand() with a 'random number' multiple times ( = 1 srand(RANDOM_NUMBER) per rand) would be less random than using the RANDOM_NUMBER by itself.

  5. #65
    Registered User
    Join Date
    May 2008
    Posts
    81
    Quote Originally Posted by brewbuck View Post
    Uniformity is important but obviously it's not the whole story. You can produce a perfectly uniform sequence of "random" values in the range [0, N] by simply generating 1, 2, 3, ..., N over and over again.

    I agree that MT is probably the best general choice. Seed it once using some entropy from somewhere (/dev/random on UNIX is a good choice) then forget about it.
    another great point. apparantly, non-sequential order is another criteria. I'm pretty sure that the probability of obtaining a successive sequence in any random distribution is demonstrably lower than that of any random element.

    of course, this brings up the question as to which sequences exactly would be subjected to lower probablity. what are the odds of getting something like fibonacci's series? how about a sequence where the elements are linked by a highly esoteric function? but that would be subject for another forum

  6. #66
    The larch
    Join Date
    May 2006
    Posts
    3,573
    how about a sequence where the elements are linked by a highly esoteric function?
    Isn't this what PRNG is all about?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  7. #67
    Registered User
    Join Date
    May 2008
    Posts
    81
    Quote Originally Posted by anon View Post
    Isn't this what PRNG is all about?
    not rand.

    j/k

    yet another good point.

  8. #68
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by shawnt View Post
    good point.

    i guess I should have clarified that I was unsure how seeding srand() with a 'random number' multiple times ( = 1 srand(RANDOM_NUMBER) per rand) would be less random than using the RANDOM_NUMBER by itself.
    Well, it can not be BETTER than the rand() function - so it's either producing an equally good result or a worse result - because processing it through rand() itself will make it "as bad as rand()" by definition. A similar thing would be "noise reduction" (e.g. images, audio) that you can always remove data, but you can't (accurately and precisely) add in the original information once you have lost it. Same with random numbers - if you have a good random number function that you then run through a poor one, you get at best the results of the poor one. If you are unlucky, it may even cause some sort of resonance/cycling with the two random number generators, so that the numbers are for example bouncing around between the large and small ends of the possible range, with only rare instances in the middle range - that's just one of several possible scenario where it actually gets WORSE by seeding with a random number.

    As a conclusion: It never gets better, but it can get worse.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  9. #69
    Registered User
    Join Date
    May 2008
    Posts
    81
    Quote Originally Posted by matsp View Post
    As a conclusion: It never gets better, but it can get worse.
    --
    Mats
    Agree. This was agreed upon earlier.

    But I disgree with this part:
    Quote Originally Posted by matsp
    Same with random numbers - if you have a good random number function that you then run through a poor one, you get at best the results of the poor one.
    This is invalidated by the results of my simulation.

  10. #70
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by shawnt View Post
    This is invalidated by the results of my simulation.
    This is logic and I dare say, can be proved by any good mathematics equation or algorithm. If you run an inferior algorithm on a superior algorithm, the outcome will be the inferior one.
    You may not see it because the end result is within your tolerance limits, but it's still inferior, nevertheless.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  11. #71
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by shawnt View Post
    This is invalidated by the results of my simulation.
    How do you mean "it's invalidated by ..."? Are you saying that there is no difference between the MT19993 before and after rand() [obviously not counting the order the numbers come out, since that would change between the MT and the rand() with no MT seed]. You may be right in your testcase. I don't believe it holds true ALWAYS.

    Also, I would consider restricting the random number 15 bits as a worsening if nothing else. It may not matter if you are using the number to generate a dice roll or coin-flip, but if you are wishing to produce relatively precise floating point random sequences, or if you need a greater range than 32K, you would definitely not be happy with the rand() set.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  12. #72
    Registered User
    Join Date
    May 2008
    Posts
    81
    by invalidated, i meant that srand(MT.out) output is much more random than srand/rand alone.

    you said that coupling the two would "at best" give the results of the poor prng. i found this to not be the case since the results I got via coupling were FAR more random that srand/rand alone.

    anyway, it doesn't matter. since I am now believe that coupling prngs does not improve randomness, I will not use rand for my program...even though I didn't see any harmful effects either by coupling or by making multiple calls to srand().
    Last edited by shawnt; 06-10-2008 at 03:36 PM.

  13. #73
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by shawnt View Post
    by invalidated, i meant that srand(MT.out) output is much more random than srand/rand alone.

    you said that coupling the two would "at best" give the results of the poor prng. i found this to not be the case since the results I got via coupling were FAR more random that srand/rand alone.
    Define "more random" - bigger spread, more likely to not repeat, or what?

    But I guess that if you feed in a GOOD random number as a seed into a poor random number generator, I conceed that you may get a better result than the poor random number generator on it's own. But not as good as the original random number generator, so what's the point?

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  14. #74
    Registered User
    Join Date
    May 2008
    Posts
    81
    Quote Originally Posted by matsp View Post
    Define "more random" - bigger spread, more likely to not repeat, or what?

    But I guess that if you feed in a GOOD random number as a seed into a poor random number generator, I conceed that you may get a better result than the poor random number generator on it's own. But not as good as the original random number generator, so what's the point?

    --
    Mats
    yup, more random = greater likelihood of equal probability of occurance for each element within the period...this was addressed in my older posts.

    like I said, I coupled MT and rand simply on an intuitive guess that it may somehow compound randomness (as defined above). having disected this topic on this forum, I now believe that that isn't the case.

  15. #75
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You do realize, I take it, that there are literally dozens of PhD disertations and other scientific documents produced on the subject of "how to produce good and/or fast pseudo-random numbers", and new ones coming out every year. But the conclusion of most of these is that it's not trivial to come up with a GOOD and SMALL random number generator. The MT is a pretty decent compromise, as far as I'm aware.

    And I think we can agree that combining two PRNG together will not lead to better results than the standalone best of the two.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. random to int?
    By psyadam in forum C# Programming
    Replies: 7
    Last Post: 07-22-2008, 08:09 PM
  2. Lesson #3 - Math
    By oval in forum C# Programming
    Replies: 2
    Last Post: 04-27-2006, 08:16 AM
  3. Another brain block... Random Numbers
    By DanFraser in forum C# Programming
    Replies: 2
    Last Post: 01-23-2005, 05:51 PM
  4. How do I restart a random number sequence.
    By jeffski in forum C Programming
    Replies: 6
    Last Post: 05-29-2003, 02:40 PM
  5. Best way to generate a random double?
    By The V. in forum C Programming
    Replies: 3
    Last Post: 10-16-2001, 04:11 PM