🚀 go-pugleaf

tjgerman@53iss6.Waterloo.NCR.COM (Trevor German) writes:


>	Someone wants to know hos to create random numbers on a computer.


>	This sounds trivial but it is not. First you need a good definition
>	of a random number. The definition required is as follows.


>	1. The number shall be contained within a range, say 0 - 255

>	2. The probability of selecting and number at any time will
>	 be 1:256.

>	3. No sequencies shall exist, ever.....

I assume you mean "no cycles will occur", in the sense that the
infinite sequence of numbers does not repeat after a while.

>	If an algorithm is used than sooner or later some condition will
>	be met that restarts the sequence. This is why these routines are 
>	usually called pseudo-random generators.

It is in fact possible to make non-repeating pseudo-random number
generators. The 'pseudo' doesn't refer to repetition, but to
predictability: if the numbers are generated by an algorithm, you can
predicat the next number if you know the current state. Therefore the
numbers are not truly random. So your condition 2 can not hold, as the
probability for any number is either 0 or 1. However, you can require
that the distribution of numbers approach the even distribution in the
limit, as the length of the sequence increases.

To make a non-repeating sequence of random numbers you need unbounded
memory (like on a Turing machine), but you will only a finite amount
of it at any time.

As an example, generate the (infinite) binary expansion of pi. To do
this requires more and more memory (and time) for each successive bit.
To generate a pseudo-random number sequence with numbers in the range
0-255, group the bits eight at a time. The sequence will never repeat
(as pi is not rational), and it will have an even limit-distribution
of numbers.

>        Hardware random number generation can be done using something that
>        counts random events, like the atmospheric noise froma tuned out
>        radio etc. 

Noise from a diode has often been used. Note that you will not
normally have an even distribution of values from such a source, but
see the discussion about unfair coins for how to generate even
distribution from an uneven source with unknown distribution.

	Torben Mogensen (torbenm@diku.dk)