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
Well, the problem is in how most random generators work. Most of them are iterated functions. For a simple, non-random one, try this:
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
(This is for FreeBasic. A ulongint is a 64-bit unsigned integer, so you can use VERY high numbers. Use 2^64-1 as Q (whatever that is) and divide by 2^64 to get numbers in a [0..1] range like QB.)
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.)
Not sure if there's any repeats in that or not. A quick scan shows 500 seemingly random numbers, though.
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.