Random Numbers

[aj47]

I'm assuming that no mathematical formula can generate random numers so by what principle do random number generators work?.

 

Are they just approximations (e.g. using things like the time in equations that give numbers that appear random) or can truly random numbers be generated?

[ecoli]

interesting, aj. I want to hear the responses to this one.

[timo]

I think you are correct by saying that no deterministic algorithm can produce random numbers - it would be somewhat self-contradicting. Within the scope of computer sciences, one usually speaks of pseudo-random numbers. Those are numbers generated by an algorithm which are good at faking being random.

 

There are several tests that one can perform on pseudo random numbers to quantify their quality. The more primitive ones are checks on the distribution (you take a large amount of those numbers and see if their distribution over the interval you wanted to take randoms over is roughly the one you wanted) and their periodicity (the computer can only handle a finite number of different numbers therefore each infinite series has to have a periodicity - the higher the periodicity the better).

Then, there are also more sophisticated tests on the correlation between the numbers (ideal random numbers are totally uncorrelated). But I have to admit that I wouldn´t have a single definition for "correlation" in mind, atm. An interesting test is trying to compress a large number of randoms with some compressing program. Ideal randoms cannot be comressed.

 

There are methods that are thought to create "true random numbers". But those are hardware solutions. An example would be connecting the computer to a geiger counter and measuring the decay of some radioactive substance. However, while one reads about those methods from time to time, I hadn´t heard of or even seen an actual random generator working that way.

[Klaynos]

often times, at least in the past they've been bassed around the processor operation count or something like that I forget the actual term.... :|

[timo]

There is a very wide range of random generators. Quality of the random numbers usually isn´t the only criterion for chosing a certain solution. Often, the random generator deliviered with your programming language is sufficient. For some programs like computer games your prime criterion is performance, not quality of the numbers. Therefore, you´ll chose a quick solution like reading out the processor time and perhaps XORing it with something to hide the continuitivity. For scientifical programs like physics simulations, the standard random generator sometimes isn´t good enough quality-wise. So you switch to algorithm which gives sufficiently good random numbers and still is fast enough.

[1veedo]

I found a couple diferent flukes in C++ a long time ago that gave random numbers. They had something to do with creating a variable, or pulling something from memory. I don't really remember.

 

You can look at specific languages to find functions that'll give you random numbers. Most rely on the current output of something, like time.

[bascule]

Cryptographic random number generators in computers work by collecting "entropy data" which is usually some function of how often interrupts inside of the computer are tripped.

[JonM]

how does the lottery generate them?

[DV8 2XL]

http://www.lavarnd.org/

 

The LavaRnd Random Number Generator

 

LavaRnd is a cryptographically sound random number generator. At its heart, it uses a chaotic source to power the generation of very high quality random numbers.

[softdragonz]

A simple function,

 

y = f(n)x + f(m)

 

Where f(1) is the first prime no =1

f(2) is the second prime no = 2

f(4) is the fourth prime number = 5 ...

 

If we need 5 random numbers, give x a user defined value.....say 2

 

and fix m=5-n

 

The random numbers would be....(assuming f(0)=1)

 

7 , 7, 8, 9, 8

[1veedo]

Just a question, softdragnoz, what does f(x) = ?

[Pleiades]

Many times a random number algorithm will use what’s called a ‘seed’ as its input, and will generate a predictable series of numbers that is unique to each seed. The algorithm is designed so that the series produced from each seed has relatively good distribution and periodicity. The seed is usually chosen by reading some value within the computer, such as the system time in milliseconds.

[softdragonz]

Just a question, softdragnoz, what does f(x) = ?

 

oops i spilled the beans.....

 

isn't there any series that can generate prime numbers.....if there is any such series, the series by itself would be a random number generator .... as prime numbers are random

 

BTW: can't we assume sin(x) to be a random no generator??? It generates random nos between -1 and 1 through an infinite series

[aj47]

Very interesting, thanks for the responses.

 

So all of these tecniques generate psuedo random numbers

with the exception of the use of atomic radioation, right?

 

This got me thinking, do you think that there is underlying order in every aspect of nature such as atomic decomposition, but becasue the order is so inistricably complex we assume its random?

[jordan]

oops i spilled the beans.....

 

isn't there any series that can generate prime numbers.....if there is any such series' date=' the series by itself would be a random number generator .... as prime numbers are random

 

BTW: can't we assume sin(x) to be a random no generator??? It generates random nos between -1 and 1 through an infinite series[/quote']

 

I would think that the point of a random number gerator would be that you put in integer values for x that are increasing by x_n=x_n-1+1 so that each x_n gerates a random number. To use the sine function to get random numbers would mean that we'd have to plug in random x's to begin with. In that case every function could be used as a random number gerator.

[softdragonz]

To use the sine function to get random numbers would mean that we'd have to plug in random x's to begin with

 

No....I don't think we need to select random x's to begin with.....for instance,

 

if we take x in radians

 

sin(1)=0.84

 

sin(2)=0.90

 

sin(3)=0.14

 

sin(4)=-0.75

 

sin(6)=-0.27

 

sin(7)=0.65

 

Multiplying the results by ten and taking the integral values, we get the numbers

 

8,9,1,-8,-3,6

 

So, though x varies linearly (not randomly) we arrived at a set of random numbers

 

The function is

 

f(x) = 10 * [sin(n)]

 

where [x] denotes interal part and n = {1,2,3.....}

[1veedo]

So you're saying no matter how many times I run

 

10 * (sin(1)) I will always get a diferent number?

 

Don't blame me for being skeptical but I dobt it.

[softdragonz]

 

10 * [sin(1)] I will always get a diferent number?

 

 

It is not 10 * [sin(1)] but it is 10 * [sin (n)] where n varies linearly....not RANDOMLY.....but the result you get may be a different number or may be a number that repeats again.....but, the numbers selected are random....It is just like throwingf a dice to select 6 no.s

[1veedo]

I'm still not getting it. If you make a program

 

for (n=0; n < 11; n++)

out 10 * (sin(x));

 

 

then the output would vary each time?

[6431hoho]

Isn't the pattern of irrational numbers random? Ex. 3.141592654...

[bascule]

Isn't the pattern of irrational numbers random?

 

pattern != random

[bascule]

If you want a simple, relatively portable entropy harvesting routine in a computer program, here's one in C:

 

#include <sys/time.h>
#include <time.h>
#include <stdio.h>
#include <limits.h>

float entr_rand(void)
{
   unsigned long base, i;
   struct timeval tv;

   gettimeofday(&tv, 0);

   base = tv.tv_sec * 1000000 + tv.tv_usec;

   for(i = 0; i < 1000000; i++);

   gettimeofday(&tv, 0);

   return (float)(tv.tv_sec * 1000000 + tv.tv_usec - base) / INT_MAX;
}

 

This is best coupled with some kind of hashing routine to improve the spread of the numbers. The amount of time it takes to execute the loop willl vary according to how often the program is scheduled by the kernel, which is dependent on the whole of the system state.

[VikingF]

I'm assuming that no mathematical formula can generate random numers so by what principle do random number generators work?.

 

Are they just approximations (e.g. using things like the time in equations that give numbers that appear random) or can truly random numbers be generated?

 

 

 

When random numbers are created by an algorithm, it isn't random, but pseudorandom. Pseudorandom means that to know the next element in a sequence is quite difficult, but even if there seems to be random, it exists a formulae that calculate what the next number should be. This is often calculated by the fomulae: X_n=aX_{n-1}+c (mod m).

[softdragonz]

I'm still not getting it. If you make a program

 

for (n=0; n < 11; n++)

out 10 * (sin(x));

 

 

then the output would vary each time?

 

 

I am not talking about (sin(x))....I am talking about [sin(x)]

 

[f(x)] stands for integral part of f(x) less than f(x)

 

For example...

 

If f(x)=3.4545345' date=' [f(x)']=3

if f(x)=1.1444 , [f(x)]=1

 

 

It is much similar to the following code

 

int m;
m=sin(10);
cout<<m;

 

Though sin(m) returns an irrational number....we are just taking the integral part of the result.....

 

the fuction [f(x)] is quite commonly used in mathematics

 

Correct me if there are any errors

 

for (n=0; n < 11; n++)
   cout<< 10 * ((int)sin(x));

 

will indeed give you random numbers as results....they probably lie between -9 and 9

[bascule]

If you have a deterministic algorithm that produces the numbers then they are not random