netdev
[Top] [All Lists]

Re: [RFC] enhanced version of net_random()

To: root@xxxxxxxxxxxxxxxxxx
Subject: Re: [RFC] enhanced version of net_random()
From: Stephen Hemminger <shemminger@xxxxxxxx>
Date: Mon, 23 Aug 2004 10:05:47 -0700
Cc: Andreas Dilger <adilger@xxxxxxxxxxxxx>, Jean-Luc Cooke <jlcooke@xxxxxxxxxxxxxx>, "David S. Miller" <davem@xxxxxxxxxx>, Alan Cox <alan@xxxxxxxxxxxxxxxxxxx>, "Theodore Ts'o" <tytso@xxxxxxx>, netdev@xxxxxxxxxxx, Linux kernel <linux-kernel@xxxxxxxxxxxxxxx>
In-reply-to: <Pine.LNX.4.53.0408201518250.25319@chaos>
Organization: Open Source Development Lab
References: <20040812104835.3b179f5a@xxxxxxxxxxxxxxxxxxxxx> <20040820175952.GI5806@xxxxxxxxxxxxxx> <20040820185956.GV8967@xxxxxxxxxxxxxxxxxxxx> <Pine.LNX.4.53.0408201518250.25319@chaos>
Sender: netdev-bounce@xxxxxxxxxxx
> The attached code will certainly work on Intel machines. It is
> in the public domain, having been modified by myself to produce
> a very long sequence...
> 
> I wouldn't suggest converting it to 'C' because the rotation
> takes many CPU instructions when one tries to do the test, shift,
> and OR in 'C',
> 
> Cheers,
> Dick Johnson
> Penguin : Linux version 2.4.26 on an i686 machine (5570.56 BogoMips).
>             Note 96.31% of all statistics are fiction.
> 
> 

My choice of PRNG was not random. I am not a mathematician (IANAM),
but what I was looking for was:

+ well researched
+ fast
+ good distribution
+ small seed (since per cpu)
+ Free and open

The second version uses tausworthe because it was the fastest in the GNU 
scientific
library and had good properties.

See:

http://www1.physik.tu-muenchen.de/~gammel/matpack/html/LibDoc/Numbers/Random.html
----------
Returns integer pseudorandom numbers uniformly distributed within 
[0,4294967295].
The period length is approximately 288 (which is 3*1026).

This is Pierre L'Ecuyer's 1996 three-component Tausworthe generator "taus88"

This generator is very fast and passes all standard statistical tests.

P. L'Ecuyer, Maximally equidistributed combined Tausworthe generators, 
Mathematics of Computation 65, 203-213 (1996), see Figure 4.
P. L'Ecuyer, Random number generation, chapter 4 of the Handbook on Simulation, 
Ed. Jerry Banks, Wiley, 1997.
--------
http://www.gnu.org/software/gsl/manual/gsl-ref_17.html

Performance
The following table shows the relative performance of a selection the available 
random number generators. The fastest simulation quality generators are taus, 
gfsr4 and mt19937. The generators which offer the best mathematically-proven 
quality are those based on the RANLUX algorithm.

1754 k ints/sec,    870 k doubles/sec, taus
1613 k ints/sec,    855 k doubles/sec, gfsr4
1370 k ints/sec,    769 k doubles/sec, mt19937
 565 k ints/sec,    571 k doubles/sec, ranlxs0
 400 k ints/sec,    405 k doubles/sec, ranlxs1
 490 k ints/sec,    389 k doubles/sec, mrg
 407 k ints/sec,    297 k doubles/sec, ranlux
 243 k ints/sec,    254 k doubles/sec, ranlxd1
 251 k ints/sec,    253 k doubles/sec, ranlxs2
 238 k ints/sec,    215 k doubles/sec, cmrg
 247 k ints/sec,    198 k doubles/sec, ranlux389
 141 k ints/sec,    140 k doubles/sec, ranlxd2

1852 k ints/sec,    935 k doubles/sec, ran3
 813 k ints/sec,    575 k doubles/sec, ran0
 787 k ints/sec,    476 k doubles/sec, ran1
 379 k ints/sec,    292 k doubles/sec, ran2



<Prev in Thread] Current Thread [Next in Thread>