Board Logo
« DO RANDOM NUMBERS REPEAT? »

Welcome Guest. Please Login or Register.
Dec 19th, 2014, 8:14pm


Conforums Terms of Service | Membership Rules | Home | Search | Recent Posts | Notification | Format Your Message | Installation FAQ

This board is not meant for general discussion, it is meant for posting articles to help others.
For general discussions use the appropriate board, which best describes your problem area.

« Previous Topic | Next Topic »
Pages: 1  Notify Send Topic Print
 thread  Author  Topic: DO RANDOM NUMBERS REPEAT?  (Read 4953 times)
Welopez
Moderator
ImageImageImageImageImage


member is offline

Avatar

Never let your beliefs get in the way of learning.


PM

Gender: Male
Posts: 4397
xx DO RANDOM NUMBERS REPEAT?
« Thread started on: Jan 28th, 2007, 12:02pm »

Do Random Numbers Repeat?


by Welopez


Many computer games, or computer simulations, rely upon random numbers. If we're playing roulette, we want to get a random number between 1 and 38; KENO, between 1 and 80; your state lottery, between 1 and 49 (or similar value); dice, between 2 and 12 (but dice are very different than roulette or KENO because we get a sum of two values from 1 to 6).

It is generally assumed random numbers are stored in your computer as a stack of values, in seemingly random order. I don't believe this, but I could be wrong. My guess is your operating system uses an algorithm to generate a random number. How often do these values repeat? I don't know. Why should you care?
Code:
PRINT RND(0)
END
 

Every time you run that line of code you should get a different value. The first time I ran it, I got 0.20178344, your value will probably be different. What if I run that line one million times?

Try this simple routine to fill an array with one million values between 0.00000001 and 0.99999999. That's more than 99 million possible values!
Code:
DIM nums(1000000)       'Set up an array of 1,000,000 random numbers

DO
reps=reps+1             'Count repetitions through the loop
flag=0                  'Reset sequence flag to 0

FOR k=1 to 1000000
    nums(k)=RND(0)      'Fill the array with random values
NEXT k

start=TIME$("ms")
FOR k=2 TO 999999       'Comparison block
    IF nums(1)=nums(k) THEN
    flag=1              'Set flag if sequence has repeated
    END IF
NEXT k
finish=TIME$("ms")

PRINT "Program executed in "; (finish-start); " ms; "; flag; " repeats."
LOOP WHILE reps<10

END
 

The routine will execute 10 repetitions requiring about 20 seconds each, on a machine with a 2.8 GHz processor. It fills the array with one million values, then compares the first value to every value in the array, and reports how many times the first value matched another. We're only comparing nums(1) to all the other values. You can rewrite the code to use nested loops for nums(x) and nums(y). If you do, send me a post card when the comparison finishes, it's going to take a very long time!

Then it loops and fills the array with one million new values, compares the first value to all the others and reports again. It will do this for 10 repetitions and take about 3.5 minutes, depending upon the speed of your CPU. I found no repetitions, but that doesn't mean you won't! I've only generated 1,000,000 out of a possible 99,999,999 values! Maybe your run will hit pay dirt!

We may think we've found the place in our routine where the RND(0) function begins to repeat in a predictable fashion. The problem arises when we begin to limit the field of possible random numbers. In roulette, we only want to consider 38 possibilities; 49 for our state lottery; 80 for KENO. Sooner or later, one or more of those numbers will repeat. But is the sequence predictable? Try this code for a KENO game.
Code:
DIM nums(1000000)       'Set up an array of 1,000,000 random numbers
                        'with a value of 1 to 80
DO
reps=reps+1             'Count repetitions through the loop
flag=0                  'Reset sequence flag to 0

FOR k=1 to 1000000
    nums(k)=INT(RND(0)*80)+1
NEXT k

start=TIME$("ms")
FOR k=2 TO 999996       'Comparison block
    IF nums(1)=nums(k) AND _
    nums(2)=nums(k+1) AND _
    nums(3)=nums(k+2) AND _
    nums(4)=nums(k+3) THEN
    flag=1              'Set flag if sequence has repeated
    END IF
NEXT k
finish=TIME$("ms")

PRINT "Program executed in "; (finish-start); " ms; "; flag; " repeats."
LOOP WHILE reps<10

END
 

In this routine, we fill the nums(array) with 1,000,000 random values from 1 to 80. Even my grand-daughter will tell you there must be a few repeat values. But is the sequence identifiable? When I wrote the following comparison block:
Code:
IF nums(1)=nums(k) AND _
nums(2)=nums(k+1) THEN
flag=1
END IF
 

...every program run tripped the flag. Why not? If you stand around a roulette wheel long enough, you'll see a number repeat once in awhile, but not necessarily the same number. Likewise for your state lottery or a KENO game of 80 numbers.

When I rewrote the code to compare 3 values in sequence, it occasionally (not always) tripped the flag; 80^3=512,000, and the sequence of 3 numbers was identical once in awhile. So I wrote it again to compare 4 values in sequence, and the flag was never tripped; 80^4=40,960,000. The flag could have been tripped, but since we've only compared 1 million out of 40 million sequences, we were lucky.

The smaller your field of possible values, the more likely it is for a short sequence to repeat. But random is still (more or less) random. I'm not an expert in the construction of computer algorithms, so I'm pretty content to use the tools the experts give me. Just be aware random numbers are seldom predictable, unless the programmer is pulling a fast one like an Old West card sharp.
« Last Edit: Jan 28th, 2007, 4:14pm by Welopez » User IP Logged

JB 1.01
Win7 64bit, 4 GB RAM, Pentium 6200@2.13 GHz (laptop)
WinXP, 1 GB RAM, Intel N270@1.6 GHz (netbook)
Brian M.
Full Member
ImageImageImageImage


member is offline

Avatar



YIM YIM
Homepage PM

Gender: Male
Posts: 441
xx Re: DO RANDOM NUMBERS REPEAT?
« Reply #1 on: Jun 6th, 2007, 05:13am »

Wow, Welopez, its nice to know that you have a whole 1000 megabytes, providing each array element is 1 byte, isn't that a gigabyte? dedicated to array memory? I remember when basic compilers out there gave you only a measly 64 mb. It just goes to show you just how far we have advanced technilogically, more ideas = bigger ideas = more memory = even bigger ideas= even more memory = even bigger ideas. Yeah its a never ending story of growth and expansion. I just want to thank you for all the tutorials/tips you have donated to JB forums. If it wasn't for you, JB would be half what it is today. Catch ya later, alligator...
« Last Edit: Jun 6th, 2007, 07:35am by Brian M. » User IP Logged

Brian M's Just Basic Site
American Acolyte Dot Org--freeware development software directory
Welopez
Moderator
ImageImageImageImageImage


member is offline

Avatar

Never let your beliefs get in the way of learning.


PM

Gender: Male
Posts: 4397
xx Re: DO RANDOM NUMBERS REPEAT?
« Reply #2 on: Jun 6th, 2007, 07:43am »

Thanks for your comments, Brian. Usually it's my Worbles who get the swelled heads, they are such simple fellows you know... but it's nice to know that some people actually do read the tutorials.

For those who were around when the average home computer had 4KB of RAM, or less, it's really marvelous to have MB, even GB sticks of RAM now days. Of course, the new coders, with all that RAM to burn, seldom learn simple tricks to make their code more concise. I think the advantage of larger and faster RAM is not having to worry about keeping the remarks limited, to save program space, and it's much easier to write and debug programs if you can avoid lines with six, eight, or ten multiple statements.

I checked out your contest entry... very nice! I still enjoy using wordpad to create HTML documents. It seems everytime someone creates a new HTML generator, you have to learn how to use it, which takes more time than simply typing a document. I have Front Page, but creating a web page with wordpad is often much easier. I always keep my reference book close at hand! Next to an inquisitive mind, references and help are the programmers most important tools!
User IP Logged

JB 1.01
Win7 64bit, 4 GB RAM, Pentium 6200@2.13 GHz (laptop)
WinXP, 1 GB RAM, Intel N270@1.6 GHz (netbook)
shillito111
Full Member
ImageImageImageImage


member is offline

Avatar




Homepage PM


Posts: 222
xx Re: DO RANDOM NUMBERS REPEAT?
« Reply #3 on: Jun 10th, 2007, 03:50am »

Great tutorial it will help me with the games i make ive read all your tutorials that ive found as they all help me. wink

Shillito111
User IP Logged

Visit T-ACE GAMES today with all my games on it...

http://tacegames.googlepages.com
Julian
New Member
Image


member is offline

Avatar




PM

Gender: Male
Posts: 3
xx Re: DO RANDOM NUMBERS REPEAT?
« Reply #4 on: Jul 30th, 2007, 5:25pm »

1000 Bytes is equal to 1 Megabyte, not 1000[EDIT: Sorry, I just read a post by Stefan Pendl,http://justbasic.conforums.com/index.cgi?board=general&action=display&num=1185867502, where he corrects me, he's right, 1 Megabyte is actually equal to 1,000,000 bytes, dumb mistake on my part.] . So anyone should be able to try Welopez's program with the one million element array. cheesy
I'm 99.999999% sure that computers use algorithms to generate random numbers, in some languages like QBasic you call the algorithm with a command like RND, and either supply it with a "seed" number, in which case it will mathematically scramble the seed and then spit it out again as a fairly random number, or, you can tell it to use the clock as it's seed, so that the number generated will be even more random, because it's seed will be different almost every time. Of coarse, if I'm right, (and surely I am grin ) then every computer with the same algorithm would get the same "random" number, if run at the exact same time!

I hope I don't sound annoying with all this...
« Last Edit: Aug 3rd, 2007, 09:04am by Julian » User IP Logged

ExtraAmmo
New Member
Image


member is offline

Avatar




PM


Posts: 4
xx Re: DO RANDOM NUMBERS REPEAT?
« Reply #5 on: Aug 6th, 2007, 12:20pm »

1 bit = 1/0
1 byte = 8 bits
1 kilobyte = 1024 bytes
1 megabyte = 1024 kilobytes
1 gigabyte = 1024 megabytes
1 gigabyte = 8,589,934,592 bits = 1,073,741,824 bytes

A CPU of 3.00 GHz is launching 25,769,803,776 bits through it per second.
User IP Logged

tsh73
JB-Supporter


member is offline

Avatar




PM

Gender: Male
Posts: 2925
xx Re: DO RANDOM NUMBERS REPEAT?
« Reply #6 on: Aug 6th, 2007, 2:43pm »

Quote:
A CPU of 3.00 GHz is launching 25,769,803,776 bits through it per second.


This one is wrong.
Basically it's different things.
Like speed of car, mph and rpm of it's engine.
They not directly related and relation differs from car to car (think processor models).

You can read some on it here
http://en.wikipedia.org/wiki/Hertz#Computing
« Last Edit: Aug 7th, 2007, 01:17am by tsh73 » User IP Logged

Q: "And if I took your codes and compile them, and sell them for a profit"?
A: Go ahead. I had my share of good then I coded it for fun, if you can make better use of it - please do.
(enjoying JB 1.01 on WinXP, netbook and desktop)
AndyAmaya
Board Moderator


member is offline

Avatar




PM

Gender: Male
Posts: 295
xx Re: DO RANDOM NUMBERS REPEAT?
« Reply #7 on: Aug 7th, 2007, 07:58am »

tsh73 is spot on about differences in CPU's

Mostly due to the implementation of varying numbers of "pipelines"
(see: http://en.wikipedia.org/wiki/Pipeline_%28computer%29 )

With pipelining more than 1 instruction per machine cycle can be performed. These instructions can vary in the number of bits from 32 bits to more than 32 bits due to the complex instruction set used by Intel processors.

In summary, clock speed (GHz) does not necessarily indicate true processing speed.
User IP Logged

tsh73
JB-Supporter


member is offline

Avatar




PM

Gender: Male
Posts: 2925
xx Re: DO RANDOM NUMBERS REPEAT?
« Reply #8 on: Sep 24th, 2007, 08:26am »

Actually, I think the answer is important.
And the answer is "yes".
(because "ordinary" computers use some formula to calculate next random value based on preious one(s) - I do not took into accout some special boxes getting RND out of space rays etc. Have you seen any of that stuff? I personally do not, so your computer does that he can in simulating random - just counts stuff).

But next question will be - how fast they'll start repeating?
If you need handful of numbers - you do not care much.
But if you need more? (and it takes about 30 sec to fill an array with 1000000 random numbers now!)

Because if it will start repeating from 1001, and you need 10000 random - that is, unpredictable - numbers for say numerical simulation, you are in trouble.

Now, Welopez says "... an array with one million values between 0.00000001 and 0.99999999. That's more than 99 million possible values!"

I really wonder if it written somehere. - amount of possible values, that is. Probably not, because computers think in binary so "0.99999999" is unlikely number for computer to use as a bound. And because it looks like JB stores abount 14 significant digits, so we likely would have more then 99 999 999 variations.

Below is the program (variations of things Welopes put in his article) that looks for repetition. It stores some first randome numbers, then looks for first match, then checks if it continue to match.
Code:
RANDOMIZE .5
minDiff = 100
'DIM i AS LONG
DIM a(100)
FOR j = 1 TO 100
   a(j) = RND(1)
NEXT
t = a(1)
PRINT t

i = 100
DO WHILE 1
scan
    i = i + 1
    IF i MOD 100000 = 0 THEN PRINT i, i/1e6
    r = RND(1)
    diff = ABS(r - t)
    IF r = t THEN PRINT "!!!", i, r: EXIT DO
    IF diff < minDiff THEN
        minDiff = diff
        PRINT i, r, diff
    END IF
LOOP

FOR j = 2 TO 15
   PRINT i + j - 1, a(j), RND(1)
NEXT
 

Now, computers is so fast that I can run it and forget it, and check after may be hours passed.
I breaked it after it just get over 104 000 000 - so I am pretty sure that indeed we have more then 99 999 999 variations. Next suspectable nuber would be somehere around 256^4 - but it will work forever ? Actually just 40 times longer, so if you run it for a week or two you will know if it repeats after 256^4 or not.
But I think 100 millions of un-repeating random numbers pretty good for me, so I'll stop that.

Now, you see commented "'DIM i AS LONG" in that program? I run it in QBasic - and indeed I got that random numbers in QBasic started repeat after 16777216, that is, 256^3. No matter how you convert you RND you will not get after 16 777 216 without repeating.
But we, JB users, are more lucky. We get it over 100 000 000 - noone(?) knows how far.
User IP Logged

Q: "And if I took your codes and compile them, and sell them for a profit"?
A: Go ahead. I had my share of good then I coded it for fun, if you can make better use of it - please do.
(enjoying JB 1.01 on WinXP, netbook and desktop)
uncleBen
Senior Member
ImageImageImageImageImage


member is offline

Avatar




PM


Posts: 1679
xx Re: DO RANDOM NUMBERS REPEAT?
« Reply #9 on: Sep 24th, 2007, 10:58am »

It is quite possible that the next pseudorandom number is not determined only by the previous value. Even if the exact same value comes up, it needn't mean that the whole sequence is repeating.

In comparison with C where rand() returns integers in range [0, RAND_MAX) and RAND_MAX is merely 32,767 for me - the random values naturally reoccur quite often, but that doesn't mean that the same sequence would start all over.

----------
If I'm not mistaken, this tutorial was written in response to this thread, and indeed if you reboot the computer inbetween your next run of a program will produce the exact same sequence of random values. If that is a problem, seeding the random number generator (probably with a combination of date/time to produce a unique value for each run of the program) may be necessary.

User IP Logged

Passing arrays to subroutines, functions that work with any types, quick string indexing and much more - JBExtensions.

Tired of Minesweeper? Try TomatoSweeper
tsh73
JB-Supporter


member is offline

Avatar




PM

Gender: Male
Posts: 2925
xx Re: DO RANDOM NUMBERS REPEAT?
« Reply #10 on: Sep 25th, 2007, 12:07am »

Quote:
It is quite possible that the next pseudorandom number is not determined only by the previous value. Even if the exact same value comes up, it needn't mean that the whole sequence is repeating.

Well, I do not argue. Actually I use it backwards: if you do not have number repeated in 100 000 000 iterations, then you GUARANTEED to have 100 000 000 numbers before sequence repeat.
But for QBasic it just happened that then number repeated, it seems to be repeat of whole sequence (I checked just beginning of sequence, not all 16 ### ###).

Quote:
In comparison with C where rand() returns integers in range [0, RAND_MAX) and RAND_MAX is merely 32,767 for me - the random values naturally reoccur quite often, but that doesn't mean that the same sequence would start all over.

Indeed probably C keeps random generator state in some bigger variable - or variables. Since I got repeat of first number is 7 ###... but repeat of two in 10 ### ### - and then my old DOS Borland C crashed leaving me without working program, so I gave up.

But the point was: random genetator has to store it's state somewhere; and if it is 4 bytes, that llimits the sequence with 256^4 (or 2^32), 4 ### ### ###, no matter that. Of cource it's pretty big number. And if it's not enough, you can use two 4-byte integers for a state, rising theoretical limit to 2^64. And 14 significant digits in real (that about that we see in JB) needs 8 bytes (in QBasic , VB and C at least) - so probably sequence of random numbers in JB is VERY long.
User IP Logged

Q: "And if I took your codes and compile them, and sell them for a profit"?
A: Go ahead. I had my share of good then I coded it for fun, if you can make better use of it - please do.
(enjoying JB 1.01 on WinXP, netbook and desktop)
tsh73
JB-Supporter


member is offline

Avatar




PM

Gender: Male
Posts: 2925
xx Re: DO RANDOM NUMBERS REPEAT?
« Reply #11 on: Sep 27th, 2007, 12:02am »

Quote:
We get it over 100 000 000 - noone(?) knows how far.


I was interested enough to leave that program running for several days.
Yesterday it get somewhere above 2 ### ### ### random number, still without repeat. But in the evening it crashed with this error log:
Quote:
Error log timestamp 9/26/2007 21:51:18
Message 3005:
Virtual machine stack overflow.

so:
1) JB have at least 2 000 000 000 un-repeating random numbers;
2) I do not know if they repeat anythere soon after 2 000 000 000 (remember, that 256^4 = 4 294 967 296)
3) probably JB not supposed to run for several days in a row non-stop. (Well, It might be a coincidence. I just not in mood to start this program for another 3 days).
User IP Logged

Q: "And if I took your codes and compile them, and sell them for a profit"?
A: Go ahead. I had my share of good then I coded it for fun, if you can make better use of it - please do.
(enjoying JB 1.01 on WinXP, netbook and desktop)
Sub12
Full Member
ImageImageImageImage


member is offline

Avatar




PM

Gender: Male
Posts: 198
xx Re: DO RANDOM NUMBERS REPEAT?
« Reply #12 on: May 6th, 2008, 10:49am »

This is rather like this statement:

"If we had a infinite amount of monkeys randomly pressing keys on an infinite amount of typewriters then eventually one of them will type out the entire Old Testament, correct to the last full stop."

If we had an infitite amount of random numbers, say from 1 to 1000, eventually the first 100 numbers, or even the first 1000, would be repeated exactly, simply because the random numbers are infinite. In this way, I guess, random numbers do repeat. If anyone could be bothered they could run a program that generates 10 million random numbers, and prehaps the first 10 or 5 numbers would be repeated somewhere.

Bit of an old thread, but oh well.
« Last Edit: May 6th, 2008, 10:49am by Sub12 » User IP Logged

Pages: 1  Notify Send Topic Print
« Previous Topic | Next Topic »

Conforums Terms of Service | Membership Rules | Home | Search | Recent Posts | Notification | Format Your Message | Installation FAQ

Donate $6.99 for 50,000 Ad-Free Pageviews!

| |

This forum powered for FREE by Conforums ©
Sign up for your own Free Message Board today!
Terms of Service | Privacy Policy | Conforums Support | Parental Controls