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

Nicholas O. Lindan wrote:
> "Nick Maclaren" <nmm1@cus.cam.ac.uk> wrote
>>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.

Huh?

Multi-dimensional frequency checks are afaik among the standard tests 
for pseudo-random generators.

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

As opposed o the expected brownian motion?

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

drift/bias is the first thing you remove when converting some physical 
process into a real random number generator.
> 
> 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.

I.e. the infinite number of monkeys hitting keys on typewriters.

The fun part is that not only will they write Hamlet, in all living and 
dead languages expressible on said typewriter, they will also write them 
with all possible typos.

Infinity is a strange subject, pretty soon you'll start talking about 
Cantor and his Aleph (?) numbers. :-)

Terje

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

On 2005-03-04, Nicholas O. Lindan <see@sig.com> wrote:

>> Is random number generation function/method in programming languages
>> implemented in software layer or in hardware layer
>
> In any case the 'random numbers' coming from a computer program aren't.

Some desktop OSes attempt to build up a pool of random bits
from events like the timing of keypresses and netowrk traffic.

How well that works is another question.

-- 
Grant Edwards                   grante             Yow!  -- In 1962, you could
                                  at               buy a pair of SHARKSKIN
                               visi.com            SLACKS, with a "Continental
                                                   Belt," for $10.99!!

"Terje Mathisen" <terje.mathisen@hda.hydro.com> wrote
> Nicholas O. Lindan wrote:
> > "Nick Maclaren" <nmm1@cus.cam.ac.uk> wrote
> > >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.
> Huh? Multi-dimensional frequency checks are afaik among the standard tests 
> for pseudo-random generators.

Yes, and they fail them.  Have to.  They _do_ repeat, so there
is at minimum 1 periodic frequency.  Individual digits/bits have
shorter periodic cycles.

> > 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'.
> As opposed [t]o the expected brownian motion?
My turn to say 'huh?'.  Yes, it should be a random walk which if it
goes on long enough will have deviations approaching infinity.
A prng can't do that.

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

> drift/bias is the first thing you remove when converting some physical 
> process into a real random number generator.

All physical processes are random.  Any modification makes them less
random.  For our convenience, though, we put the sequence through a high-pass
filter, as it were.  You can't -remove- the bias and drift, only attenuate
it.  It comes from 1/f effects and from the defects in the generating
apparatus.  That's the key: the prng has _no_ defects.


> > 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.
> 
> I.e. the infinite number of monkeys hitting keys on typewriters.

Men make pretty good monkeys when it comes to typewriters.  If the
zipped version of Hamlet is acceptable then the monkeys will get it
done faster.

> The fun part is that not only will they write Hamlet, in all living and 
> dead languages expressible on said typewriter, they will also write them 
> with all possible typos.

Took all the random events of the universe 15 billion years to
come up with just the _one_ (AFAIK) Hamlet.  Man has been permutating
it into its many variations ever since.

Anyone remember that old sci-fi story about the ten billion names of God?

> Infinity is a strange subject, pretty soon you'll start talking about 
> Cantor and his Aleph (?) numbers. :-)

Or we could divide by zero.

It is refreshing to contemplate the Universe does have a _finite_ size
and age.

-- 
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:
> Took all the random events of the universe 15 billion years to
> come up with just the _one_ (AFAIK) Hamlet.  Man has been permutating
> it into its many variations ever since.
> 
> Anyone remember that old sci-fi story about the ten billion names of God?

Yes!

(You've committed a fence-post error though, it is The _Nine_ Billion 
Names of God, (C) 1967 A. C. Clarke

It's a beautiful short story, even though the end is somewhat obvious. :-)
> 
>>Infinity is a strange subject, pretty soon you'll start talking about 
>>Cantor and his Aleph (?) numbers. :-)
> 
> 
> Or we could divide by zero.
> 
> It is refreshing to contemplate the Universe does have a _finite_ size
> and age.

Or the inside of the black hole we're all living in fits that description?

(If the missing 90% or so 'dark matter' does exist, then the universe is 
closed and will eventually collapse. That does make it a black hole, right?)

Terje

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

"Del Cecchi" <cecchinospam@us.ibm.com> wrote
> Actually there are no software random number generators.  Generating 
> random numbers is very difficult.

Well, for a usable bit rate, yeah.  Otherwise a beta particle
detector, a little Americium, and an interval timer would do.

Fortunately, generating random numbers is rarely necessary.
Good-quality pRNG does for every application I know of,
including generating keys and nonce's for crypto apps.
--
Dennis M. O'Connor    dmoc@primenet.com 

"Terje Mathisen" <terje.mathisen@hda.hydro.com> wrote

> Or the inside of the black hole we're all living in fits that description?

I don't believe in black holes.  The 'Nine Billion Names of God' has more
ring of truth to it.

                         *     *      *

                   "One must never, ever doubt
                    What nobody is sure about."

-- 
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/

Terje Mathisen wrote:
> Huh? Multi-dimensional frequency checks are afaik among the standard tests 
> for pseudo-random generators.

"Nicholas O. Lindan" <see@sig.com> writes:
> Yes, and they fail them.  Have to.  They _do_ repeat, so there
> is at minimum 1 periodic frequency.  Individual digits/bits have
> shorter periodic cycles.

There are readily available PRNGs that operating at one output per
nanosecond would take longer than the current age of the universe
to repeat.

Any frequency check you can actually perform on them within your
lifetime will not reveal the periodic cycle.

Eric

"Jim Stewart" <jstewart@jkmicro.com> wrote in message
news:pt6dnXVJY4niIbXfRVn-hg@omsoft.com...
> 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.
>
Been there, done that.  Customers really bitched about the random soft
errors from the radioactive lead in the solder balls and the thorium in
the glass.  :-)  They wouldn't believe it was really a feature....

Random numbers require a source of entropy - like a
quantum noise source. I've made use of a cheap sound
card, no input connected, with the microphone record
gain turned to the max, to generate noise from the
quantum shot noise of the pre-amplifer input. This is
helping produce random numbers to drive the SSL key
generator for online banking systems in major European
banks :-).

However, I suspect that what you really want (if this
isn't just a homework exercise) are *unpredictable*
numbers - which is quite a different thing. Beware that
many PRNG sequence generators, notably the classic rand,
srand pair from Unix, have poor spectral chararacteristics.
This is due both the fact that they only have 32 bits of
stored state (*way* insufficient - we used 4096 *bytes*),
and use only one multiplication in the step sequence.
That means that if you know the recent numbers in the
sequence, you have a much better then expected chance of
guessing the next one.

Clifford.

In comp.arch Nicholas O. Lindan <see@sig.com> wrote:
> "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.
> 

Heres a quiz : how many digits of a random number do you need to 
definitely tell if it is random or not? 

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

wrong

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

This is even worse than wrong.

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

ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha ha

the worst thing about this is that not just will a true rng also
output images that have patterns (one day possibly all of Shakespeare's
works) but humans are very good in seeing patterns in cases where 
there isn't one.

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

This is utterly untrue. 

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

most prngs have biases. also, with a real hrng you want to
eliminate any bias it might have.

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

No finite string can do that, and we don't have enough time
to wait for the infinte ones.

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

Wrng yet again - it is the quantum events themselves that are 
(provably) random and there is no need to bring "interaction" 
into it. especially as in the end, all events are.


-- 
	Sander

+++ Out of cheese error +++