Thread: Lottery Simulation

for my university assignment i have been asked to create a lottery simulation program.

the program needs to:
1. Welcome user to the program
2. Store 6 original numbers (saved in the code)
3. Ask how many years to simulate
4. Generate 6 unique lottery numbers (between 1-49)
5. Check the original numbers against lottery numbers
6. Store number of lottery numbers matched
7. Repeat step 4-6 for X years, or until jackpot is won.
Print year and results.

i have also attached a picture of a basis of what i want the program to look like.

im not asking for someone to write this code for me just give me some ideas on what i will need to use in my code to make this program.

Many Thanks

Ok, the obvious way is to have an array of numbers from 1 to 49 which you would shuffle, and then maybe pick the first 6 or the last 6 or whatever.

The shuffling can be made in a variety of ways, the easier one being to swap the position of two numbers in random positions for at least 100 times. The more numbers you swap, the more shuffled the array will be in the end. Practically, this can be accomplished by generating two random indices between 0 to 48, kinda like this:

Code:

int index1 = rand() % 49;
int index2 = rand() % 49;

int temp = randArray[index1];
randArray[index1] = randArray[index2];
randArray[index2] = temp;

put that inside a for loop and you're golden.

EDIT: I should point out that the previous method of generating ranged random numbers isn't very good, because PRNGs typically have some bias in their least significant bits. If you're interested, you might want to look into this alternative method:

Code:

int index = (int)((rand()/(double)RAND_MAX)*48 + 0.5);

Oh, and don't forget to use srand(time(NULL)) somewhere at the beginning of your program. Use it only once.

Originally Posted by GReaper

The shuffling can be made in a variety of ways, the easier one being to swap the position of two numbers in random positions for at least 100 times. The more numbers you swap, the more shuffled the array will be in the end. Practically, this can be accomplished by generating two random indices between 0 to 48

Instead of that, I'd suggest Knuth shuffle (a.k.a. Fisher-Yates shuffle): for each element in the array, pick a random element in the range from the element to the end (or beginning, if you iterate in reverse), then swap them.

That said, with only 6 numbers out of a possible 49, shuffling an array just to select the first 12% of the elements is a bit of a waste. I'd suggest generating 6 random numbers in the range, re-generating if you generate a duplicate

A good place to start is here - FAQ > Generate random numbers? - Cprogramming.com

I'd suggest that you start with laserlight's second suggestion with an array of 6, re-generating if you generate a duplicate.

Some considerations about random numbers generation. GReaper is right pointing to the fact that the linear congruential random number generator is problematic. The lower bits tends to be less random. Notice that this is a characteristic of this specific PRNG and the method using floating-point is a way to mitigate the problem obtaining a value between 0.0 and 1.0, and multiplying by the desired range. But there is a faster way: Use the upper bits instead.

This expression:

Code:

int index = (int)((rand()/(double)RAND_MAX)*48 + 0.5);

Could be writen using, entirely, integer operations like:

Code:

int index = (rand() >> 25) % 50;

Why 25 bits right shift? Because we need values between 0 and 2⁶ (64, the upper 6 bits -- more bits will be less random!), but rand() always returns an unsigned value (it is usual RAND_MAX to have the most significant bit zeroed). And for i386 and x86-64 modes it is usual RAND_MAX to be 31 bits long...

The second function is faster the the first (no floating point required and just one division)...

Hardware RNG:

There is a faster way, and more random!

If you are using Intel or AMD processors and want a "truly random" number (not "pseudo"), Modern architectures (since Haswell, for instance) has an internal diode to measure "noise" caused by temperature. Using this "quantum effect" we have a "true" RNG (almost!). And there is an instruction to get these random values generated by the CPU: RDRAND.

There are two advantages: RDRAND is faster then rand() and will return 16, 32 or 64 bits of truly random number (not 31).

Except by the intrinsic function __cpuid(), I prefer to implement RDRAND in assembly (there is an instrinsic __randNN_step() available in immintrin.h). NN is 16, 32 or 64:

Code:

#include <stdlib.h>
#include <time.h>

#if defined( __x86_64__ ) || defined( __i386__ )
#include <cpuid.h>

static int supports_rdrand = 0;

// This will be called before main()...
__attribute__ ( ( constructor ) )
void test_rdrand_support ( void )
{
# ifdef __x86_64__
  unsigned long long flags;
# else
  unsigned int flags;
# endif
  unsigned int a, b, c, d;

  __asm__ __volatile__ (
# ifdef __x86_64__
    "pushfq; popq %0"
# else
    "pushfl; popl %0"
# endif
    : "=g" ( flags ) );

  // supports cpuid?
  supports_rand = 0;
  if ( flags & ( 1U << 21 ) )
    supports_rdrand = 1;

  if ( supports_rdrand )
  {
    __cpuid ( 1, a, b, c, d );
    supports_rdrand = !! ( c & ( 1U << 30 ) );

    if ( supports_rand )
      return;
  }

  srand ( time ( NULL ) );
}

int getrand ( void )
{
  if ( supports_rdrand )
  {
    int rnd;

    __asm__ __volatile__ (
      "1: rdrand %0; jnc 1b" : "=r" ( rnd )
    );

    return rnd;
  }
  else
    return rand();
}
#else
# define getrand(...) rand()
#endif

Originally Posted by flp1969

Notice that this is a characteristic of this specific PRNG

Exactly, and what algorithm is chosen for rand() is implementation defined. If I needed a quality PRNG, I would drop in a known PRNG implementation rather than try and guess what problems rand() might present. For a university assignment that clearly is a throwaway learning program in which the specifics of the PRNG or RNG isn't the learning point, nah. Just use rand() % n and investigate PRNGs and RNGs outside of the assignment confines.

@flp, That jnc 1b looks a little fishy to me. Maybe I'm wrong, but doesn't that translate as "if the carry flag is not set (i.e., if rdrand failed) then jump forward 27 bytes?

Originally Posted by john.c

@flp, That jnc 1b looks a little fishy to me. Maybe I'm wrong, but doesn't that translate as "if the carry flag is not set (i.e., if rdrand failed) then jump forward 27 bytes?

Hehehe... it looks that way! I was confused when I saw this for the first time, but assembly in AT&T sintax requires a suffix 'f' (forward) or 'b' (backward) when the label is numeric:

Code:

1:
  rdrand
  jnc 1b     # jumps to 1 (backwards)
  jmp 1f    # jumps to 1 (forward)
1:

To use a hexadecimal value you need to prefix with '0x' (or, maybe, '$0x' - must test).

Ahhh... and this piece of asm is not entirely correct (it works!). The correct approach should be:

Code:

__asm__ __volatile__ ( "1: rdrand %0; jnc 1b" : "=r" (rnd) :: "cc" );

Because rdrand mess with the carry flag. The "cc" in "clobbered" field of asm block says to the compiler: "preserve the flags, if you must".

PS: Usually I prefer not to use ';' as a separator (for Intel processors, GNU Assembler uses # as comments). I wrote this way as a one liner. The syntax I prefer is:

Code:

__asm__ __volatile__ (
  "1:\t\n"
  "  rdrand %0\t\n"
  "  jnc 1b\t\n"
: "=r" (rnd) : : "cc" );

This way, when creating an asm listing with -S on GCC, this piece of code will be perfectly aligned with the remaining code...

@flp, If it means jump 1 byte backwards then it needs to be more than 1. The program counter will point to the beginning of the instruction after the jnc instruction, so you need to jump back as many bytes in both the jnc and the rdrand (and even the rdrand will be more than 1 byte long). It probably seems to work simply because rdrand rarely fails. Technically you shouldn't just jump back to it in an potentially infinite loop, but should instead retry it a fixed number of times. Intel recommends 10 times. Intel(R) Digital Random Number Generator (DRNG) Software Implementation Guide | Intel(R) Software

Originally Posted by john.c

@flp, If it means jump 1 byte backwards then it needs to be more than 1

No... it means jump to the label '1' before this point. Note, in the other example, there are 2 labels '1'...

I know the meaning of relative to RIP (or EIP) jumps...
In AT&T Syntax you can use numeric labels this way...

Code:

1: jmp 1f   # jumps to "jmp 2b".
2: jmp 2f   # jumps to "jmp 1b"
1: jmp 2b  # jumps to "jmp 2f"
2: jmp 1b  # jumps to "jmp 2b"

It's like the Knuth MIX assembly language!

And this example, using RDRAND, isn't an infinite loop... RDRAND will set CF when all "random" bits are available... CF=0 (and the destination is 0) when RDRAND still don't have them all...

Oh, of course. The 1 is a label. That makes sense now.

But I didn't say it was an infinite loop. I said it could become one if rdrand was for some reason not working properly. I also pointed you to the Intel documentation that recommends retrying only 10 times then giving up.