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

Huh?

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

As opposed o the expected brownian motion?

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

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

--
- 
"almost all programming can be viewed as an exercise in caching"
Reply to
Terje Mathisen
Loading thread data ...

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
 Click to see the full signature
Reply to
Grant Edwards

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.

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.

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.

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.

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?

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.
 Click to see the full signature
Reply to
Nicholas O. Lindan

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

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

--
- 
"almost all programming can be viewed as an exercise in caching"
Reply to
Terje Mathisen

"Del Cecchi" wrote

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 snipped-for-privacy@primenet.com

Reply to
Dennis M. O'Connor

"Terje Mathisen" wrote

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.
 Click to see the full signature
Reply to
Nicholas O. Lindan

"Nicholas O. L> Yes, and they fail them. Have to. They _do_ repeat, so there

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

Reply to
Eric Smith

digits

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

Reply to
del cecchi

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.

Reply to
Clifford Heath

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

wrong

This is even worse than wrong.

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.

This is utterly untrue.

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

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

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 +++
Reply to
Sander Vesik

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.

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.

-----

formatting link

Reply to
Ben Bradley

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
 Click to see the full signature
Reply to
Bob Niland

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

Reply to
Jim Stewart

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

Reply to
Robert Finch

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.
Reply to
Eric Smith

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

Reply to
Eric Smith

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

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

Reply to
habib bouaziz-viallet

However if you do need random numbers without the pseudo bit then an Intel Motherboard does the job.

formatting link
The UK Government Actuary's Department does statistical analysis on all the numbers generated to verify that there is no discernable pattern.

Peter

Reply to
Peter

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.

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.

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.

Reply to
Nick Maclaren

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)
 Click to see the full signature
Reply to
Brian Inglis

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.