[fpc-pascal]Random generator

Alan Mead cubrewer at yahoo.com
Sun Dec 7 19:25:20 CET 2003


--- Florian Klaempfl <Florian.Klaempfl at gmx.de> wrote:
> /dev/random is very random, it's gets it's data from an "entropie
> pool" 
> which is filled using the random times when hardware interrupts are
> 
> triggered. Because this pool has a limited size and only a few
> hardware 
> interrupts per second happen, this random generator runs quite fast
> out 
> of data. There is also a "non"-blocking random device which uses a
> usual 
> random generator when the entropie pool runs out of data, but I
> don't 
> remember it's name.

This reply is vary long.

After I posted this, I looked into these devices.  They were written
by Theodore T'so of kerberos fame and, I have to imagine, intended to
produce crypotgraphically-secure randomness.  As you say, /dev/random
produces data that should be close to truely random but in fits and
not very much.  The other device is /dev/urandom.  Some people may
also have a /dev/hwrandom which may, or may not, work.  It sounds
like Intel included a hardware RNG on some chips.  There were several
sites that described generating random numbers from sound card white
noise.  I also looked into hardware RNG's.  It looked like these
would be a (small) project and cost at least 80-140 USD.  

Here is a comparison of the FPC 1.0.10 random number generator and
the system devices:

[amead at alan irt]$ uname -a
Linux alan 2.4.7-10 #1 Thu Sep 6 17:27:27 EDT 2001 i686 unknown
[amead at alan ent]$ fpc -v
Free Pascal Compiler version 1.0.10 [2003/06/26] for i386
Copyright (c) 1993-2003 by Florian Klaempfl
Fatal: No source file name in command line
[amead at alan ent]$ ./ent fpcrandom.txt
Entropy = 7.982320 bits per byte.

Optimum compression would reduce the size
of this 10000 byte file by 0 percent.

Chi square distribution for 10000 samples is 244.81, and randomly
would exceed this value 50.00 percent of the times.

Arithmetic mean value of data bytes is 128.9561 (127.5 = random).
Monte Carlo value for Pi is 3.142857143 (error 0.04 percent).
Serial correlation coefficient is 0.005214 (totally uncorrelated =
0.0).
[amead at alan ent]$ ./ent urandom.txt
Entropy = 7.999914 bits per byte.

Optimum compression would reduce the size
of this 2252800 byte file by 0 percent.

Chi square distribution for 2252800 samples is 269.51, and randomly
would exceed this value 50.00 percent of the times.

Arithmetic mean value of data bytes is 127.5270 (127.5 = random).
Monte Carlo value for Pi is 3.141578731 (error 0.00 percent).
Serial correlation coefficient is -0.000061 (totally uncorrelated =
0.0).
[amead at alan ent]$ ./ent random.txt
Entropy = 7.892939 bits per byte.

Optimum compression would reduce the size
of this 1477 byte file by 1 percent.

Chi square distribution for 1477 samples is 212.05, and randomly
would exceed this value 97.50 percent of the times.

Arithmetic mean value of data bytes is 127.6141 (127.5 = random).
Monte Carlo value for Pi is 3.186991870 (error 1.45 percent).
Serial correlation coefficient is 0.000579 (totally uncorrelated =
0.0).

I would discount the chi-square because it varys a lot when you
repeat this experiment.  Also, I think of it having a one-tailed
distribution whereas the ent author interprets it as two-tailed. 
Also, note that the samples vary enormously in their size.  I got the
/dev/random and /dev/urandom samples by cat'ing the devices and
redirecting into a file (and then breaking).  So the /dev/urandom
sample is quite large and the /dev/random sample is pretty small. 
For the FPC generator, I wrote a very simple program that generated
10,000 random bytes, cast these as chars, and wrote them to disk.

The compression forecast and Monte Carlo estimation of Pi strike me
as the best indicators of how the RNG's operate relative to my needs.
 Way back, I used to plot this Pi test with the BGI unit and visually
inspect it for patterns.  By whichever method, clearly /dev/random
wouldn't work well as a random number generator although it might
provide good random seed values.  Is the FPC RandSeed  16 of 32 bits?
 Either way, you could probably re-seed from /dev/random every 30
seconds. To use the device in a Pascal program, just open
'/dev/random' or '/dev/urandom' as a text file and 'read(ran,ch)',
given 'ch:char;'.

-Alan

__________________________________
Do you Yahoo!?
New Yahoo! Photos - easier uploading and sharing.
http://photos.yahoo.com/




More information about the fpc-pascal mailing list