From: Stephen Hemminger <shemminger@osdl.org>
To: root@chaos.analogic.com
Cc: Andreas Dilger <adilger@clusterfs.com>,
Jean-Luc Cooke <jlcooke@certainkey.com>,
"David S. Miller" <davem@redhat.com>,
Alan Cox <alan@lxorguk.ukuu.org.uk>,
"Theodore Ts'o" <tytso@mit.edu>,
netdev@oss.sgi.com, Linux kernel <linux-kernel@vger.kernel.org>
Subject: Re: [RFC] enhanced version of net_random()
Date: Mon, 23 Aug 2004 10:05:47 -0700 [thread overview]
Message-ID: <20040823100547.33b7a448@dell_ss3.pdx.osdl.net> (raw)
In-Reply-To: <Pine.LNX.4.53.0408201518250.25319@chaos>
> 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
next prev parent reply other threads:[~2004-08-23 17:07 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
2004-08-12 17:48 Stephen Hemminger
2004-08-12 19:48 ` David S. Miller
2004-08-13 18:51 ` Stephen Hemminger
2004-08-13 19:28 ` Andi Kleen
2004-08-16 6:27 ` David S. Miller
2004-08-12 20:02 ` Ben Greear
2004-08-20 17:59 ` Jean-Luc Cooke
2004-08-20 18:47 ` David S. Miller
2004-08-20 18:59 ` Andreas Dilger
2004-08-20 19:22 ` Richard B. Johnson
2004-08-20 19:48 ` David S. Miller
2004-08-20 19:53 ` Jean-Luc Cooke
2004-08-22 15:04 ` Andi Kleen
2004-08-23 17:05 ` Stephen Hemminger [this message]
2004-08-23 18:09 ` Richard B. Johnson
2004-08-20 21:24 ` Lee Revell
2004-08-20 23:55 ` Alan Cox
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20040823100547.33b7a448@dell_ss3.pdx.osdl.net \
--to=shemminger@osdl.org \
--cc=adilger@clusterfs.com \
--cc=alan@lxorguk.ukuu.org.uk \
--cc=davem@redhat.com \
--cc=jlcooke@certainkey.com \
--cc=linux-kernel@vger.kernel.org \
--cc=netdev@oss.sgi.com \
--cc=root@chaos.analogic.com \
--cc=tytso@mit.edu \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®