[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 
library and had good properties.

Returns integer pseudorandom numbers uniformly distributed within 
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.

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>