Random Numbers
Random Numbers
Can anyone clue me in to the workings of random number generators? Im aware of there being a few kinds in existance but I cant seem to find any sites with a formula, or something of that nature. If possible, code would be nice.
C:\DOS
C:\DOS\RUN
RUN\DOS\RUN
C:\DOS\RUN
RUN\DOS\RUN
- {Nathan}
- Veteran
- Posts: 1169
- Joined: Thu Aug 19, 2004 6:08 pm
- Location: The wetlands of central Ohio, USA
- Contact:
I think (tell me if I am wrong) but he wants to know the inner-workings of QB's RND function. I do believe that if you use the TIMER seed, then it will be randomized off of time.
Now, this is all guesses (I am not sure about these, but am pretty sure). The RANDOMIZE statement takes a number and creates a mathmatical formula based upon it. Basically, when you use a set number, its the same pattern all the time (more on this later), but when you use TIMER as a randomazation seed, it is different each time (the seed is) so therefor so is the formula.
As for using a set number? Ever heard of the game show Wammy? There was a guy from Ohio, USA that basically found the pattern, went on that show and won a ton of money. Because of this they soon had to shut down the system, but he is back at work cracking the "new" wammy system, but who knows what hes gonna do for us...
Now, this is all guesses (I am not sure about these, but am pretty sure). The RANDOMIZE statement takes a number and creates a mathmatical formula based upon it. Basically, when you use a set number, its the same pattern all the time (more on this later), but when you use TIMER as a randomazation seed, it is different each time (the seed is) so therefor so is the formula.
As for using a set number? Ever heard of the game show Wammy? There was a guy from Ohio, USA that basically found the pattern, went on that show and won a ton of money. Because of this they soon had to shut down the system, but he is back at work cracking the "new" wammy system, but who knows what hes gonna do for us...
- matt2jones
- Veteran
- Posts: 80
- Joined: Sat Feb 19, 2005 8:29 am
- Location: elsewhere
- Contact:
There are an infinite number or chaotic functions that will return 'random' numbers. Given the same argument they'll always return the same number, but there's no pattern in the numbers returned for any interval...
That's a way to return random numbers.
The first time it's called, you call rnd(0), the second time rnd(1) etc.
I don't actually know if this method is used by any compilers though...
matt
That's a way to return random numbers.
The first time it's called, you call rnd(0), the second time rnd(1) etc.
I don't actually know if this method is used by any compilers though...
matt
Do not mistake Apathy for feeling Content.
http://www.disjointed.cjb.net - Short Storys
http://matt2jones.deviantart.com - Random Art
http://www.freewebs.com/matt2jones - WebComic
http://www.disjointed.cjb.net - Short Storys
http://matt2jones.deviantart.com - Random Art
http://www.freewebs.com/matt2jones - WebComic
Randomized number generators work by setting a internal starting value..
(In QB you can pass this as an argument)
It then stores that value in a variable, divide by a number, multiplicate and such..
And spits out a new number..
The new number is also stored..
Next time you call the function it does the same thing.. the "new number" is moved to the "old number" and a real new number is created and returned using the "old number" and "new number"
All RND generators wrap around at some point, often far sooner than you might think..
(In QB you can pass this as an argument)
It then stores that value in a variable, divide by a number, multiplicate and such..
And spits out a new number..
The new number is also stored..
Next time you call the function it does the same thing.. the "new number" is moved to the "old number" and a real new number is created and returned using the "old number" and "new number"
All RND generators wrap around at some point, often far sooner than you might think..
I have left this dump.
Re: Random Numbers
using search machine and the words Pseudo-random Numbers you will find some formulas but seeing that we are in Quickbasics you can find the formula used by the Basics of Microsoft into this article of the Quickbasics knowledge base.Zamaster wrote:Can anyone clue me in to the workings of random number generators?
http://support.microsoft.com/default.as ... n-us;28150
- matt2jones
- Veteran
- Posts: 80
- Joined: Sat Feb 19, 2005 8:29 am
- Location: elsewhere
- Contact:
The Chaotic Functions I was talking about don't, that's why I brought them up... Non-periodic or something...All RND generators wrap around at some point, often far sooner than you might think..
matt
Do not mistake Apathy for feeling Content.
http://www.disjointed.cjb.net - Short Storys
http://matt2jones.deviantart.com - Random Art
http://www.freewebs.com/matt2jones - WebComic
http://www.disjointed.cjb.net - Short Storys
http://matt2jones.deviantart.com - Random Art
http://www.freewebs.com/matt2jones - WebComic
That is impossible, if you have a finite amount of numbers, you will wrap around and repeat at some point..matt2jones wrote:The Chaotic Functions I was talking about don't, that's why I brought them up... Non-periodic or something...All RND generators wrap around at some point, often far sooner than you might think..
matt
Simple example to prove the point:
Assume you have a 1bit number, that is: 0 to 1 can be represented..
You can do the following combinations:
10, 11, 01 and 00
You can combine them in different ways etc.. but they will rpeeat after a while..
As you can see even a 1bit number will create a huge table before it wraps around..
But with todays computers, even a 32bit number is only a matter of minutes, if not seconds, before it wraps around..
I have left this dump.
- matt2jones
- Veteran
- Posts: 80
- Joined: Sat Feb 19, 2005 8:29 am
- Location: elsewhere
- Contact:
Of course it can return a number more then once! If you roll a dice 27 you get each number more then once, that's still a random number generator.
What I ment was there is no repitition of the pattern, eg.
int(rnd*2) -> 1 0 1 0 1 0 1 0
Where there is a pattern in the random numbers.
matt
Do not mistake Apathy for feeling Content.
http://www.disjointed.cjb.net - Short Storys
http://matt2jones.deviantart.com - Random Art
http://www.freewebs.com/matt2jones - WebComic
http://www.disjointed.cjb.net - Short Storys
http://matt2jones.deviantart.com - Random Art
http://www.freewebs.com/matt2jones - WebComic
Well, the problem is in how most random generators work. Most of them are iterated functions. For a simple, non-random one, try this:matt2jones wrote:
Of course it can return a number more then once! If you roll a dice 27 you get each number more then once, that's still a random number generator.
What I ment was there is no repitition of the pattern, eg.
int(rnd*2) -> 1 0 1 0 1 0 1 0
Where there is a pattern in the random numbers.
matt
X(n+1) = (X(n)^2 + p) mod q
(This isn't QB syntax, it's mathematical.)
Suppose P = 2 and Q = 99 and X(1) = 5. Running through this you'd get:
5
27
38
60
38
60
38
etc.
Ok, bad example there: After just 3 iterations you get into a 2-cycle. Let's try p = 7 and q = 101, and x(1) = 5 again:
5
32
21
44
24
88
75
77
78
31
59
54
and so on. (I could keep going, but I didn't feel like writing a program to do it and I'm just doing them by hand.) But eventually you'd hit one of those numbers again, which would start a cycle, since x(n+1) is always going to be the same given x(n). Now, you could use different P, Q, and X(1) values, which all have their own cycles and oddities (as 2, 99, 5 did above). You can make Q high enough, and with Q prime can end up with some fairly long non-repeating cycles. But as soon as you repeat a number, you're in a cycle.
One way to avoid this is to make the new number dependant on the previous TWO numbers, as such:
x(n+1) = (x(n)*(x(n-1)^2) + p) mod q
Thus the conditions required to intiate a cycle are much more difficult to achieve, but could happen eventually. (This time, you'd get into a cycle as soon as any two-number sequence repeats.)
Real generators use a more complex function than just squaring the number, but I just used that for simplicity. With two numbers to work with(in addition to P and Q), we can also do some more interesting things. Let's try for p = 11, q = 37, x(0) = 1, and x(1) = 27:
(1)
(27)
2
26
4
25
15
22
36
13
25 (GASP! A repeat!)
20 (But the next number is different!)
27 (Another repeat)
31 (But things are different again)
31
4
Also note that 31 repeated there. If a number repeated in the one-previous equation, it would just keep repeating (a 1-cycle). The problem is, you'd probably eventually hit a two-number cycle again. Solutions to this are to either continually increase the number of previous terms used (which require more seeds and more computation), or to simply use a Q value high enough that any cycle would be millions or billions of numbers long, or a combination of both.
The modulus arithmetic used in random number generators makes it difficult to reverse-engineer an equation just by looking at the random numbers generated for a given seed. Note in C and other languages, the random number function returns an integer, not a [0..1] float, which you then can MOD by whatever range of random numbers you need.
Also note that P and Q aren't "seeds", they're parameters in the function. The only seed(s) are pre-set X(n) values used before the first number is generated.
EDIT: Ok, I wrote a small program. First the code:
Code: Select all
dim as ulongint p, q, x0, x1, xn, num
print "Random Number Test Generator by Xerol"
print "Using equation x(n) = ((x(n-1)*(x(n-2)^2) + p) mod q"
input "Value to use for p:", p
input "Value to use for q:", q
input "Seed #1 (x(0)):", x0
input "Seed #2 (x(1)):", x1
input "Number of numbers to generate:", num
open "random.txt" for output as #1
print #1, "P = "; p
print #1, "Q = "; q
print #1, "x0 = "; x0
print #1, "x1 = "; x1
print #1, "Generating "; num; " numbers using above parameters."
for n = 1 to num
xn = (x0*(x1^2)+p) mod q
print xn
print #1, xn
x0 = x1
x1 = xn
next n
sleep
Now the output:
Code: Select all
P = 101
Q = 2538213
x0 = 300295
x1 = 1828216
Generating 500 numbers using above parameters.
2395437
2495048
584393
717526
2138110
394008
582479
312317
932809
954598
1958796
(List truncated for sake of space. I'll upload the file later.)
One good test of how well a random number generator works is to show a distribution of the numbers it outputs. So, we'll do a histogram. I divided the interval of [0..q] into 800 parts, and plotted a histogram:
500 numbers isn't a good indicator of how well a generator does. Let's try 500000 points:
That doesn't look too good. There's obvious peaks and valleys. Maybe it's just the seeds. Let's try with x0 = 29392:
The distribution is nearly identical. So this equation isn't that great. Generally, though, you want to keep the (crap + p) mod q format. Crap just needs to be different.
(I think this is a pretty good start on a Random Number Generation article for QBXP. I might just write it.)
Ok, I just tried different numbers, same equation. Got slightly better results:
This is with:
p = 101
q = 2530887
x0 = 2939212
x1 = 1821623
For 500,000 iterations. The choice of Q seems to be the driving factor here. So maybe it isn't such a bad formula after all.
If you need music composed in MP3, WAV, or MIDI format, please contact me via email.
Xerol's Music - Updated Regularly!
Xerol's Music - Updated Regularly!
You missed my point or missunderstood me..matt2jones wrote:
Of course it can return a number more then once! If you roll a dice 27 you get each number more then once, that's still a random number generator.
What I ment was there is no repitition of the pattern, eg.
int(rnd*2) -> 1 0 1 0 1 0 1 0
Where there is a pattern in the random numbers.
matt
A random number generator has to restart at some point.. everything has to restart, or end.. it's just a universal truth.. Nothing lasts forever
So a RNG would repeat at some point...
Also, making an RNG that spits out 1 or 0 is easy, way easier than making a "proper" one that spits out.. oh.. 32bit numbers
Here's a RNG I made a while ago:
Code: Select all
function getRND (precission as uinteger = 703) as single
static lastnum as single
dd = (((timer*1000) mod 255000)) mod 65536
aa! = dd
aa! = aa! mod precission
aa! = aa! / precission+lastnum
while aa! > 1
aa!=aa!-1
wend
lastnum = aa!
getRND = aa!
end function
I have left this dump.
Wow, I appreciate hte effort you guys put in. Something really interesting caught my attention though: When I helped that guy on the vampire numbers program I decided to plot the pixel at the location (mul1, mul2) when the 2 created a vampire number. What I got was a seemingly random pattern that did generate some obvious dead spots, for some unnkown reason, usally in the shape of curves. Here's the code:
Weird right? Im no big math guy, so I have little a clue as to whether or not there's a method to this. At any rate I thought this just might fit under the catgory of chaos, maybe?
Code: Select all
DECLARE FUNCTION num$ (nm&)
SCREEN 12
FOR mul1% = 1 TO 4096
FOR mul2% = 1 TO 4096
mstr$ = num$(CLNG(mul1%) * CLNG(mul2%))
nstr$ = mstr$
m1$ = num$(CLNG(mul1%)): m2$ = num$(CLNG(mul2%))
f% = 0
FOR i% = 1 TO LEN(m1$)
test% = INSTR(nstr$, MID$(m1$, i%, 1))
IF test% <> 0 THEN
MID$(nstr$, test%, 1) = SPACE$(1)
f% = f% + 1
ELSE
EXIT FOR
END IF
NEXT i%
FOR i% = 1 TO LEN(m2$)
test% = INSTR(nstr$, MID$(m2$, i%, 1))
IF test% <> 0 THEN
MID$(nstr$, test%, 1) = SPACE$(1)
f% = f% + 1
ELSE
EXIT FOR
END IF
NEXT i%
IF f% = LEN(m1$) + LEN(m2$) THEN
'PRINT mstr$ + "," + m1$ + "," + m2$
'SLEEP
PSET (VAL(m1$) / 10 - 1, VAL(m2$) / 10 - 1), 15
END IF
NEXT mul2%
NEXT mul1%
FUNCTION num$ (nm&)
num$ = RIGHT$(STR$(nm&), LEN(STR$(nm&)) - 1)
END FUNCTION
C:\DOS
C:\DOS\RUN
RUN\DOS\RUN
C:\DOS\RUN
RUN\DOS\RUN
Well, there's plenty of things that fall under "chaos" that wouldn't be suitable for a random number generator. Most single-prior-term systems fall under that. Take the quadratic iterator for example:
For x(n) in [0..1] and a = [0..4].
Most notably the case for a = 4. This produces rather chaotic behavior, but the distribution of points makes it very poor for a random number generator, and also around certain values the next value is nearly identical. Here's a graph of 400 iterations:
Also note for various 'a' values you get a different possible range of "final" states. The following is a graph of a = [1..4] (1 being on the left, 4 on the right) and all states of x(n) for n = [100..10000]:
There's a ton of interesting crap you can do with this, but it's not really relevant. (Note that for a > 4 all values eventually diverge from [0..1] and for a < 1 they all go to 0.)
The point I'm trying to make, though, is that chaos doesn't necessarily mean random. Some functions give the illusion of randomness (as the quadratic iterator does if you just looked at a list of values of x(n)) but in reality have distinct patterns that add interesting qualities while still retaining chaotic elements.
Code: Select all
x(n+1) = a*x(n)*(1-x(n))
Most notably the case for a = 4. This produces rather chaotic behavior, but the distribution of points makes it very poor for a random number generator, and also around certain values the next value is nearly identical. Here's a graph of 400 iterations:
Also note for various 'a' values you get a different possible range of "final" states. The following is a graph of a = [1..4] (1 being on the left, 4 on the right) and all states of x(n) for n = [100..10000]:
There's a ton of interesting crap you can do with this, but it's not really relevant. (Note that for a > 4 all values eventually diverge from [0..1] and for a < 1 they all go to 0.)
The point I'm trying to make, though, is that chaos doesn't necessarily mean random. Some functions give the illusion of randomness (as the quadratic iterator does if you just looked at a list of values of x(n)) but in reality have distinct patterns that add interesting qualities while still retaining chaotic elements.
If you need music composed in MP3, WAV, or MIDI format, please contact me via email.
Xerol's Music - Updated Regularly!
Xerol's Music - Updated Regularly!
while were on random numbers lets talk ranges again
a normal range thing is
x = int(rnd * x) +1 or without the +1
such as if i want a range from 0 to 200
i do
x = int(rnd * 200) or x = int(rnd *200)+1
what if i want a range of -200 to +200
how do i do that? as i dont see how to generate
a negative number in the same statement along
with a positive.....these would be coordinates
for placing objects on a map thats 400 x 400
but uses 0,0 in the center rather then the corner
of the map...
a normal range thing is
x = int(rnd * x) +1 or without the +1
such as if i want a range from 0 to 200
i do
x = int(rnd * 200) or x = int(rnd *200)+1
what if i want a range of -200 to +200
how do i do that? as i dont see how to generate
a negative number in the same statement along
with a positive.....these would be coordinates
for placing objects on a map thats 400 x 400
but uses 0,0 in the center rather then the corner
of the map...
You'd either want to do int((rnd-.5)*400) or int(rnd*400) - 200, both of which give you [-200, 199] ranges.
If you need music composed in MP3, WAV, or MIDI format, please contact me via email.
Xerol's Music - Updated Regularly!
Xerol's Music - Updated Regularly!
- matt2jones
- Veteran
- Posts: 80
- Joined: Sat Feb 19, 2005 8:29 am
- Location: elsewhere
- Contact:
Riiiight....
The chaotic function I was talking about was somewhere in the realm of
F(x) = Asinx + Bsinx
Where A/B is an irrational number.
I'm not sure if that can even be replicated on a computer (cause of the irrational number bit), but I have heard (from a mathematician, not a programmer) that the function is not periodic, so there are no patterns in the results...
It's not an iterative process (I think...), so it doesn't fall down there, but I do recognise that it's impossible to pass an X of larger then, say 64 bits, which would mean it would appear to wrap around again, but that's not the algorithms fault, it the computers ...
I don't really know what I'm talking about here, I'm just repeating what I heard cause I thought it was interesting though...
How about just spitting out 32 1's or 0's at a time
matt
The chaotic function I was talking about was somewhere in the realm of
F(x) = Asinx + Bsinx
Where A/B is an irrational number.
I'm not sure if that can even be replicated on a computer (cause of the irrational number bit), but I have heard (from a mathematician, not a programmer) that the function is not periodic, so there are no patterns in the results...
It's not an iterative process (I think...), so it doesn't fall down there, but I do recognise that it's impossible to pass an X of larger then, say 64 bits, which would mean it would appear to wrap around again, but that's not the algorithms fault, it the computers ...
I don't really know what I'm talking about here, I'm just repeating what I heard cause I thought it was interesting though...
making an RNG that spits out 1 or 0 is easy,way easier than making a "proper" one that spits out.. oh.. 32bit numbers
How about just spitting out 32 1's or 0's at a time
matt
Do not mistake Apathy for feeling Content.
http://www.disjointed.cjb.net - Short Storys
http://matt2jones.deviantart.com - Random Art
http://www.freewebs.com/matt2jones - WebComic
http://www.disjointed.cjb.net - Short Storys
http://matt2jones.deviantart.com - Random Art
http://www.freewebs.com/matt2jones - WebComic
Random Numbers and Cryptography
The subject of random numbers has certainly generated a bunch of interest here. This subject and that of cryptography is a passing interest of mine. I wish I had more time to explore!
Bruce Schneirer, in his book "Applied Cryptography, 2nd Edition" describes MANY methods of generating random numbers. Other methods can be found in "Numerical Recipes" by ...what's his name... Also, Donald Knuth has a bunch of stuff on this.
My recent areas of interest here are with LFSR's (Linear Feebback Shift Registers) and Fibinocci generators which are based on the famous sequence from math class.
I have links to a few web sites that discuss randomness and genereators (as well as DOS and BASIC related sites) on my bookmark page at
http://www.chibardun.net/~zim/bookmark.htm#CryRan
I'll be back!
Bruce Schneirer, in his book "Applied Cryptography, 2nd Edition" describes MANY methods of generating random numbers. Other methods can be found in "Numerical Recipes" by ...what's his name... Also, Donald Knuth has a bunch of stuff on this.
My recent areas of interest here are with LFSR's (Linear Feebback Shift Registers) and Fibinocci generators which are based on the famous sequence from math class.
I have links to a few web sites that discuss randomness and genereators (as well as DOS and BASIC related sites) on my bookmark page at
http://www.chibardun.net/~zim/bookmark.htm#CryRan
I'll be back!