_Perfect_ simulation of a lotto-machine

[u]

Or instead of copying....

assuming nrandom(45) returned "3" (zero-based), do:
BallsRemaining[3] = BallsRemaining[44];


Here's C code, (for clarity) :

Code Select Expand


void Generate(int* Results){
int BallsRemaining[45];
for(int i=0;i<45;i++){
BallsRemaining[i] = i+1; // make results 1-based
}

int Max = 45;

for(int curDraw=0;curDraw<6;curDraw++){
int r = nrandom(Max);

Results[curDraw] = BallsRemaining[r];

Max--;
BallsRemaining[r] = BallsRemaining[Max];
}
}

Generate proc uses ebx esi edi pResults
local BallsRemaining[45]:DWORD

mov ecx,45
@@:
mov BallsRemaining[ecx*4-4],ecx
dec ecx
jnz @B


mov edi,Results
mov ebx,6 ; curDraw=6
mov esi,45 ; Max=45
@@:

invoke nrandom,esi ; nrandom(Max)
dec esi ; Max--
dec ebx ; curDraw--
mov edx,BallsRemaining[eax*4]
mov [edi+ebx*4],edx
mov edx,BallsRemaining[esi*4]
mov ballsRemaining[eax*4],edx
jnz @B
ret
Generate endp


Despite the reordering, each ball keeps its equal chance to be taken, but it depends on how nrandom() will disperse its results, thus the resulting dispersion of this lotto function can suffer a bit.

[jj2007]

Or, if you have complete faith in randomness (you shouldn't :lol) then you can swap the Nth number with the last element of the list -- a random random number is still random.

Swapping is a good solution.

   mov esi,45 ; Max=45

In real life, after each drawing one ball is gone forever, so Max must be decremented.

[MichaelW]

With so many parameters involved simulating a lotto machine even approximately would be a virtual impossibility, even if you had all of the specs. With such a great difference in the generators, I fail to see how progressively limiting the range of the numbers produced by nrandom, or other similar schemes, could be any better than just rejecting the invalid numbers.

[jj2007]

With so many parameters involved simulating a lotto machine even approximately would be a virtual impossibility, even if you had all of the specs. With such a great difference in the generators, I fail to see how progressively limiting the range of the numbers produced by nrandom, or other similar schemes, could be any better than just rejecting the invalid numbers.

You are probably right, but 1. cobold wants to simulate real behaviour, and 2. rejecting needs more code than just decrementing the Max  :wink

[u]

 :eek

ok, hands up all of you that studied extensively Probability and Statistics at university. My hand is raised now. I almost bombed Statistics, but at least I think I know how to create formulas for the probability. Heck, this "lotto machine" is one of the first tutorials in Probability classes  ::)
You want to create a perfect lotto simulation? Be my guest and make a 3D physical model simulation with Euler's integrations for the dynamics; I bet you'll get the same dispersion. Which currently is perfect.
jj2007, "dec esi" ... and nrandom(45) returns a number in the range [0;44].

This lotto proc has already been completed here imho. The only problem remaining is the construction of nrandom to wait for the user to press a button, and measure that time in cycles - to add more randomization. But that way we can't get the dispersion results easily :)

[MichaelW]

Interesting, “perfect simulation� apparently means something very different to me than it does to others here. It is very unlikely that a physical machine that is designed primarily to impress the ignorant masses, mostly through eye appeal, would produce statistically random sequences, or be designed in such a way that it could be reasonably modeled.

[FairLight]

Here's what i've done to generate random numbers for the german lotto about a year ago. It's a simple 6 out of 49 numbers generator. Not quite well programmed... wanted to learn assembly step by step, and to see how the nseed and nrandom procedures functioning... In my code you will see code step by step, no code improvements and failures due to lack of time, ... i've discarded the "rng" project.

"Ultrano wrote: The only problem remaining is the construction of nrandom to wait for the user to press a button, and measure that time in cycles - to add more randomization."

My conclusion to add more randomization was to nearly randomize the nseed procedure with GetTickCount, GetLocalTime, add, xor, sub, etc. instead of pressing the button six times !

Have Fun !





[attachment deleted by admin]

[Mark Jones]

Another source for a random seed could be the microphone recording input. Even with no signal present, there is noise... sample that, generate a random value, sample again, add it to the previous value, generate another random value, sample again... etc.

If you have some electronics experience, try applying around 20v/1mA in reverse through a general-purpose NPN transistor's B-E junction. This exceeds the breakdown voltage and current flows erratically on an atomic scale, which can be sampled and converted to integer(s). As simple as this seems, I wonder why the CPU doesn't include one extra transistor (out of the other billion-or-so) just for this purpose. An "FRND" instruction would be nice...

[Rockoon]

Re: FRND

Probably because it would be too difficult to provide any guarantees as to its distribution. It would be far better to implement such an instruction using a deterministic methodology, and as such, there doesnt really need to be an instruction.

I am not sure what to make of some of the comments in this thread but I think several people here are having trouble understanding that a truely random sequence of values from a normal distribution has statistical properties that can be emulated using psuedo-random techniques. That infact for all intents and purposes the output of a PNRG like the mersenes twister (MT) can be treated exactly like an ideal random number generator. The sequence length of MT19937 is so long that never in your lifetime will you ever run over the same location in the sequence if you so choose. The length is approximately 4.315425E+6001.

While it is true that many PNRG's have very poor statistical properties (especialy LCG's), that is not true for all of them.