Statistics: Posted by Zim — Mon Dec 05, 2005 4:57 pm
]]>
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!
Statistics: Posted by Guest — Fri Dec 02, 2005 12:52 pm
]]>
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
Statistics: Posted by matt2jones — Wed Nov 09, 2005 7:47 am
]]>
]]>
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...
Statistics: Posted by sid6.7 — Tue Nov 08, 2005 8:50 pm
]]>
Code:
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.
Statistics: Posted by Xerol — Tue Nov 08, 2005 7:59 pm
]]>
Code:
DECLARE FUNCTION num$ (nm&)SCREEN 12FOR mul1% = 1 TO 4096FOR mul2% = 1 TO 4096mstr$ = num$(CLNG(mul1%) * CLNG(mul2%))nstr$ = mstr$m1$ = num$(CLNG(mul1%)): m2$ = num$(CLNG(mul2%))f% = 0FOR i% = 1 TO LEN(m1$)test% = INSTR(nstr$, MID$(m1$, i%, 1))IF test% <> 0 THENMID$(nstr$, test%, 1) = SPACE$(1)f% = f% + 1ELSEEXIT FOREND IFNEXT i%FOR i% = 1 TO LEN(m2$)test% = INSTR(nstr$, MID$(m2$, i%, 1))IF test% <> 0 THENMID$(nstr$, test%, 1) = SPACE$(1)f% = f% + 1ELSEEXIT FOREND IFNEXT i%IF f% = LEN(m1$) + LEN(m2$) THEN'PRINT mstr$ + "," + m1$ + "," + m2$'SLEEPPSET (VAL(m1$) / 10 - 1, VAL(m2$) / 10 - 1), 15END IFNEXT mul2%NEXT mul1%FUNCTION num$ (nm&)num$ = RIGHT$(STR$(nm&), LEN(STR$(nm&)) - 1)END FUNCTIONStatistics: Posted by Zamaster — Tue Nov 08, 2005 6:26 pm
]]>
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:
function getRND (precission as uinteger = 703) as singlestatic lastnum as singledd = (((timer*1000) mod 255000)) mod 65536aa! = ddaa! = aa! mod precissionaa! = aa! / precission+lastnumwhile aa! > 1aa!=aa!-1wendlastnum = aa!getRND = aa!end functionStatistics: Posted by Z!re — Tue Nov 08, 2005 2:16 pm
]]>
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:
dim as ulongint p, q, x0, x1, xn, numprint "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:", pinput "Value to use for q:", qinput "Seed #1 (x(0)):", x0input "Seed #2 (x(1)):", x1input "Number of numbers to generate:", numopen "random.txt" for output as #1print #1, "P = "; pprint #1, "Q = "; qprint #1, "x0 = "; x0print #1, "x1 = "; x1print #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 = xnnext nsleepNow the output:
Code:
P = 101Q = 2538213x0 = 300295x1 = 1828216Generating 500 numbers using above parameters.2395437249504858439371752621381103940085824793123179328099545981958796(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.
Statistics: Posted by Xerol — Tue Nov 08, 2005 12:25 pm
]]>
]]>
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
Statistics: Posted by matt2jones — Tue Nov 08, 2005 10:58 am
]]>
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..
Statistics: Posted by Z!re — Tue Nov 08, 2005 10:39 am
]]>
All RND generators wrap around at some point, often far sooner than you might think..
The Chaotic Functions I was talking about don't, that's why I brought them up... Non-periodic or something...matt
Statistics: Posted by matt2jones — Tue Nov 08, 2005 8:05 am
]]>
Can anyone clue me in to the workings of random number generators?
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.http://support.microsoft.com/default.as ... n-us;28150
Statistics: Posted by Macric — Tue Nov 08, 2005 7:25 am
]]>
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..
Statistics: Posted by Z!re — Tue Nov 08, 2005 7:01 am
]]>