Exploring the Production and Use of Random Numbers in C++

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

 

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

 

[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

 

[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

 

[jim mcnamara]

Using CRG's example, a seed sets the "old state" to a beginning value -

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.

 

[rcgldr]

Can random numbers be produced by computers?

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.

 

[chroot]

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.

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

 

[CRGreathouse]

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.

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

 

[chroot]

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

 

[CRGreathouse]

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.

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 2¹⁰ = 1024 bits of memory can choose not
$$2^{10}=1.024e3$$
starting places but
$$2^{2^{10}}\approx1.798e308$$
starting places.

 

[chroot]

$$2^{10}=1.024e3$$
starting places but
$$2^{2^{10}}\approx1.798e308$$
starting places.

You lost me there. What are you talking about?

- Warren

 

[George Jones]

You lost me there. What are you talking about?

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.

 

[CRGreathouse]

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.

Exactly, thanks for the explanation.

 

[chroot]

Heh, of course.

- Warren