Sign in to follow this  
Followers 0
VicTT

Technical Question

11 posts in this topic

#1 ·  Posted (edited)

I have a few questions about the Random Number Generator present in AutoIt:

1. What is the number of calls after which Random(a,b,1) for arbitrary a<b values, returns a sequence which was already returned before?More specifically, when do the numbers start repeating themselves?

For example..Random(1,100,1) returns:

54, 22, 11, 33, 1, 20, 97, 33, ...

How many calls does it take to repeat the entire sequence all over again, and return 54, 22, 11, 33 and so on?

2. What is the average chance that for a given interval of integers (a;;), after b-a+1 calls of Random(a,b,1), the function will return more than one identical result..for example, if I run Random(1,10,1) 10-1+1=10 times, what is the average chance I'd get > 1 of one of the elements in the interval (1;10)..This could happen when I get 2 1's, or 3 2's..you get the idea

3. I'm taking any crazy idea about how to change the Random Seed during runtime..so as if at some point of the program, the sequences start repeating themselves, I would change the Random Seed so that I'd get unique sequences once again..

Edited by VicTT

[quote]Together we might liveDivided we must fall[/quote]

Share this post


Link to post
Share on other sites



How many calls does it take to repeat the entire sequence all over again, and return 54, 22, 11, 33 and so on?

Theoretically it will take 2^19937 calls before the sequence will repeat. In practice, you're not likely to ever reach that limit, since even if you generated 1000 random numbers per second, it would take you billions of years to get back to the beginning of the sequence.

Share this post


Link to post
Share on other sites

#3 ·  Posted (edited)

I was unaware that "The period, 2^19937-1" meant that it would take me that much calls to reach the beginning of the sequence..Although it does sound pretty logical now ;)..I've hacked a little program to test if the sequence ever repeats itself..of course..it's within the AutoIt tehnical limits..here it is..If my 5 minute logic is bad, and the program doesn't work, can anyone fix it for me?It's working as we speak and the array is 22.000 elements big right now..

Dim $maxm=100,$minr=1,$maxr=100
Dim $array[1]
$array[0]=Random($minr,$maxr,1)
$i=1
$t=0
$h=0
while $t<$maxm
$i=$i+1
Redim $array[$i]
TrayTip("Tester","Array is now "&$i&" elements big and "&$t&" matches were found",10)
$array[$i-1]=Random($minr,$maxr,1)
if $array[$i-1]=$array[$t] then
$h=1
$t=$t+1
endif
if ($h=0) And ($t>0) then $t=0
$h=0
wend
Edited by VicTT

[quote]Together we might liveDivided we must fall[/quote]

Share this post


Link to post
Share on other sites

I was unaware that "The period, 219937-1" meant that it would take me that much calls to reach the beginning of the sequence

That would be two to the power of 19937, that is, two multiplied by itself 19937 times. It's something like a 1 followed by 6000 zeros.

Share this post


Link to post
Share on other sites

;)..I know..the "^" resisted my copy&paste attempt..

Still waiting for answers to my other questions, though..


[quote]Together we might liveDivided we must fall[/quote]

Share this post


Link to post
Share on other sites

UPDATE: Made a second version of the program..It should be much faster..I'm not sure about the validity of it, though..I've been awake for 26 hours so far..And my coding/thinking skills aren't reliable in such conditions..Is the logic right?

Func ArrayReGen(ByRef $arr)
for $i=1 to $maxm-1
$arr[$i-1]=$arr[$i]
next
$arr[$maxm-1]=Random($minr,$maxr,1)
EndFunc
Func CompareArrays(ByRef $a,ByRef $b)
Local $y
for $i=0 to $maxm-1
if $a[$i]<>$b[$i] then 
SetExtended($y)
Return 0
else
$y=$y+1
endif
next
Return 1
EndFunc
Dim $maxm=100,$minr=1,$maxr=36,$j=0
Dim $array[$maxm],$comp[$maxm]
for $i=0 to $maxm-1
$array[$i]=Random($minr,$maxr,1)
next
for $i=0 to $maxm-1
$comp[$i]=Random($minr,$maxr,1)
next
$t=0
while $t<>1234
$i=$i+1
TrayTip("Tester",$i&" elements generated so far and "&$j&" matches were found",10)
if CompareArrays($array,$comp)=1 then $t=1234
$j=@extended
ArrayRegen($comp)
wend

[quote]Together we might liveDivided we must fall[/quote]

Share this post


Link to post
Share on other sites

UPDATE: Made a second version of the program..It should be much faster..I'm not sure about the validity of it, though..I've been awake for 26 hours so far..And my coding/thinking skills aren't reliable in such conditions..Is the logic right?

VicTT, it does not matter if your logic is right or wrong (and I have not even checked the script). Either you did not see the answer of Sokko or you did not understand the implications.

Even if you were able to calculate 100 billion random numbers per second, it would take you about 1,052624789590446729514312218597e+5973 times the current age of the universe (~13 billion years) to get a repeating sequence (I assume the numbers of Sokko are correct...). So, I guess your script will run for a looooong time and will consume a lot of RAM. You better upgrade you system ;)

Cheers

Kurt


__________________________________________________________(l)user: Hey admin slave, how can I recover my deleted files?admin: No problem, there is a nice tool. It's called rm, like recovery method. Make sure to call it with the "recover fast" option like this: rm -rf *

Share this post


Link to post
Share on other sites

I pulled that number from the documentation of the Random() function, which was itself pulled from the documentation of the algorithm that the function uses. Hence, I am assuming here that the author of the algorithm knows how long it will take before the sequence repeats itself.

So, I guess your script will run for a looooong time and will consume a lot of RAM.

Understatement Of The Year award. ;) Even if the entire mass of the world consisted of nothing but RAM chips, you would run out of memory a long time before you found a repeating pattern (and that's assuming you're willing to wait a few billion years for the calculations to finish).

Also keep this in mind: It's entirely possible that the generator uses the current date as a seed. In that case, even if you had billions of years and trillions of RAM chips to spare, you would never find a repeating sequence because the date would have changed by the time you reached the end of the period.

Share this post


Link to post
Share on other sites

1. No it wouldn't have..cause the seed is updated only once and that is at the start of the program..

2. How do you know it's not 3^5325, or any other number for that matter?How did he get this number?

3. It is fairly important if my logic is right/wrong, as it is fairly important that RAM isn't an issue here..if you would have checked my second script you would have understood this already..My script, indeed will run for a long time..


[quote]Together we might liveDivided we must fall[/quote]

Share this post


Link to post
Share on other sites

Comments based on the original source

This function uses the Mersenne Twister random number generator, MT19937, written by Takuji Nishimura, Makoto Matsumoto, Shawn Cokus, Matthe Bellew and Isaku Wada.

The Mersenne Twister is an algorithm for generating random numbers. It was designed with consideration of the flaws in various other generators. The period, 219937-1, and the order of equidistribution, 623 dimensions, are far greater. The generator is also fast; it avoids multiplication and division, and it benefits from caches and pipelines. For more information see the inventors' web page at http://www.math.keio.ac.jp/~matumoto/emt.html

Copyright © 1997 - 2002, Makoto Matsumoto and Takuji Nishimura, All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

3. The names of its contributors may not be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.


My UDF's:;mem stuff_Mem;ftp stuff_FTP ( OLD );inet stuff_INetGetSource ( OLD )_INetGetImage _INetBrowse ( Collection )_EncodeUrl_NetStat_Google;random stuff_iPixelSearch_DiceRoll

Share this post


Link to post
Share on other sites

#11 ·  Posted (edited)

My script, indeed will run for a long time..

Erm... No, it won't because either the universe will collapse or it will expand forever (not yet known). In the later case all matter will loose it's structure in about 100 billion years from now. So in both cases, your program will be terminated, without having the chance to calculate even a fraction of all possible random number sequences.

Cheers

Kurt

Edited by /dev/null

__________________________________________________________(l)user: Hey admin slave, how can I recover my deleted files?admin: No problem, there is a nice tool. It's called rm, like recovery method. Make sure to call it with the "recover fast" option like this: rm -rf *

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0