Random Number Generation -----> Hardware or Software?

"Vadim Borshchev" <vadim.borshchev@127.0.0.1> wrote in message
news:opsm4huyury1ubid@news...
> On 4 Mar 2005 07:42:36 -0800, Motaz K. Saad <motsad@yahoo.com> wrote:
>
> > Is random number generation function/method in programming languages
> > implemented in software layer or in hardware layer [...]
>
> Note also that these (software) library functions generate *pseudo-random*
> sequences.  True random sequences are impossible to be achieved by solely
> software means.

A compromise is to use the accurate timing of keystrokes. The number of
keystrokes
must be carfully determined to get the proper amount of randomness.

More wetware than hardware ;-)

Wim

Del Cecchi wrote:
> Motaz K. Saad wrote:
> 
>> Hi every one,
>> I would like 2 ask about the random number generation.
>> Is random number generation function/method in programming languages
>> implemented in software layer or in hardware layer, and if it is
>> implemented in software layer, how it is implemented in the regular
>> calculator i.e. pocket calculator (not calculator program).
>> thanx
>>
> 
> Actually there are no software random number generators.  Generating 
> random numbers is very difficult.

"Generating random numbers is too important to be left to chance".

(Knuth?)
...
I found a ref: http://www.c2i.ntu.edu.sg/resources/aipages/aiquotes.html

The generation of random numbers is too important to be left to chance. 
-- R.R. Coveyou

Terje

-- 
- <Terje.Mathisen@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"

"Motaz K. Saad" wrote:
> 
> I would like 2 ask about the random number generation.
> Is random number generation function/method in programming languages
> implemented in software layer or in hardware layer, and if it is
> implemented in software layer, how it is implemented in the regular
> calculator i.e. pocket calculator (not calculator program).

Software.  The most common (and one of the simplest) is the linear
congruential type, which implements:

   R(n+1) = (R(n) * K1 + K2) modulo K3

and the seeding process sets R(n).  The magic is in picking the
various K's, which can result in fairly good or very bad pseudo
random sequences.  Knuth has a thorough discussion.  A more complex
system is the Mersenne Twister.  You can google for that, or find
an implementation (used for testing) within my hashlib package at:

  <http://cbfalconer.home.att.net/download/hashlib.zip>

-- 
"If you want to post a followup via groups.google.com, don't use
 the broken "Reply" link at the bottom of the article.  Click on 
 "show options" at the top of the article, then click on the 
 "Reply" at the bottom of the article headers." - Keith Thompson

"Nick Maclaren" <nmm1@cus.cam.ac.uk> wrote

> Del Cecchi <cecchinospam@us.ibm.com> writes:
> > 
> > Actually there are no software random number generators.  

Agreed.  Randomness _can't_ come from a fully deterministic
system.  The main claim to fame of a computer is that it
is deterministic, unlike those unpredictable humans.

> > Generating random numbers is very difficult.

Worse than merely difficult.

Generating pure noise with no signal is the mirror task, 
and just as impossible, as generating signal with no noise.

> If it is impossible to determine that a generator is not truly
> random without invoking godlike powers, 

God does not play dice with the universe -> God _is_ the dice.

> is it random?

All one can do is try and prove it isn't random and fail.

> Therefore, if it is infeasible to determine that a black-box
> pseudo-random generator is not truly random without breaking
> open the black box, should it be regarded as random?

It is not only feasible, it is dead-nuts easy to determine that 
a black-box is outputting pseudo-random data.  Map the PRNG output
on a CRT and you will soon see pattern evolving on the screen.
Use the last digit to increment/decrement a line sweeping across
the screen: the last digit will have a repeat to it that is much
shorter than the repeat of the whole generator and the line
will not slowly go up or down, it will _always_ stay around '0'.
Count the frequency of same value strings (# of 1's, 11's, 111's...
0's, 00's, 000s), the numbers will be just _too_ perfect.

A dead give-away is PRNG's don't drift or have biases.

The first chapter of Knuth Vol 2 "Seminumerical Algorithms", 
all 170 pages of it, is dedicated to determining if a set of
data is random.

Truly random _isn't_, you just can't predict how it isn't.
Somewhere in a truly random string there exist the works of
Shakespeare: it they aren't there then the string does not
contain all possible sequences and is therefore not random.

> You can ask exactly the same about a quantum state.
What is the question?
> If you answer "yes" and "no" to the above, 
In the sprit of the post, let's answer both yes and no
and wait for the wave function to collapse.

> then physical randomness would disappear if anyone ever
> found a way of measuring a quantum state directly, 
> however impractical.

Interaction with quantum events is what _creates_ randomness.  
You _can't_ make physical randomness disappear.  You can 
not predict the behavior of a physical system except in 
general terms and short time frames.

If you can make physical randomness disappear then look
out: you are simulation in some giant computer.

> The philosophy of randomness is a lot more complex than most
> people realize.

Infinitely complex.  When randomness runs it's course the 
Universe ends.

Home Study Question: Are the digits of the square root of 
                     two random?

-- 
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer:  Electronics; Informatics; Photonics.
To reply, remove spaces: n o lindan at ix  . netcom . com
psst.. want to buy an f-stop timer? nolindan.com/da/fstop/

David Magda wrote:
> Del Cecchi <cecchinospam@us.ibm.com> writes:
> 
> 
>>Actually there are no software random number generators.
>>Generating random numbers is very difficult.
> 
> 
>     Anyone who considers arithmetical methods of producing random digits
>     is, of course, in a state of sin.
>         John Von Neumann, 1951       
> 

LOL.  Turing proposed that all computers have a
low-level radioactive source whose decay events
could be used as a random number generator.

"mark thomas" <marycoy4@execyulinky.comy> wrote

> The philosopy of randomness involving "godlike powers" is a futile and 
> pointless discussion at best,

One of the oldest: predestination Vs free-will.  The answer is the universe
is a combination of the two, a frightfully boring answer.

> and doesn't serve to offer any insight into 
> any practical matters.

I'll disagree.  I believe randomness is the root of intelligence 
and consciousness.  So does Penrose.

> Philosophy itself as a subject is completely useless 
> from a practical standpoint,

That's a very philosophical statement.  Thought is the only thing that
really matters, all else is in support of it.

> and I don't even know why I'm wasting my time 
> talking about it.

Because it is more enjoyable than the other tasks that await you.

Like, I need to make some cold calls -- or maybe I will clean
the kitchen floor with a toothbrush -- or maybe I will write random
posts on the philosophy of randomness.  Choices, choices ...

-- 
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer:  Electronics; Informatics; Photonics.
To reply, remove spaces: n o lindan at ix  . netcom . com
psst.. want to buy an f-stop timer? nolindan.com/da/fstop/

"David Magda" <dmagda+trace050112@ee.ryerson.ca> 
> John Von Neumann wrote:
> > Anyone who considers arithmetical methods of producing random digits
> > is, of course, in a state of sin.

As asked before, what about sqrt(two), pi, e ...?  Devil of a question.

-- 
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer:  Electronics; Informatics; Photonics.
To reply, remove spaces: n o lindan at ix  . netcom . com
psst.. want to buy an f-stop timer? nolindan.com/da/fstop/

"mark thomas" <marycoy4@execyulinky.comy> wrote
> 
> Any good random number generators that I know of rely on the system clock - 

Agreed, the randomness is supplied by the timing of the human hitting the 
keyboard and asking for a number.

The reality is a bit different however.  The result will have a constant
bias.  Interestingly, JvonN's method does not remove the bias.

JvonN's method for correcting an unfair coin:

 If 1's and 0's have a different frequency then the data can be made
 unbiased by considering only strings of 01 and 10 and removing all 
 11..1 and 00...0 strings.

I spent a few years on the electronic generation of random numbers.  It
can't be done, there is always a bias, but that in itself is part of the 
randomness of the results.  A sort of 1/f noise.

Oh, yes.  The lack of 1/f noise -- the longer the timeframe the wilder
the swings -- is one dead give-away to a prng.  A prng has a hard limit
on the length of a winning streak.

-- 
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer:  Electronics; Informatics; Photonics.
To reply, remove spaces: n o lindan at ix  . netcom . com
psst.. want to buy an f-stop timer? nolindan.com/da/fstop/

"Motaz K. Saad" <motsad@yahoo.com> wrote

> Is random number generation function/method in programming languages
> implemented in software layer or in hardware layer

In a 'programming language' random numbers are generated in software.  By
definition.

If we change the question to generation in 'systems' rather than
languages then ...

Most systems use a pseudo random number generator that is seeded 
by the system clock at the start of program execution.  If the program
is started by the system clock you may have a slight problem.

In any case the 'random numbers' coming from a computer program aren't.

Some computers, used for cryptology and monte-carlo simulation, do have
physical random number generators as a hardware accessory.  One for
a desk-top PC:

http://www.idquantique.com/qrng.html

The _really_ good ones, well they don't exist, do they ...

-- 
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer:  Electronics; Informatics; Photonics.
To reply, remove spaces: n o lindan at ix  . netcom . com
psst.. want to buy an f-stop timer? nolindan.com/da/fstop/

Nicholas O. Lindan wrote:
> "David Magda" <dmagda+trace050112@ee.ryerson.ca> 
> 
>>John Von Neumann wrote:
>>
>>>Anyone who considers arithmetical methods of producing random digits
>>>is, of course, in a state of sin.
> 
> As asked before, what about sqrt(two), pi, e ...?  Devil of a question.

Not really in the same league IMHO:

Even though all these numbers seem to consists of effectively 
unpredictable digits, strange things do happen, like the totally 
unexpected discovery of a formula that allows you to calculate an 
arbitrary hex digit in pi.

Terje
-- 
- <Terje.Mathisen@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"