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

In comp.arch and comp.arch.embedded, on 4 Mar 2005 07:42:36 -0800,
"Motaz K. Saad" <motsad@yahoo.com> 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

   They are universally generated in software, such as the linear
congruence generators mentioned elsewhere in this thread. But these
are NOT true random number generators. They are named pseudo-random
number generators, because though they may "look" random (they pass
some of the "tests" for random numbers), they are totally predictable
from the algorithm and the seed. Donald Knuth discusses this method
(and his first attempt at pseudo-random number generation that didn't
work well at all) in whichever volume it is of his "The Art of
Computer Programming." If you don't buy a copy, it's well worth going
to the library or bookstore to read that portion of the series.

>implemented in software layer, how it is implemented in the regular
>calculator i.e. pocket calculator (not calculator program).

   I recall older calculators such as (IIRC) the TI SR-52 having a
"RND" button that gave a two-digit decimal number when pressed. I
presume that there is a two-digit counter that is incremented at every
keyboard scan, and when the RND button is pressed the counter's value
is copied to the display register. The keyboard is scanned at the rate
of several hundred times per second, resulting in an essentially
random number displayed when the RND button is pressed. The thing
couldn't generate more than two 'random' digits at a time, because it
doesn't count fast enough. It's like a stopwatch, where the seconds
and tens of seconds would be highy correlated: it's easy enough to
press start and stop to get it to display 12, 13, 14, 15, 16 seconds,
but it's virtually impossible to get a stopwatch to stop on a
particular digit in the hundreths and thousanths positions.

>thanx

-----
http://mindspring.com/~benbradley

> Ben Bradley <ben_nospam_bradley@frontiernet.net> wrote:

> They are universally generated in software, such as the
> linear congruence generators mentioned elsewhere in this
> thread. But these are NOT true random number generators.
> They are named pseudo-random number generators, because
> though they may "look" random (they pass some of the
> "tests" for random numbers), they are totally predictable
> from the algorithm and the seed.

Do many algorithmic rngs ever have two adjacent generated
raw numbers be identical? (Obviously it's common after
rounding or truncating.) In cases where the seed and the
result are the same length, and the result is the next seed,
and nothing else dithers the calculation, runs would seem
impossible unless the algorithm got wedged (in which case
the output will never change again).

Just as flipping a coin can (and does) result in
infrequent runs of all-heads and all-tails, I'd expect
a "real" rng to at least be capable of occasional
duplicate sequential results, if not runs of them.

Of course, if the application for the generated numbers
demands that successive numbers never be the same,
then perhaps a "real" rng isn't suitable. For example,
encryption keys for successive data transmissions.

-- 
Regards, Bob Niland                        mailto:name@ispname.tld
http://www.access-one.com/rjn           email4rjn AT yahoo DOT com
NOT speaking for any employer, client or Internet Service Provider.

Sander Vesik wrote:
> 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? 

I don't know, but I bet Shannon would (:

> Note also that these (software) library functions generate *pseudo-random* 
> sequences.  True random sequences are impossible to be achieved by solely 
> software means.
>

Well, it depends on how long you're willing to wait doesn't it ? No system 
operates perfectly for an indefinite period of time. Because at some point a 
hardware error will occur, due ultimately to the randomness in the universe. 
So in a sense even software algorithms probably produce truly random 
sequences (if you wait long enough). I know my C64 used to heat up after 
about 5 hours or so, then the games became really interesting due to the 
hardware errors.

How about building a hardware LFSR (rng) at a hot spot on a chip, so that 
it's guarenteed to occasionally fail ?

I've thought that the all randomness in the universe might be reducible to 
effectively a single point of randomness. Something I've called the spark of 
life. It just constantly flashes in different patterns causing quantum state 
changes to appear randomly.

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.

(This is all just fanciful speculation by me. I like to speculate - 
speculate first, verify later).

Rob

Bob Niland <email4rjn@yahoo.com> writes:
> Do many algorithmic rngs ever have two adjacent generated
> raw numbers be identical? (Obviously it's common after
> rounding or truncating.) In cases where the seed and the
> result are the same length, and the result is the next seed,
> and nothing else dithers the calculation, runs would seem
> impossible unless the algorithm got wedged (in which case
> the output will never change again).

However, there are PRNGs that carry more internal state than
is present in one output value.  These can easily produce the
same output on two consecutive iterations.  In fact, you expect
that on average a good PRNG should do that with probability
1/n for any two consecutive outputs.  For instance, if you roll
a normal 6-sided die twice, there should be a 1/6 chance that
it will have the same result both times.

Sander Vesik <sander@haldjas.folklore.ee> writes:
> Heres a quiz : how many digits of a random number do you need to 
> definitely tell if it is random or not? 

Trick question.  Having all of the digits is a necessary but not
sufficient condition.  If you only have n-1 digits of a putative n digit
random number, you can't tell whether the final digit can be predicted
from earlier digits.  But if you do have all n digits, and no other
information, you still can't prove that the number is random.  For
instance, if you have all the digits of the putative n-digit random
number, it may still be the output of a PRNG that has a short cycle,
and thus the entire n-digit number my have been easily predictable.

One could question whether it is meaningful to talk of a single finite
rational number as being random.  However, if one hold that it is not,
one also have to accept that any finite sequence of finite rational
numbers can also not be considered random, because any such sequence can
be represented as a single finite rational number.

Eric

Le Fri, 04 Mar 2005 07:42:36 -0800, Motaz K. Saad a �crit�:

> 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

Hello all,

Wathever the methods used to produce random numbers (integers, float,
binary ...) i.e :
/dev/random (Linux),
rand(), lrand() ...etc,
LFSR implemented in FPGA (Lewis & Payne)
Thermal noise sources,
... etc.

IMHO opinion the only valued question is :
Is the sequences of numbers MUST conform to various battery of tests (Cf.
G.Marsaglia, D.E Knuth,) in order to decide if this method is a good one
for the targeted application. 

The test process of a given RNG is a very hard step and require some brave
and courage.

Habib

"Dennis M. O'Connor" <dmoc@primenet.com> wrote in message 
news:1109984830.209821@nnrp2.phx1.gblx.net...
> "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.
> --
However if you do need random numbers without the pseudo bit then an Intel 
Motherboard does the job.
http://www.lightstraw.co.uk/gpo/posb/ernie4.html
The UK Government Actuary's Department does statistical analysis on all the 
numbers generated to verify that there is no discernable pattern.

Peter 

In article <055Wd.1265$603.1005@newsread2.news.atl.earthlink.net>,
Nicholas O. Lindan <see@sig.com> wrote:
>"Terje Mathisen" <terje.mathisen@hda.hydro.com> wrote
>>
>> 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.

Sigh.  This is what comes of a poor understanding of the unrealistic
models so popularised by modern computer science courses.  I did some
work on this a while back - here is a VERY rough summary:

1) There is a universal test that will distinguish all pseudo-random
generators from true ones.  Actually, there are many, and several
have been known (to statisticians) since the 1920s, but there were a
couple of 1980 (?) CS papers that described these as new :-)  Let's
agree on that one.

2) There is a universal pseudo-random generator that will pass all
tests as truly random.  This operates by simulating all tests (there
are only a countable number, after all) and choosing a sequence that
will "fail the failure test" for each.  A simple variant of Turing's
diagonalisation proof.

The key is that the proofs use different models of complexity.  In
both cases, they allow the favoured antagonist unlimited resources
compared to its opponent.  In the first case, a mere exponential
increase in complexity is needed; in the latter, it is rather more
evil.

There is very similar situation with designing for reliability and
security - or in breaking them - where the first question is "what
are we protecting against?"  It is a classic axiom of military
intelligence that you can overwhelm any system if you put enough
resources into doing so.

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

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.

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

Your first sentence is religion, not engineering.  They may be, but
we don't know.

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

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


Regards,
Nick Maclaren.

On Sat, 5 Mar 2005 08:37:54 -0000 in comp.arch, "Peter"
<moocowmoo@newprovidence.demon.co.uk> wrote:

>
>"Dennis M. O'Connor" <dmoc@primenet.com> wrote in message 
>news:1109984830.209821@nnrp2.phx1.gblx.net...
>> "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.

>However if you do need random numbers without the pseudo bit then an Intel 
>Motherboard does the job.
>http://www.lightstraw.co.uk/gpo/posb/ernie4.html

It uses a Logica motherboard with an Intel (810/815/830/845G?) chipset
including an 82802 FirmWare Hub whose RNG generates an octet in less
than 4.5ms (~0.5ms/bit?) Okay if you only need 11 digits/week for the
lottery, but at that rate, it would take 4 days to fill a CD. For
security uses, you'd want to collect the bytes on a timer and keep
them around for when you need a bunch of them quickly. 

-- 
Thanks. Take care, Brian Inglis 	Calgary, Alberta, Canada

Brian.Inglis@CSi.com 	(Brian[dot]Inglis{at}SystematicSW[dot]ab[dot]ca)
    fake address		use address above to reply