The random number generator in a pc isn't really random.

It's pseudo-random.

People have made careers out of random number generators.

The British Premium Bond machine allegedly uses the noise generated by a zener diode as the source for a random number generator.

This is checked for randomness before and after a draw is made.

You can also get meta-stable states in logic where it doesn't know whether it's a 1 or a 0, which is a bit awkward.

rgds
Zeit.

If you are not too picky, you can make an oscillator from
three inverters and sample it with a D-FF clocked with
a much lower frequency.

<nbucska@pcperipherals.com>

My reading suggests that there are problems even trying to define 'randomness', far less generate arandom number.  If there are still people arguing about what it means to be random, then actually generating random numbers is a bit of a lost cause!

I believe older PCs generated a random number by just sampling the least significant byte or word in the real-time clock, relying on the time between samples being random.  Not too good if the sampling is inside a regular, repeating program loop.

Bung
Life is non-linear...

There are interesting issues with randomness.  

The simplest is having a sequence of numbers whose values are unknowable enough that they serve a useful function.  Pseudo-random generators produce such numbers with known, predictable repeat intervals.  But if you were a gambler and knew the algorithm, every number would be predictable.  On the other hand, radioactive decay is truly unpredictable.

A related issue is uniqueness.  Things like microsoft GUID's are 128 bit values that are not terribly random, but are guaranteed unique.  No matter how many you generate, no two anywhere in the universe generated by any number of people will ever collide.  (In theory)

Writing a program or creating an algorithm requires defining the specification for the 'random' output, then creating something that exceeds your requirements.

Rand() is pretty useless by itself except in the simplest of applications, and in some cases has a 16 bit or less repeat interval.  If the seed is not changed then you have exactly the same sequence every time it is used.

These are simply practical problems.  As Bung mentioned above, defining the problem usually allows solving it, because part of any real problem is a definition of how good the solution has to be.

Rand Corporation ran a study a long time ago to create a table of random numbers.  They ran it through multiple level testing, not just looking at each successive digit, but also looking a two digit, three digit, skipped digit randomness.  There's something like 1 million digits that are supposed to be as close truly random as possible.

As far as most random number generators used in computers or programs, they're usually done with a cyclic polynomial generator.  As mentioned above, the polynomial will essentially repeat after a while.

TTFN

I believe that some intelligence agencies use the electromagnetic noise from outer space as a random number generator for encryption purposes.

On the other hand, the guy who designed my CD player apparently knew nothing about randomness, and designed a player that will play the same tracks over and over when you hit "random play".
Most annoying.

 

Philosophical question: if you know that your table of 1 million digits is that "random", how predictble has it become?  After all, you have specifically excluded any non-randomness, any from of pattern at all, then you must have reduced the set of possible sequences.  A sequence with a pattern to it may be truly non-random in some applications, and completely random in another, could it not?

Is the chaotic behaviour of non-linear processes under some conditions random?

I agree with DspDad - the best way to choose a "random" number is to do it based on knowing why you want it, and so what constitutes randomness for your application.

Bung
Life is non-linear...

BuzzViper, if you really want randomness, then stop doing all the things you do to avoid randomness and start doing the exact opposite (Ha-Ha).

I once read an article in some trade magazine about a random number generating algorithm written in C (sounds like an oxymoron).  It was basically some crazy mathematical algorithm calculating some otherwise useless floating point values and doing something else with them (I can't quite remember).  I believe at the end of the algorithm the numbers are made to be between 0.0 and 1.0.

What about using a high resolution A/D converter 12 bit or
more and measuring some external enviromental variable
like temperature and use the least significant digit
of each conversion in decimal with adequate time
between samples and combine as many of these as you
need to form a random value.
comments ?
rodar

You're assuming that the noisefloor of the A/D is "random."  True randomness is difficult to achieve.  The A/D noise may be dominated by something like AC line noise, which may result in a highly non-random acquisition sequence.

TTFN

  One of the truly random things in nature is radioactive decay... If you set up a slowly decaying isotope and run, say, a 16 bit counter that you read whenever a decay is detected you'll have a random number....

Fred Saberhagen's entire Beserker series is even based on this.  Great SiFi.

Good overview article:
http://www.americanscientist.org/template/AssetDetail/a...

As stated before, computers or logical circuits can not generate infinite random number sequences due to their inherent nature, i.e., a 16 bit ALU (arithmetic logic unit) has a finite set of possible integers (2^16 combinations) it can generate. The patterns of 1's and 0' generated by a logical circuit will always be finite and will always repeat eventually. If, however, the set of possible combinations is large enough, one can safely assume pseudo-randomness. This is why, as dspDad pointed out, it is important to define the nature (no pun intended) of randomness needed.  

Electronic circuits dedicated to random number generation are  better (but not perfect) than ALU's in my opinion. Off the shelf boards can be purchased. A circuit idea using digital techniques can be found at:

http://www.ee.washington.edu/circuit_archive/circuits/r...

Modern CPU's, e.g., Intel Celeron, have a built-in random number generator based on thermal noise and quantum mechanics (intended for security puposes)!

There are numerous computer algorithims to generate psuedorandom numbers. The algorithm implemented by QBasic's RND command can be used to generate complex fractal (chaotic) patterns. An interesting irony!

The following book is an excellent source of info:
Knuth, D.E.: The Art of Computer Programming, volume 2: Seminumerical Algorithms. Addison-Wesley, Reading, MA, 3rd edition, 1997.

The following site generates random numbers from a radioactive decay process for all to download and use. However, once again, "random" must be defined to be useful.

http://www.fourmilab.ch/hotbits/

Finally, randomness in nature is an illusion. Current research in choas theory is set to dispel the myth of randomness in quantum mechanical events such as radioactive decay. One day soon we will accept Einstein's view that "God does not play dice with the Universe".

I would like to clarify my idea somewhat.
To me the A/D noise floor does not matter because
I would like to measure a natural phenomena like
wind speed or temperature variation. Suppose
the naturaly occuring variable typically created
+/- 100 counts of varitation between samples of
this natural process. What factors of the measuring
circuit could be discernable when the external
process is producing a sample to sample variation
of at least 100 counts or more.
Finally what would happen if once a suitable amount
of random numbers were accumulated they were subject
to a swapping algorithem that is driven by the same
random number source such that these fixed values are
shuffled repeatedatly by the random process. The
original values are all still there just their order of
placement in the array has been shuffled excessively.
Finally isn't the simple test of autocorrelation applied
to a sequence enough to determine randomness. With a
flat autocorrelation there is no information with which
to make a guess of the next value that is any better than
randomness.
Comments??

amptramp:  Great link there to Formilab!  It sucked me in totally.  Very well done.  Thanks for the link.

60hzhmmm:
No problem! I have enjoyed this thread very much. I hope we can keep the thread sewing!

I am interested in reading responses to a comment in rodar's last post about autocorrelation. Everything I have read indicates that although  a "flat" autocorrelation does imply independency, it is also important the random number sequence be uniformly distributed within its range (typically normalized from 0 to 1). In other words, statistically speaking, more than one test is required to determine some level (once again, definition is required) of psuedorandomness.

For example, would it be possible, if the sequence is "crowded" (not uniformly distributed), for a crypto hack to use this "failure" to crack the sequence, eventhough the sequence is independant?

To regress somewhat, one of the most common psuedorandom number generator algorithms is the following recursive formula:

    x_{n+1} = (a*x_n + c) mod m

where:
      a,c = "optimization" constants
        m = modulus (affects the period of the sequence)
      x_n = "seed"

It is referred to as a linear congruential generator. For true RNG geeks, there are many hours of "enjoyment" that can be spent "optimizing" the random sequence so it is "random" (passes the tests).
         
 

Amptramp:
The CPU wordlenght has no connection to the lenght of the integer it can generate : an 8 bit CPU can generate easily
a 256 bit integer -- 8 bits at a time. Working in decimal
number system we still can use 2,3 digit or even larger
numbers !  

<nbucska@pcperipherals.com>

Thanks everyone for the links and stuff. This has turned out more interesting than I thought.

nbucksa:

You took my statement out of context. I was discussing generating random numbers - not integers.

Also, you implied it takes "eight bits at a time to generate the 256 bit integer. Is this not a connection? And is this not a connection based on the "word length" of the CPU. I am afraid your position was not well defended.

But just for fun...

If I understand you correctly, you are implying either the use of concatenation to generate "large" binary integers (numbers) or the use of codes, i.e. B.C.D., to generate representations of "large" integers (numbers) in other base systems, specifically decimal.

To preface:

It is understood we are discussing the counting numbers (integers) only - not floating point numbers, for example.

It is understood all "numbers" used by CPU's are representations of numbers - even binary numbers.

It is also understood the inherent number system of a CPU is binary (radix 2). All numbers represented by a CPU are either "true" binary numbers (1011), converted binary numbers (to octal, decimal, or hex, etc.), or coded numbers (B.C.D., ). In our discussion, only true binary numbers or coded numbers are relevant. Converted binary numbers are just that - binary numbers.

To begin:

Although it is true concatenation of bits allows for large binary integers to be enumerated and coding can represent large decimal (if you choose) integers as well, stating "CPU wordlenght has no connection to the lenght of the integer it can generate" is like saying a "2 by 4" has nothing to do with building a house!

(Would you make the same statement if our CPU had a word length of one bit?)

Again, the maximum number of combinations a sequence of "n" binary bits can represent is 2^n.
The maximum number of signed integers that can be represented by these combinations are 2^(n-1) - 1.

The implication of the previous statement for concatenation:

Even if you concatenate, there will still be an "n" bit sequence based upon (as you implied) a multiple of the "CPU word length".

Further, even assuming the use of a recursive algorithm and concatenation, there is still a finite number (integer) that can be generated (represented) due to the fact that the algorithm (recursive steps) must "halt" to be useful.   

Next, coding requires an algorithm to generate the number. The algorithm must be executed within the constraints of the CPU in use - and one of the fundamental constraints of most CPU's is the word length. Ever heard of the Von Neumann bottleneck?

For coding, every "symbol", i.e., digit, is represented by a "group" of bits (where the minimal form of grouping is one bit, or in other words, the simplest code is plain old binary).

In B.C.D., 4 bits are used for each digit (symbol); therefore, two decimal digits can be represented by an eight bit CPU for a maximum (without using concatenation!) of decimal 99. However, using binary, the same eight bits can represent a maximum of decimal 255 (obviously a larger number).

The implication is coding is less efficient than concatenation for generating large integers; therefore, we dismiss coding as a viable method.

We are left with concatenation as our method of choice. And it should be obvious concatenating the maximum grouping of bits available is most efficient - and the "maximum grouping available" is the "CPU word length"!

Now, all this being said, we return to the original subject - random number sequences. Looking again at the linear congruential generator algorithm:

x_{n+1} = (a*x_n + c) mod m

And remembering "m" affects the period of the "random" sequence, it is apparent any limitation on integer size limits the size of the random number sequence before it repeats. This fact is why I made my statement:

computers or logical circuits can not generate infinite random number sequences due to their inherent nature, i.e., a 16 bit ALU (arithmetic logic unit) has a finite set of possible integers (2^16 combinations) it can generate.

There are numerous algorithms to generate random number sequences. Obviously, I am not familiar with all of them. All I am familiar with are constrained by the maximum integer size that can be plugged into the algorithm.

I think you are confusing word length with the algorithm.

So long as the algorithm is properly executed, any length integer can be accommodated, so there is absolutely no problem with even an 8-bit processor running 64-bit arithmetic, it just takes a LOOONG time.

The same principle is how the 80x86 family was able to do 32-bit floating point without 80x87 co-processors.

Carry-add arithmetic is how a human being can multiply 20-digit numbers with only 10 fingers.

TTFN

IRstuff:

Thanks for the input.

I do not believe I am confused. I must not be communicating my point effectively.

I agree if an "algorithm is properly executed, any length integer can be accommodated", but my point is "any length integer" can not be generated in the first place. As I stated before, all algorithms (even ones to generate long integers) must halt for them to be useful. (The halting problem of algorithms was greatly infuenced by the work of Alan Turing - you may have heard of him.)

In our discussion, we could talk about two algorithms - one to generate the long integer and one to generate the psuedorandom sequence - both of which would have to halt to produce a useful output.

More info on the halting problem:
http://en2.wikipedia.org/wiki/Halting_problem

Although it is true concatenation of bits allows for large binary integers to be enumerated and coding can represent large decimal (if you choose) integers as well, stating "CPU wordlenght has no connection to the lenght of the integer it can generate" is like saying a "2 by 4" has nothing to do with building a house!

(Would you make the same statement if our CPU had a word length of one bit?)


Your posting essentially posited that an 8-bit computer could not perform something like 64-bit arithmetic, which is clearly not the case, since a Turing machine is a 1-bit processor that can emulate larger processors.

TTFN

I did not imply an 8-bit computer could not perform something like 64-bit arithmetic. I believe we all understand this operation can be achieved. However, it would take more than one instruction cycle (possibly at least 8 instruction cycles) to complete the operation. To me, this implies a connection to the word length of the CPU (ALU) and this connection is what I posited.

Also, a Turing Machine is not necessarily a one bit processor. The special case of the one "symbol" Turing Machine is often described as it is easy to illustrate the concepts involved using a minimal symbol set. And don't confuse the individual cells on the infinite (finite) tape as a "bit".

See th following web sites:

http://www.cs.princeton.edu/courses/archive/fall02/cs12...

http://mathworld.wolfram.com/TuringMachine.html

Maybe this web site will help convey what I originally meant by my comment, "computers or logical circuits can not generate infinite random number sequences due to their inherent nature, i.e., a 16 bit ALU (arithmetic logic unit) has a finite set of possible integers".

http://www.andreas-mielke.de/sm-en-5.html

Amp: We understand only we disagree:

Even if we neglect that infinite number is meaningless
your previous statement is wrong: Any computer can generate
an infinite number -- it just takes infinite time.

I give IRSTUFF a red star -- I would give a black one
to you if there was any...This is an engineering forum
and engineering is the practical application of the
science. If you want to split hair, find a forum for
mathematicians -- or barbers.
 

<nbucska@pcperipherals.com>

Since there is a finite number of integers that a ALU can produce, the possibility of randomness is 0?  What about the game craps?  There are a finite set of numbers that can be achieved with 2 dice, but the outcome of the game is essentially random.

To nbucksa:

I sincerely apologize if I have offended you. I was simply enjoying the joust. I humbly accept your black star.

To all:

I also apologize if I have offended anyone else.

Hi Amp:
Argument is not offense -- no apology is needed.

The original question was: How the random function can be implemented usig digital circuitry?

The answer: by approximation. It depends on the application
if a given approximation is good or bad. One simple way
-- on PC and "C" -- to read the system timer:

outbyte (0x43,0xd2); lsb=inbyte(0x40); msb=inbyte(0x40);
/** perhaps even XOR lsb w/ msb **/ lsb = lsb ^ msb;

I found this good enough in many applications.

<nbucska@pcperipherals.com>

Depends on the craps table and casino

Because of the construction of the rules for casino craps, there is an inherent bias in favor of the house, so the outcome is rarely random: YOU always lose to the house, it's just a matter of time for when that happens.

TTFN

Just a side question to randomness:

The string tangling therom: A tring or chain or similar always tend to tangle up if it is given a kinetic energy. An example of this if something of a string kind is left in a pocket and then as you walk and do things the pocket gets KE and when you take the thing out at the end its always tangled to an unbelievable mess.

This brings me two questions:

a) Does that mean that the string gets into a more random state or a less random one?

b) Is this what the universe is like? i.e. gets more random or less random with time in a natural manor. Then would this lead to a concludion that randomness is something cannot really be totally controlled or randomised, as it has its own natural rythem?

Politicians, journalists and environmentalists survive using doublespeak and obfuscation, unlike engineers who need to use words precisely.  Unambiguous naming conventions are critical in the sciences, and sloppy use of words leads to as many bad conclusions as sloppy use of statistics.

If entropy had been described as increasing relaxation or increasing comfort instead of increasing randomness, then we would live in a universe where sagging and rest were the outcomes instead of chaos.  Unfortunately, randomness has some connotations that imply discord and uncertainty, whereas increasing entropy really implies quietness, death, and drifting eternally without change.  About as predictable as it gets.

In physiology, the health of an system can be measured in part by its unpredictability, heart rate for example.  A dying heart has a non-varying rhythm, whereas your heart varies in rate every beat.  

Entropic, thermodynamic randomness and random numbers, while sharing the same root word (meaning to run unpredicably) share little else.

Your tangled string is a semantic convention.  Is it a good model for randomness.  A frayed knot.

The universe experiences continuously increasing entropy which unrelentingly follows the laws of thermodynamics.  The antithesis of 'randomness'.

Have a Happy Thanksgiving.
DspDad

Hey Buzz,

The string obeys the Law of Entropy - it is seeking a state of maximum aggrevation.

a) Is there such a thing as "degree of randomness" - or, if it is random, then it is random (assuming we are not talking about psuedo-randomness).

b) The Universe is Chaotic!