rand() is producing patterns

This is a discussion on rand() is producing patterns within the C Programming forums, part of the General Programming Boards category; I created a lottery-type program that you pick 6 numbers from a given range. The program randomly selects 6 numbers ...

  1. #1
    usb
    usb is offline
    Registered User
    Join Date
    Nov 2004
    Posts
    4

    Unhappy rand() is producing patterns

    I created a lottery-type program that you pick 6 numbers from a given range.

    The program randomly selects 6 numbers from the same range and determines how many tries it takes to choose 6 numbers that match the your 6 numbers.

    I used rand() and srand() to generate the random numbers that the computers uses to try and match your six numbers.

    I am experienceing patterns with the random number drawing of rand().

    If I chose 6 numbers from a max range of 47 numbers.
    The computer matched my numbers in the same amount of attempts in a serries of 37 tries.

    Example:
    Attempt 1: match in 2277042 tries
    Attempts: 2 - 36
    Attempt 37: match in 4817236 tries

    Attempt 38: match in 2277042 tries
    Attempts: 39 - 74 (same as attempts 2 - 36)
    attempt 75: match in 4817236 tries

    Any answers on why the patterns when it should be random?
    Is there a way to prevent this pattern forming in random number drawing?

  2. #2
    Super Moderator Harbinger's Avatar
    Join Date
    Nov 2004
    Posts
    74
    > Any answers on why the patterns when it should be random?
    Because rand() uses an algorithm, and all algorithms produce repeatable output from identical input.
    All pseudo random number generators have a periodic length after which the sequence begins again in exactly the same order as before.

    For the sake of discussion, here's one
    1 7 3 4 9 6 2 5 9 8
    Now if you call srand() with a different value, you may get
    4 9 6 2 5 9 8 1 7 3
    or
    5 9 8 1 7 3 4 9 6 2
    but the result is always the same, after you're passed the periodic length, you're back to where you started.

    > Is there a way to prevent this pattern forming in random number drawing?
    Use a much better algorithm
    http://www.google.com/search?hl=en&q=mersenne+twister
    This has a period which blows the usual rand() implementation away. This is usally good enough for statistical applications

    If you're on Linux, then try
    man urandom
    to see how to use the cryptographic quality random number generator.

  3. #3
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Because you are only choosing 6 numbers. Also you have to remember that its a psuedo-random number generator. And I'm willing to bet that you are using mod to get your 6 random numbers.

    All of these combined pretty much ensure you'll have some type of pattern.

  4. #4
    Registered User
    Join Date
    Jan 2002
    Location
    Vancouver
    Posts
    2,220
    Only call srand once, at the start of your program.

  5. #5
    .
    Join Date
    Nov 2003
    Posts
    307
    try
    Code:
    srand(time(NULL));

  6. #6
    usb
    usb is offline
    Registered User
    Join Date
    Nov 2004
    Posts
    4
    To jim mcnamara and Brian:
    At the start of the code I run srand((unsigned)time(NULL)); once. It never runs again.

    To Thantos:
    I am using mod. This is the function:

    Code:
    int roll (int max) {
        int rmax;
      	rmax = rand()%max+1;
    	return rmax;
    }
    To Harbinger:
    I am on a windows system using Borland C++ Compiler 5.5.
    Will this other algorithm work in this environment?

  7. #7
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,586
    Hint: pseudo-random number generator.

  8. #8
    usb
    usb is offline
    Registered User
    Join Date
    Nov 2004
    Posts
    4
    I found and downloaded this random number generator: mt19937int.c

    This is a step beyond my scope.

    I deleted main and renamed the file to random.h
    In my program I entered: #include <random.h>
    I seeded the routine as described sgenrand(4357) in mt19937int.c

    I am unsure how to tell genrand() the range of numbers to randomly pick from.
    Last edited by usb; 11-11-2004 at 06:22 PM.

  9. #9
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,344
    > This is a step beyond my scope.
    Then I suggest you post what you've tried so far, so we can suggest improvements within the scope of what you know already.

  10. #10
    usb
    usb is offline
    Registered User
    Join Date
    Nov 2004
    Posts
    4
    I used mod to generate the numbers from a specific max as when I used rand(). It works, however one of the comments posted seemed to state that using mod is not the best way.

    In both rand() and genrand() I must add 1 to max in order to get the maximum randomly chosen.

    This works, but again it sounded like there was a better way of telling the function the maximum number to randomly select from.

    Code:
    /* Generate random number */
    int roll (int max) {
       int rmax;
       rmax = genrand()%max+1;
       return rmax;
    }

  11. #11
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Do a board search and you'll find better algorithms. To sum up a general one:
    1) Cast the return of rand() to a double and divide by RAND_MAX. This gives you a number between 0 and 1 inclusive.
    2) Multiply by the difference between your high and your low
    3) Add your low value
    4) Cast to the type you want (ie double, float, int).

  12. #12
    .
    Join Date
    Nov 2003
    Posts
    307
    FWIW - It may be your base algorithms, not the PNRG you're using.

    Just coded a quick & dirty test. It is not your rand() function. I used rand() drand48() and other PNRG's we have here. The number of iterations for all of them were all over the place, as you would expect. I used four fixed test arrays of six numbers.

    I suspect it is your algorithm.
    I create an array 1-47, select 6 of those at random(no duplicates) , copy them into an array with six elements, then compare the sorted small array with the original six element array.
    This puts six random "choices" into the first six first six elements of arr[].

    Code:
    void shuffle(long arr[],int len)
    {  /* len is always six */
       int i;
       int which=0;
       for(i=0;i<len;++i) arr[i]=i+1;
       for(i=0;i<6;++i)
       {
           which =rand()%len;
           swap(&arr[which],&arr[i]);    
       } 
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. bit patterns of negtive numbers?
    By chunlee in forum C Programming
    Replies: 4
    Last Post: 11-08-2004, 07:20 AM
  2. Cprog tutorial: Design Patterns
    By maes in forum C++ Programming
    Replies: 7
    Last Post: 10-11-2004, 01:41 AM
  3. Creating Bullet Patterns
    By The Dog in forum Game Programming
    Replies: 9
    Last Post: 10-30-2003, 02:33 PM
  4. Creating Patterns
    By incognito in forum Game Programming
    Replies: 5
    Last Post: 03-16-2003, 08:02 AM
  5. Patterns
    By Unregistered in forum A Brief History of Cprogramming.com
    Replies: 6
    Last Post: 04-29-2002, 04:02 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21