Random numbers

  • Thread starter kant
  • Start date
  • #1
388
0
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?
 

Answers and Replies

  • #2
CRGreathouse
Science Advisor
Homework Helper
2,824
0
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
388
0
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
CRGreathouse
Science Advisor
Homework Helper
2,824
0
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
jim mcnamara
Mentor
4,430
3,156
Using CRG's example, a seed sets the "old state" to a beginning value -
Code:
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
rcgldr
Homework Helper
8,770
569
kant said:
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.
 
  • #7
chroot
Staff Emeritus
Science Advisor
Gold Member
10,239
39
Jeff Reid said:
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
 
  • #8
CRGreathouse
Science Advisor
Homework Helper
2,824
0
chroot said:
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. :biggrin:
 
  • #9
chroot
Staff Emeritus
Science Advisor
Gold Member
10,239
39
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
CRGreathouse
Science Advisor
Homework Helper
2,824
0
chroot said:
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 210 = 1024 bits of memory can choose not
[tex]2^{10}=1.024e3[/tex]
starting places but
[tex]2^{2^{10}}\approx1.798e308[/tex]
starting places.
 
  • #11
chroot
Staff Emeritus
Science Advisor
Gold Member
10,239
39
CRGreathouse said:
[tex]2^{10}=1.024e3[/tex]
starting places but
[tex]2^{2^{10}}\approx1.798e308[/tex]
starting places.

You lost me there. What are you talking about?

- Warren
 
  • #12
George Jones
Staff Emeritus
Science Advisor
Gold Member
7,482
1,207
chroot said:
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.
 
  • #13
CRGreathouse
Science Advisor
Homework Helper
2,824
0
George Jones said:
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.
 
  • #14
chroot
Staff Emeritus
Science Advisor
Gold Member
10,239
39
Heh, of course.

- Warren
 

Related Threads on Random numbers

  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
3
Views
3K
Replies
9
Views
1K
Replies
3
Views
8K
Replies
12
Views
2K
  • Last Post
Replies
7
Views
4K
  • Last Post
Replies
4
Views
2K
Replies
4
Views
13K
Replies
1
Views
3K
Top