Random Numbers

If you have questions about any aspect of QBasic programming, or would like to help fellow programmers solve their problems, check out this board!

Moderators: Pete, Mods

User avatar
Zamaster
Veteran
Posts: 174
Joined: Wed Jun 15, 2005 1:51 pm
Contact:

Random Numbers

Post by Zamaster » Mon Nov 07, 2005 6:18 pm

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

Guest
Veteran
Posts: 128
Joined: Sun Aug 14, 2005 8:33 pm
Location: Forest Lake, MN
Contact:

Post by Guest » Mon Nov 07, 2005 6:44 pm

Look at the FB compilers source code...

moneo
Veteran
Posts: 451
Joined: Tue Jun 28, 2005 7:00 pm
Location: Mexico City, Mexico

Post by moneo » Mon Nov 07, 2005 8:06 pm

Are you looking for something other than the RND function in QB for generating random numbers?
*****

User avatar
{Nathan}
Veteran
Posts: 1169
Joined: Thu Aug 19, 2004 6:08 pm
Location: The wetlands of central Ohio, USA
Contact:

Post by {Nathan} » Mon Nov 07, 2005 8:33 pm

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...
Image

User avatar
{Nathan}
Veteran
Posts: 1169
Joined: Thu Aug 19, 2004 6:08 pm
Location: The wetlands of central Ohio, USA
Contact:

Post by {Nathan} » Mon Nov 07, 2005 9:08 pm

Also, just to elabortate on my last post, the TIMER is not "special" to the RANDOMIZE statement, it treats it like any other integer. Just thought that could clear up some confusion.
Image

User avatar
matt2jones
Veteran
Posts: 80
Joined: Sat Feb 19, 2005 8:29 am
Location: elsewhere
Contact:

Post by matt2jones » Tue Nov 08, 2005 3:59 am

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
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

Z!re
Veteran
Posts: 887
Joined: Wed Aug 04, 2004 11:15 am

Post by Z!re » Tue Nov 08, 2005 7:01 am

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..
I have left this dump.

Macric
Coder
Posts: 34
Joined: Fri Mar 25, 2005 11:11 pm
Location: Mexico

Re: Random Numbers

Post by Macric » Tue Nov 08, 2005 7:25 am

Zamaster wrote: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

User avatar
matt2jones
Veteran
Posts: 80
Joined: Sat Feb 19, 2005 8:29 am
Location: elsewhere
Contact:

Post by matt2jones » Tue Nov 08, 2005 8:05 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
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

Z!re
Veteran
Posts: 887
Joined: Wed Aug 04, 2004 11:15 am

Post by Z!re » Tue Nov 08, 2005 10:39 am

matt2jones wrote:
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
That is impossible, if you have a finite amount of numbers, you will wrap around and repeat at some point..

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.

User avatar
matt2jones
Veteran
Posts: 80
Joined: Sat Feb 19, 2005 8:29 am
Location: elsewhere
Contact:

Post by matt2jones » Tue Nov 08, 2005 10:58 am

:shock:

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

User avatar
Zamaster
Veteran
Posts: 174
Joined: Wed Jun 15, 2005 1:51 pm
Contact:

Post by Zamaster » Tue Nov 08, 2005 12:19 pm

Believe me, I am well aware of how to use the TIMER and RANDOMIZE and RND statements. I was just curious to know why random number generators work the way they do and which ones work best, ect...
C:\DOS
C:\DOS\RUN
RUN\DOS\RUN

User avatar
Xerol
Veteran
Posts: 81
Joined: Tue Jan 04, 2005 6:27 pm
Location: Timonium, MD
Contact:

Post by Xerol » Tue Nov 08, 2005 12:25 pm

matt2jones wrote::shock:

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:

Image
500 numbers isn't a good indicator of how well a generator does. Let's try 500000 points:
Image
That doesn't look too good. There's obvious peaks and valleys. Maybe it's just the seeds. Let's try with x0 = 29392:
Image
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:

Image

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!

Z!re
Veteran
Posts: 887
Joined: Wed Aug 04, 2004 11:15 am

Post by Z!re » Tue Nov 08, 2005 2:16 pm

matt2jones wrote::shock:

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
You missed my point or missunderstood me..

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 :P

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
It was just an experiment of how a RNG could look.. Also, how well it would work with a TIMER involved..
I have left this dump.

User avatar
Zamaster
Veteran
Posts: 174
Joined: Wed Jun 15, 2005 1:51 pm
Contact:

Post by Zamaster » Tue Nov 08, 2005 6:26 pm

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:

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
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?
C:\DOS
C:\DOS\RUN
RUN\DOS\RUN

User avatar
Xerol
Veteran
Posts: 81
Joined: Tue Jan 04, 2005 6:27 pm
Location: Timonium, MD
Contact:

Post by Xerol » Tue Nov 08, 2005 7:59 pm

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:

Code: Select all

x(n+1) = a*x(n)*(1-x(n))
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:

Image

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]:
Image

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!

User avatar
sid6.7
Veteran
Posts: 318
Joined: Tue Jun 21, 2005 8:51 am
Location: west USA
Contact:

Post by sid6.7 » Tue Nov 08, 2005 8:50 pm

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...

User avatar
Xerol
Veteran
Posts: 81
Joined: Tue Jan 04, 2005 6:27 pm
Location: Timonium, MD
Contact:

Post by Xerol » Tue Nov 08, 2005 8:56 pm

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!

User avatar
matt2jones
Veteran
Posts: 80
Joined: Sat Feb 19, 2005 8:29 am
Location: elsewhere
Contact:

Post by matt2jones » Wed Nov 09, 2005 7:47 am

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 :wink: ...

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 :D

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

Zim

Random Numbers and Cryptography

Post by Zim » Fri Dec 02, 2005 12:52 pm

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!

Post Reply