Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Random numbers

  1. Sep 18, 2006 #1
    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. jcsd
  3. Sep 18, 2006 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  4. Sep 18, 2006 #3
    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
     
  5. Sep 19, 2006 #4

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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
     
  6. Sep 24, 2006 #5

    jim mcnamara

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  7. Sep 24, 2006 #6

    rcgldr

    User Avatar
    Homework Helper

    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.
     
  8. Sep 25, 2006 #7

    chroot

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
     
  9. Sep 25, 2006 #8

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Alternately, the process of determining the nth digit of pi is just a complicated but determanistic hash function. :biggrin:
     
  10. Sep 25, 2006 #9

    chroot

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
     
  11. Sep 25, 2006 #10

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  12. Sep 25, 2006 #11

    chroot

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You lost me there. What are you talking about?

    - Warren
     
  13. Sep 25, 2006 #12

    George Jones

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  14. Sep 25, 2006 #13

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Exactly, thanks for the explanation.
     
  15. Sep 25, 2006 #14

    chroot

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Heh, of course.

    - Warren
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Random numbers
  1. C++ random numbers! (Replies: 3)

Loading...