how does a computer generate a random number?

[Cerberus_e]

yes... how http://forums.3drealms.com/ubbthreads/images/graemlins/eek.gif
in some programming languages you can create a random number between 0 and 1.
but a computer doesn't randomize, it's either a 0 signal or 1 signal, so how does that work?
and how is it assured that 0.1613 has as much chance than 0.6456 for example?
does it use the time of your computer? so then there is a certain interval, and if you always generate a random number on that interval, that it generates always the same number... and what if you always reset the systime before creating a random number, then you also have always the same number... correct?

...or wrong? http://forums.3drealms.com/ubbthreads/images/graemlins/grin.gif

[Lain]

in c++ you have to use the milliseconds of the time to have a random number. then multiply it so it's useful.

[rg3]

http://en.wikipedia.org/wiki/Random_number_generator

Essentially, there are two types of random number generators. The first type, pseudorandom number generators, are mathematical functions (a set of operations) that you pass a number through and returns a completelly different number. Two consecutive numbers produce two completelly different numbers.

Sometimes you want the random numbers to be different each time you run the program. A common way of achieving this is to start generating numbers (that's called setting the seed) using the number of seconds since the Epoch (January 1st, 1970 at 00:00).

Other times you want random numbers but you want to be able to repeat the process later (this is very common doing simulation with the Monte Carlo method). In this case, you can choose a fixed seed yourself and change it when apropiate.

The second type of random number generator is one based on system entrophy. Essentially, you collect data from the system (example: the last digits of the microseconds when you press a keyboard key or the number of open files) from time to time and generate random data with it. The amount of random data you can get with this method is smaller, but the numbers are really random and cannot be used in the simulation case.

Many Unix systems, for example, provide /dev/random and /dev/urandom. /dev/random is a device you can read bytes from and is "truly" random. If there's not enough random data to satisfy your request, the program is blocked until enough data is available. The later never blocks, but may not be suitable for, for example, cryptographical applications.

[Cerberus_e]

and how does for example visual basic do it?

[Rider]

I believe it was RND() but I'm not sure...

[Fragger00]

I was not pleased with the answers you got so far, so I'll explain how I believe random number generators work. I have researched this quite a bit so you should believe me and not the other people. http://forums.3drealms.com/ubbthreads/images/graemlins/tongue.gif

Essentially, computer CANNOT produce a random number. Like you said, programs are 0s and 1s that produce a exactly the same outcome each time you run them (at least in theory). If a program varies its output from one execution to the next, its because something in the external environment caused it to do so. This can be as simple as the temperature of your machine, the extra load of running multiple programs or executing programs in a different order.

While these factors can cause some kind of randomization, this generally cannot be relied upon (and never is) because there is no guaranty that these factors will produce an even distribution of unique numbers. Some other method has to be used to create randomization, again, from the external environment. One common method of randomization which is fairly accurate, depending on the medium, is taking the least significant bits of input from a device. These devices can vary. Some good examples are audio input or radio-active decay.

In previous postings, some forum members suggested using the lowest bits of the timer as good method of generating a random number. While it is true that under certain conditions this method can produce an even distribution of numbers, this method assumes that each program cycle is FAR less consistent than your computer's clock. For example, suppose your program simply outputs random numbers to the screen and you have no tasks in the background to cause resource inconsistencies. Because your program always does the exact same thing during every pass, each loop will take the same amount of time. If your processor timings are as accurate as your computer's clock, this will not result in a random number. Instead, each number will always vary by the same interval (while sometimes loosing the most significant digits). For this reason, I'm pretty sure this method is not used by statisticians.

If your microphone input has enough bits of precession (Ex: 16 bit sound versus 8 bit sound), the last few bits are probably random. This is related to some Scientific law which states that the more you know about the value of something, the less you know about how much that value is changing (or something along those lines). However, there is no guaranty that your computer has a sound card and computers that don't have sound cards can still produce "random" numbers, so this method obviously is not generally used.

Newer computers contain a device (which I think is built into the processor itself) which contains a piece of some element which has predictable rate of radio-active decay. A device measures the amount of radio-active decay from this element. Although the first few digits of decay are predictable, the last few digits will be random up till a certain date which is probably long after you are expected to live. So for your lifetime, this device will produce random numbers. However, these hardware random number generators where not available on older PCs, but older PCs were able to produce "random" numbers, so there is obviously another way that programmers came up with to produce random numbers.

OK, so here is the method that is probably used most often to generate "random" numbers. Well, I should first point out that this method isn't random, but actually "pseudo random". Pseudo random numbers are generated using a pseudo random number generator. Essentially a pseudo random number generator works like this:

- A seed is entered into a algorithm and an unrelated number is outputed.
- On the next pass, the last output is re-entered as the seed and a new unrelated number is outputed.
- Repeat the last step for the duration of the program.

Its important to note that ALL pseudo random number generators will eventually start to repeat themselves. Also, given the same seed, pseudo random number generators will always output the same results in the same order.

So now there is the problem of how to select the seed. You could ask the user for a seed, but people rarely choose a number that is random. http://forums.3drealms.com/ubbthreads/images/graemlins/tongue.gif What is most often used is the computer's time and date. This will always be a different number because FULL dates never repeat themselves. Using the time and date as the seed will ensure that your program doesn't do the same thing every time you start to run it.

Different pseudo random number generators work differently. Some sets of outputs are closer to being truly random than others. The pseudo random number generator you choose should depends on the task you use it for. Games probably don't have very good pseudo random number generators, but the ones they do use sufficiently fulfill their intended purpose. Some pseudo random number generators take multiple seeds. Some have longer periods (the number of outputs before repetition) than others.

The most common type of pseudo random number generator are linear congruential generators. This is what was probably used in Duke Nukem 3D, although I haven't looked in the source code to confirm it. If you want to know why linear congruential generators work, I quite honestly don't have an answer for you, but there is plenty of information on Google. (Be sure to brush up on your math skills.)

I hope this was the answer you were looking for.

[DudeMiester]

It's not so much a matter of if the generator is 100% random, but rather if it's random enough to do your job effecively.

[Cerberus_e]

Rider said:
I believe it was RND() but I'm not sure...



I know but my question was where for example visual basic gets his random number, not how to program it http://forums.3drealms.com/ubbthreads/images/graemlins/smile.gif I know how to program it I have used it to make dumb games in visual basic.

thanks for the long answer fragger00, I'll read it later this day, at evening, I don't have time now, it's lunchpause in school and I'm eating at home.
also thanks for researching, that was really too nice http://forums.3drealms.com/ubbthreads/images/graemlins/grin.gif

[Cerberus_e]

I read your answer now, it was really a tense answer... giving an example of a method, then saying why the method is bad, moving on to the new.... http://forums.3drealms.com/ubbthreads/images/graemlins/smile.gif
but you say using miliseconds of the time isn't good because some are skipped, but what if a program had it's own clock, as long as it runs (like psuedo random algorythms) it adds 1 to an integer, and if the integer reaches 99, it restarts with 0, so you have 100 different possibilities.
then there won't be any skipped? or do they?

also, today in maths we had to create a random number on our calculator. with RandomInt()
if you press enter then it outputs a randum number, press enter again and you have another number...
it uses probably a very bad algorithm.
because I pressed enter and it generated 76, then I pressed again and it gave 73.
later I used ther algorithm again and I had 48 and 47.
the pairs of numbers always were close, and the second a tiny little bit less.
it uses probably how much power is left in the batteries http://forums.3drealms.com/ubbthreads/images/graemlins/grin.gif

[rg3]

Probably a pseudorandom generating function, just my guess.

[Fragger00]

Rider said:
also thanks for researching, that was really too nice http://forums.3drealms.com/ubbthreads/images/graemlins/grin.gif



I didn't do the research for you. I did it previously because I was asking the same questions. ...but your welcome just as well.

[Fragger00]

Cerberus_e said:
but you say using miliseconds of the time isn't good because some are skipped, but what if a program had it's own clock, as long as it runs (like psuedo random algorythms) it adds 1 to an integer, and if the integer reaches 99, it restarts with 0, so you have 100 different possibilities.
then there won't be any skipped? or do they?



Nah, you missed what I said. Lets say your clock starts at 00 seconds. You program's loop always takes two seconds. Your first output would be 01, second would be 03, third 05, fourth 07... This of course is not random. The only way this will output a random number is if your program's cycle duration is random and significantly greater than your clock's cycle.


Cerberus_e said:
it uses probably a very bad algorithm.
because I pressed enter and it generated 76, then I pressed again and it gave 73.
later I used ther algorithm again and I had 48 and 47.
the pairs of numbers always were close, and the second a tiny little bit less.



Just because two numbers are close to the same value doesn't mean its not random. Actually, if the domain (range) is small enough, its not uncommon for two numbers to end up right next to each other. When humans are asked to pick random numbers, they often pick numbers that are far from each other, but this isn't random. You must unlearn what you have learned. The caculator is probably outputting a pretty good random numbers.

[Cerberus_e]

just saw this:
http://www.vbexplorer.com/VBExplorer/random/random_numbers_1.asp

I'm going to create a program that generates 10000 random numbers from 1 to 100, and I'll make a statistic http://forums.3drealms.com/ubbthreads/images/graemlins/smile.gif it interesses me.

results will be posted here

EDIT: that url is interesting, it explains that visual basic has 1 million of pre-built number from [0, 1[
too bad tutorial 2 and 3 don't work

[Cerberus_e]

ok, took me 15 minutes to create a program.
but first you should read this:
visual basic uses random numbers by going through a list of a million possible numbers, it will follow the same list each time you run the program.
unless you use randomize(), then the starting point of that list will be randomized using a complex algorithm.
so if randomize turns out to be 113 then rnd will start at 113, then 114, then 115, ...
if you don't use randomize it will start at 1, 2, 3, ...
I have made 6 statistics:
1) generate 10 000 numbers from 1 to 100, with using randomize() only 1 time at the start
2) generate 10 000 numbers from 1 to 100, with using randomize() each time before I use rnd(), so the starting point is always different
3) generate 10 000 numbers from 1 to 100 without using randomize() at all, so it starts at the beginning of the list.

then I thought: there are 1 million different possibilities, so what if I use 1 000 000 different numbers from 1 to 100?

4) generate 1 000 000 numbers from 1 to 100, with using randomize() only 1 time at the start
5) generate 1 000 000 numbers from 1 to 100, with using randomize() each time before I use rnd(), so the starting point is always different
6) generate 1 000 000 numbers from 1 to 100 without using randomize() at all, so it starts at the beginning of the list AND GOES THROUGH THE WHOLE LIST.

results going to be posted here, the results are like this:
amount * value from [1, 100]
so 105 * 73 means that the number 73 is generated 105 times

[Cerberus_e]

1) generate 10 000 numbers from 1 to 100, with using randomize() only 1 time at the start

PS: it's not the first time 73 is generated 105 times

[Cerberus_e]

2) generate 10 000 numbers from 1 to 100, with using randomize() each time before I use rnd(), so the starting point is always different

it's obvious that it gives better results, all around the 100 as it should be (100 times 100 = 10 000)

[Cerberus_e]

3) generate 10 000 numbers from 1 to 100 without using randomize() at all, so it starts at the beginning of the list.

the other results are going to take 5 mins, it takes forever to go through a loop of a million

[Cerberus_e]

4) generate 1 000 000 numbers from 1 to 100, with using randomize() only 1 time at the start

didn't took as long as I thought http://forums.3drealms.com/ubbthreads/images/graemlins/smile.gif

[Cerberus_e]

5) generate 1 000 000 numbers from 1 to 100, with using randomize() each time before I use rnd(), so the starting point is always different

again more accurate than 4, but took longer because of all the randomizing (1 million times)

[Cerberus_e]

6) generate 1 000 000 numbers from 1 to 100 without using randomize() at all, so it starts at the beginning of the list AND GOES THROUGH THE WHOLE LIST.

for a million loops it went pretty quick
*hugs 2.6 ghz processor*

as you can see, it went through the whole list, so either that article lied about 1 million answers (there are more or less), or visual basic's integral list is unbalanced

these results probably doesn't interess many people, but it interesses me, and probably some hardcore programmers.

[Fragger00]

Cerberus_e said:
that url is interesting, it explains that visual basic has 1 million of pre-built number from [0, 1[



Read it closer. It's a "conceptual internal list of 1 million psuedo-random values". There isn't an actual list of "random" values. It just means VB has the ability to always regenerate those exact values.

[Cerberus_e]

how come you always have the same results then if you don't use randomize?

[DudeMiester]

The psudo-random functions that are used by VB, C++ and other languages are iterative functions. That is you start with an inital value, the seed, and the function transforms that number. I returns the result, and also stores it internally, so that the next time you ask for a random number, it performs the mathematical transformation on the stored [previous] value, and remember the new results. So on and so fourth.

The seed will usually default to 1, unless you call Randomize() or srand() etc... What this function does is to change the seed, usually to the date in milliseconds, but you can also specifiy a value. Note, the date used by computers is the number of milliseconds since some point in the 70s or something, when they started using this system. You can look it up.

Here is an example of a psudo-random generator called the Mersainne Twister:

/* Period parameters */
#define N 624
#define M 397
#define MATRIX_A 0x9908b0dfUL /* constant vector a */
#define UPPER_MASK 0x80000000UL /* most significant w-r bits */
#define LOWER_MASK 0x7fffffffUL /* least significant r bits */

static unsigned long mt[N]; /* the array for the state vector */
static int mti=N+1; /* mti==N+1 means mt[N] is not initialized */

/* initializes mt[N] with a seed */
void init_genrand(unsigned long s)
{
mt[0]= s & 0xffffffffUL;
for (mti=1; mti<N; mti++) {
mt[mti] =
(1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
/* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
/* In the previous versions, MSBs of the seed affect */
/* only MSBs of the array mt[]. */
/* 2002/01/09 modified by Makoto Matsumoto */
mt[mti] &= 0xffffffffUL;
/* for >32 bit machines */
}
}

/* generates a random number on [0,0xffffffff]-interval */
unsigned long genrand_int32(void)
{
unsigned long y;
static unsigned long mag01[2]={0x0UL, MATRIX_A};
/* mag01[x] = x * MATRIX_A for x=0,1 */

if (mti >= N) { /* generate N words at one time */
int kk;

if (mti == N+1) /* if init_genrand() has not been called, */
init_genrand(5489UL); /* a default initial seed is used */

for (kk=0;kk<N-M;kk++) {
y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1UL];
}
for (;kk<N-1;kk++) {
y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1UL];
}
y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1UL];

mti = 0;
}

y = mt[mti++];

/* Tempering */
y ^= (y >> 11);
y ^= (y << 7) & 0x9d2c5680UL;
y ^= (y << 15) & 0xefc60000UL;
y ^= (y >> 18);

return y;
}

Note, this is an advanced generator, the actual ones used in VB and C++ are much simpler.

[Night Hacker]

Cerberus_e said:
how come you always have the same results then if you don't use randomize?




When you use a random number generator it takes a seed value that you give it, in C you use the function srand() to seed the generator. The generator then performs some complex calculations to produce a different number every time you use rand().

If you use the same seed value, you will get the same series of numbers.

A good seed value I usually use in my games is the current time. It is always changing so you get sufficient random (unpredictable) results.

Probably one of the best examples I have seen of using a random number generator was in the game ELITE. Due to the lack of storage space etc... back when Elite was created they came up with an excellent way to create a huge universe with a single number! They used the same seed value for their built in random number generator and it generated the same universe each time the program was run.

Anothe game called Modem Wars used seed values to generate levels you played. It asked you to imput letters which meant you could use a word that was easily remembered, converted those characters to a seed value and generated a map with it. If you used the same word (seed) you got the same map. No need to save a map.

I plan on using this idea in a game of my own in the future.