mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
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



  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®