Thread: Ranom numbers having uniform distribution

  1. #1
    Registered User
    Join Date
    Feb 2008
    Posts
    146

    Ranom numbers having uniform distribution

    Hi,

    I need to generate 500 random numbers having uniform distribution. Does rand function ensure uniform distribution?

    Thanks,
    edesign

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Do you mean something like this: 2 8 10 6 12 4 ?

    The only random element of that is the order. In that case, I would just make an array of evenly distributed numbers (eg, generated with some function), and then use rand() to select the element number.
    Last edited by MK27; 08-15-2009 at 10:47 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    The standard doesn't guarantee a uniform distribution (it just says that rand gives a sequence of pseudo-random integers) but I am not aware of any compiler that doesn't have a uniform distribution for rand.

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    If we assume that "uniform" means "it's roughly the same likelihood of getting all numbers in the expected range", then I'd agree with Tabstop. rand() is not perfect, but for many things it's good enough. And this sounds like one of those cases.

    If you intend to make money using the random numbers, then you may need something better (less predictable for example), so that someone playing your card game or whatever can not predict what the next set of cards will be, for example.

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

  5. #5
    Registered User
    Join Date
    Feb 2008
    Posts
    146
    I want it to be uniformly distributed precisely. If I generate a histogram, I want it to be flat, same count for all the numbers. I need to generate the numbers in [0,1]. If rand generates same number more times than it'll destroy Uniform Dist property and will lead to errors in further calculations. The only way I can think of avoiding it is to check for every value, but that will be too costly to do. Is there some other way to do that?

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Even if rand() gives uniformly distributed numbers (which it does) that does not imply that you will get a flat histogram, nor should you expect it to, nor should you desire it to be so.

  7. #7
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    I think the only way to do that would be a rand() which guaranteed no repetition until all possibilities have occurred, which is not exactly random. When you roll a die, there is some chance of rolling 3 sixes in a row. If you rolled 100 times, I suppose the distribution would be reasonable uniform, but for this reason you cannot ask it to be perfect -- that's not random.

    Going back to my earlier idea, you could put all numbers into an array, shuffle it using rand(0), and then pop them off one at time from this "random list"; when you reach the end, shuffle and start again. No matter how many times you do that, you will end up with a dead even number of repetitions for each value, but the order in which they occur will be random.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by edesign View Post
    I want it to be uniformly distributed precisely. If I generate a histogram, I want it to be flat, same count for all the numbers. I need to generate the numbers in [0,1]. If rand generates same number more times than it'll destroy Uniform Dist property and will lead to errors in further calculations. The only way I can think of avoiding it is to check for every value, but that will be too costly to do. Is there some other way to do that?
    In other words, when you generate say the 400th random number it is absolutely not allowed under any circumstance to be equal to one of the previous 399 numbers?
    If so, then you can't just use a PRNG directly. You need an algorithm. The good news is that when done cleverly the cost of checking that the number hasn't been generated already becomes near zero.
    The trick is to first set up an array of the items you want to include in your output, pick one at random, and then overwrite it with one from point n, decreasing the length of the portion you are allowed to pick numbers from.
    My C is a little rusty, I'm used to C++ but...
    Code:
    int main(void)
    {
        /* setup */
        float values[500];
        int n = 500;
        int pos;
        for (int i=0; i<500; ++i)
            values[i] = i / 499.0;
    
        /* generation */
        srand(time(NULL));
        while (n > 0)
        {
            pos = rand() % n;
            printf("%f\n", values[pos]);
            n--;
            values[pos] = values[n];
        }
    }
    Including the appropriate headers is left as an exercise fo the reader
    That should give 500 equally spaces values in the range [0,1] assuming you didn't actually mean the range [0,1).
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  9. #9
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by iMalc View Post
    You need an algorithm. The good news is that when done cleverly the cost of checking that the number hasn't been generated already becomes near zero.
    The trick is to first set up an array of the items you want to include in your output, pick one at random, and then overwrite it with one from point n, decreasing the length of the portion you are allowed to pick numbers from.
    That's exactly what I suggested, using a Durstenfeld style shuffle.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  10. #10
    Registered User
    Join Date
    Feb 2008
    Posts
    146
    The question is like this:
    Write a function to generate random numbers as follows: Everytime the function is called, it generates 500 new random numbers in U[0,1] and output their sum.

    Generate 50,000 random numbers by repeatetedly calling the above function and plot their normalized histogram.
    If I use the approach suggested by iMalc, it will work well for part 1 but when the experiement is repeated it will generate the same set of 500 numbers each time. Just in a different order. But thanks all for suggestions. I think I am confused about the question itself.

    Thanks,
    Edesign

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  2. Replies: 4
    Last Post: 03-03-2003, 03:52 PM
  3. the definition of a mathematical "average" or "mean"
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 12-03-2002, 11:15 AM
  4. A (complex) question on numbers
    By Unregistered in forum C++ Programming
    Replies: 8
    Last Post: 02-03-2002, 06:38 PM
  5. Replies: 5
    Last Post: 10-12-2001, 03:51 AM