## Randomness, How?

## Randomness, How?

(OP)

Hi to all,

Most electronics I've doing so far are concentrating on how make a gate or such as reliable as possible - least probabily for error. i.e. if you are meant to get a '1' as your output then that's what you get and not oscillations.

But then come to think of the random function Rand() and Seed() in C/C++, an question appears across my mind on how this can be implemented using digital circuitry. Is there a circuit configuration that can generate randomness and can be altered to change the degree of randomness? How is it done in a prebuilt machine - PC?

Website or anything can be helpful.

Thanks in Adv.

Most electronics I've doing so far are concentrating on how make a gate or such as reliable as possible - least probabily for error. i.e. if you are meant to get a '1' as your output then that's what you get and not oscillations.

But then come to think of the random function Rand() and Seed() in C/C++, an question appears across my mind on how this can be implemented using digital circuitry. Is there a circuit configuration that can generate randomness and can be altered to change the degree of randomness? How is it done in a prebuilt machine - PC?

Website or anything can be helpful.

Thanks in Adv.

## RE: Randomness, How?

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.

## RE: Randomness, How?

three inverters and sample it with a D-FF clocked with

a much lower frequency.

<nbucska@pcperipherals.com>

## RE: Randomness, How?

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

## RE: Randomness, How?

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.

## RE: Randomness, How?

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

## RE: Randomness, How?

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.

## RE: Randomness, How?

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

## RE: Randomness, How?

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.

## RE: Randomness, How?

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

## RE: Randomness, How?

TTFN

## RE: Randomness, How?

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

## RE: Randomness, How?

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

dspDadpointed 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".## RE: Randomness, How?

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

## RE: Randomness, How?

## RE: Randomness, How?

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'slast 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 testis 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).

## RE: Randomness, How?

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>

## RE: Randomness, How?

## RE: Randomness, How?

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

representationsof 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 hasis like saying a "2 by 4" has nothing to do with building a house!noconnection to the lenght of the integer it can generate"(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"

isthe"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 generateinfiniterandom 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.

## RE: Randomness, How?

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

## RE: Randomness, How?

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

## RE: Randomness, How?

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

## RE: Randomness, How?

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

## RE: Randomness, How?

"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

## RE: Randomness, How?

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>

## RE: Randomness, How?

## RE: Randomness, How?

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.

## RE: Randomness, How?

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>

## RE: Randomness, How?

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

## RE: Randomness, How?

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?

## RE: Randomness, How?

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

## RE: Randomness, How?

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!