# Random numbers

1. Sep 18, 2006

### kant

Can random numbers be produced by computers? In c++, you have functions like rand(), srand(), time(0) that more or less extract series of random numbers from a random number table. How do people produce the table in the first place?

2. Sep 18, 2006

### CRGreathouse

Detrmanistic machines cannot produce truly random numbers; they produce pseudorandom numbers. Usually these are based on congruences from an earlier internal state, seeded by the clock.

'Hardware random' information can be obtained for special purposes.

3. Sep 18, 2006

### kant

can you clarify these two points:

Usually these are based on congruences from an earlier internal state, seeded by the clock.

and

'Hardware random' information

thanks

4. Sep 19, 2006

### CRGreathouse

Hardware randomness is like hooking your comoutr up to a Geiger counter and a radioactive source -- you're just sending it real random bits.

The pseudorandom number generator often works like this:

new state = ((old state * big number) modulo (other number)) + large number

5. Sep 24, 2006

### Staff: Mentor

Using CRG's example, a seed sets the "old state" to a beginning value -
Code (Text):

old state = seconds since Jan 1 1970 + process id
new state = ((old state * big number) modulo (other number)) + large number

Hardware randomness uses arbitrary "events" in an operating system based on low-level computer hardware activity as a basis for creating a stream of bits. google for Matt Blaze's truerand program as an attempt at this sort of thing.

6. Sep 24, 2006

### rcgldr

There are algorithms to generate the "nth" digit of pi, the sequence would repeat unless "n" were stored and continued to be incremented each time the generator was used.

7. Sep 25, 2006

### chroot

Staff Emeritus
This almost sounds paradoxical at first: the concept of using a discrete computer to "look into" the depths of pi and pull out truly random numbers. There are theorems which should prevent this kind of true randomness from ever coming from a determistic computer.

The resolution of the paradox is to realize that the initial seed value -- the index n into pi with which your generator begins -- is not truly random, but only psuedorandom.

Viewed in this light, pi is nothing more than a giant table of truly random numbers, computed on-demand, and the hard part of the problem is picking a truly random n to start reading it. Since no computer will ever be able to choose a truly random starting n, the resulting algorithm's output is still not truly random.

- Warren

8. Sep 25, 2006

### CRGreathouse

Alternately, the process of determining the nth digit of pi is just a complicated but determanistic hash function.

9. Sep 25, 2006

### chroot

Staff Emeritus
There's also a pigeon-hole problem here: a computer with 2^10 bits of memory, for example, can only choose one of 2^10 different starting points for n. It would be impossible for a computer of finite memory capacity to truly explore ALL of pi. This means that, at some perhaps distant time in the future, the computer will select a value for n that was previously selected.

You can do all sorts of mixing and hashing and other procedures to eliminate periodicity in the seed, but, eventually, you will always end up producing nearly random numbers. Of course, nearly random numbers are not random, though you could design a system to produce numbers to any desired degree of "randomness."

- Warren

10. Sep 25, 2006

### CRGreathouse

I agree with you that the pigeonhole principle alone means that determanistic machines can't produce randomness. Your equation is off, though. A computer with 210 = 1024 bits of memory can choose not
$$2^{10}=1.024e3$$
starting places but
$$2^{2^{10}}\approx1.798e308$$
starting places.

11. Sep 25, 2006

### chroot

Staff Emeritus
You lost me there. What are you talking about?

- Warren

12. Sep 25, 2006

### George Jones

Staff Emeritus
Consider base b numbers. How many n-digit numbers are possible?

b^n, e.g, in base 10, 10^3 3-digit numbers are possible.

Hence, 2^(2^10) 2^10-digit binary numbers are possible.

13. Sep 25, 2006

### CRGreathouse

Exactly, thanks for the explanation.

14. Sep 25, 2006

### chroot

Staff Emeritus
Heh, of course.

- Warren