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

"Guy Macon" <http://www.guymacon.com/> wrote in message 
news:112jcib6tr8sbc6@corp.supernews.com...
>
>
>
> Bob Niland wrote:
>
>>Do many algorithmic rngs ever have two adjacent generated
>>raw numbers be identical?
>
> Happens all the time[1] when using RC4 as a PRNG.
>
>
>
> [1] (Roughly as often as it happens when using dice or coin flips...)

It should, or they're not random.  :)

"Eric Smith" <eric@brouhaha.com> 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.

I should amend the above to: "Prng's pass randomness checks with
100% flying colors and that's why they fail.  They cheat on the test."

Yes, it is theoretically possible to create a prng with some arbitrarily
long repeat cycle.  And one can postulate that in some arbitrarily long
lived universe the pattern will repeat.

That is not the point.  The pattern is not random.  It is deterministic.
If the generating method is known then each number coming out is known
with 100% certainty.  The only thing random about such a generator is
the algorithm.  The seed at which it starts is irrelevant to the
discussion: the sequence is circular - any starting point on the
circle is equivalent to any other.

It is like reading a book (it is exactly like reading a book), though
one may not know the next word, there is only _one_ possibility.
There is _no_ uncertainty.  That the observer is ignorant does not
make the sequence random.

A prng is nothing more than a _counter_.  The old TMS1000 micro used
a prng for the program counter because it could be made with less silicon
than a 'real' counter.  Debug was a gas ...

A zener diode and a comparitor will produce a sequence that can not
be predicted.  It being a real implementation it will have bias but 
in the limit it becomes impossible to tell bias from 1/f noise.  The
next generator built will have a different bias, etc. etc.

Good Lord.  Get thee to a palmist and have a seance with von Neumann
and Turing and ...  Far better minds than those here have declared
PRNG's to be mirage.

As the saying goes "The mind of God is unknowable", and I would 
add "even to God".

-- 
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer:  Electronics; Informatics; Photonics.
To reply, remove spaces: n o lindan at ix  . netcom . com

"Nick Maclaren" <nmm1@cus.cam.ac.uk> wrote
> Nicholas O. Lindan <see@sig.com> wrote:
> >"Terje Mathisen" <terje.mathisen@hda.hydro.com> wrote

> And exactly why should a pseudo-random generator be restricted to a
> bounded state space?  Why shouldn't it increase its workspace as time
> goes on?  Sorry, you aren't being imaginative enough.

I would counter that you are being maybe too imaginative.  When growth
to infinity is allowed the arguments get silly.

> >All physical processes are random.
> Your first sentence is religion, not engineering.

I didn't know they were mutually exclusive.  For the record I am
a self excommunicated Unitarian.

The argument is free-will Vs predestination.  As no one has been able to
settle the issue it seems that free will wins.  Unless you are of a 
particularly dour sect of Scots Presbyterian.

> [All physical processes may be random], but we don't know.

Any attempt at predicting reality fails.  Popper would say we
have to take reality as random until proven otherwise.

> Secondly, you CAN remove single-bit bias, or bias in any bounded
> number of bits.  Again, good 1930s results.

Ha Ha!  Have you tried it?

I can only recommend doing so. A real learning exercise.  A 15V zener, 
comparator and a parallel port are all you need.  In theory one should
be able to remove any 1/0 bias with an algorithm, in reality ...

> Thirdly, if you think that a pseudo-random generator has no defects,
> you haven't looked hard enough :-(

Very, very true.  Wait long enough and it will fail and start producing
real noise.

If it has defects from the beginning then it isn't a prng, is it?

-- 
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer:  Electronics; Informatics; Photonics.
To reply, remove spaces: n o lindan at ix  . netcom . com

Nicholas O. Lindan wrote:
> I should amend the above to: "Prng's pass randomness checks with
> 100% flying colors and that's why they fail.  They cheat on the test."
> 
> Yes, it is theoretically possible to create a prng with some arbitrarily
> long repeat cycle.  And one can postulate that in some arbitrarily long
> lived universe the pattern will repeat.

It is even possible to generate a PRNG that does not repeat. It may stop
working due to memory limits at some point, but it does not need to repeat.
Like a algorithm that produces all digits of pi, it will be fully
deterministic, though.

> A zener diode and a comparitor will produce a sequence that can not
> be predicted.  It being a real implementation it will have bias but
> in the limit it becomes impossible to tell bias from 1/f noise.  The
> next generator built will have a different bias, etc. etc.

Or the thermal noise of a resistor. If you use an auto-zero amplifier, the
bias goes away, but the noise level depends on temperature. Add an
automatic gain control (which takes the noise amplitude only), and you get
rid of that influence, too.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/

"Guy Macon" <http://www.guymacon.com/> wrote

> Riiiight.  The best cryptography experts in the world say that a
> cryptographically strong PRNG is indistinguishable from random
> data, the best known software for identifying bias (DIEHARD) 
> cannot find bias in cryptographically strong PRNGs

These the same crypto experts who bring us all these crackable
codes.  A prng is just one more code.  It is crackable just
like any other.  By _definition_.

> supposed to believe that this unnamed method [for determining
> randomness] is taught in statistics courses.

Philosophy, literature, art, religion ... stats hasn't caught 
up yet.  In my mind PLA&R kick over rocks for stats to come and explain
at some later date.

> Look here for evidence that you are wrong:
> http://www.google.com/search?q=prng+%22indistinguishable+from+random%22

Funny.  None of them say prngs are really-truly random.  They say
you can get 'good enough'.

And I didn't know Google was a particularly good source for the truth:

http://www.bonsaikitten.com/bnw.html

And

http://www.timecube.com/

And if you liked the timecube:

http://www.geocities.com/loudster/ripping_gore/web_weirdness.htm

> And this allows an unbounded state space to fit inside a bounded 
> universe [for a realizable system] - how?

And I can't believe I agree with Macon.  Aw, it's just a random event.

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

Ed Beroset wrote:
> Emil Briggs wrote:
> 
>>> Because the universe is finite, and thus the PRNG cannot increase
>>> its workspace without bounds.  Sorry, you are being too imaginative.
>>>
>> The boundedness of the universe is not a settled question.
> 
> True, and anyway it's kind of irrelevant, isn't it?  The set of
> positive integers, for example, is an infinite set whether or not
> the universe is infinite.

In order to prove that reduction to absurdity is not a valid method
of proof, I have set a machine (down in the basement) to
discovering and displaying the largest prime.  It does this quite
simply, by displaying all numbers that are not the largest prime. 
It is making steady progress.

For efficiency reasons it does its displaying in hex.  So far I can
confidently assert that the largest prime is not less or equal to:

0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff

The result will eventually require confirmation, because the ECC
memory cannot correct multiple bit errors, in fact it cannot even
detect all 3 bit errors.  In case someone wants to do this in
parallel, rather than after I publish the end result, suitable C
code follows:

   i = 0; largestprime = 0;
   while (i >= largestprime) {
      if (i && prime(i)) largestprime = i;
      printf("0x%x\n", i);
      if (!++i) break;
   }

and there are plenty of published methods of evaluating prime(i).

Note: the C system must have a suitable value of INT_MAX, otherwise
the above code can exhibit undefined behaviour.

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

Q: Is a Pseudo-Random Number Generator's output functionally 
   equivalent to a random sequence?

A: PRNG:   The next number in the sequence is knowable with sufficient
           knowledge.  Not being able to predict the number is due to
           ignorance and has nothing to do with 'random'.

   Random: No amount of knowledge will allow prediction of the
           next number.

-- 
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer:  Electronics; Informatics; Photonics.
To reply, remove spaces: n o lindan at ix  . netcom . com

"Guy Macon" <http://www.guymacon.com/> wrote
> Nicholas O. Lindan wrote:
> >> ...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.
> No, they do NOT "have to."  The period can be much longer than the 
> age of the universe.

So what?  The universe can be much longer than the period.

-- 
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer:  Electronics; Informatics; Photonics.
To reply, remove spaces: n o lindan at ix  . netcom . com

"Robert Finch" <robfinch@sympatico.ca> wrote

> The effect of randomness on static systems and the resulting progression of 
> time is interesting. Momentary randomness provides entropy which allows time 
> to pass. I wonder if one could build a time machine by varying the amount of 
> entropy in different regions of space.

Douglas Adams' "Infinite Improbability Drive"?

Good point you bring up: does a PRNG/Pi create entropy?

-- 
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer:  Electronics; Informatics; Photonics.
To reply, remove spaces: n o lindan at ix  . netcom . com

On Intel's motherboard/chipset RNG:

http://home.comcast.net/~andrex/hardware-RNG/

-- 
Nicholas O. Lindan, Cleveland, Ohio
Consulting Engineer:  Electronics; Informatics; Photonics.
To reply, remove spaces: n o lindan at ix  . netcom . com