Random number generators

Random number generators

[Heiko Bauke]

[-- Attachment #1: Type: text/plain, Size: 1585 bytes --]

Hello,

some years ago I provided some patches for serveral pseudo-random number
generators.  In these patches I focussed on correctness and portability
not on performance.  

For (multiple) linear congruential generators with prime moduls a seedup
up to a factor 15 can be gained by switching from a implementation that
uses 32-bit arithmetic to 64-bit arithmetic.  The source files attached
to this mail contain compile time switches, that check if the data type
long long is available and choose a 64-bit implementation if
appropriate.

#if defined(LLONG_MAX)
  /* 64-bit implemtation */
#else
  /* 32-bit implemtation */
#endif

The macro is only defined if the gcc switch --std=c99 is specified.

Instead of checking for LLONG_MAX it would be better to check in the
configure skript, if the data type long long is available and to define
a HAVE_LONG_LONG macro in config.h. But unfortunately I do not know
enough about autotools to integrate such a machnism.

My patches contain also some minor (aesthetic) correktions for other
generators and for the documenation of random number generators. In
particular I updated the performance measurements at the end of the
chapter about random number generators.

I would be pleased if my patches will find the way into to official gsl
source code.


	sincerely yours

	Heiko

-- 
-- Wer lügt, hat die Wahrheit immerhin gedacht.
-- (Oliver Hassencamp, dt. Schriftsteller, 1921-1987)
-- Cluster Computing @ http://www.clustercomputing.de
--       Heiko Bauke @ http://www.uni-magdeburg.de/bauke

[-- Attachment #2: random_patch.tgz --]
[-- Type: application/x-gtar, Size: 17015 bytes --]

Re: Random number generators

[Jochen Küpper]

[-- Attachment #1: Type: text/plain, Size: 961 bytes --]

Heiko Bauke <heiko.bauke@physik.uni-magdeburg.de> writes:

> For (multiple) linear congruential generators with prime moduls a
> seedup up to a factor 15 can be gained by switching from a
> implementation that uses 32-bit arithmetic to 64-bit arithmetic.

Wow. I would like to see that in GSL for sure;)

> Instead of checking for LLONG_MAX it would be better to check in the
> configure skript, if the data type long long is available and to define
> a HAVE_LONG_LONG macro in config.h. But unfortunately I do not know
> enough about autotools to integrate such a machnism.

,----
| AC_CHECK_TYPES([long long])
`----

Maybe it would be better to check for int64_t?
,----
| AC_CHECK_TYPES([int64_t])
`----

Greetings,
Jochen
-- 
Einigkeit und Recht und Freiheit                http://www.Jochen-Kuepper.de
    Liberté, Égalité, Fraternité                GnuPG key: CC1B0B4D
        (Part 3 you find in my messages before fall 2003.)

[-- Attachment #2: Type: application/pgp-signature, Size: 188 bytes --]

Re: Random number generators

[Brian Gough]

Heiko Bauke writes:
 > some years ago I provided some patches for serveral pseudo-random number
 > generators.  In these patches I focussed on correctness and portability
 > not on performance.  
 > 
 > For (multiple) linear congruential generators with prime moduls a seedup
 > up to a factor 15 can be gained by switching from a implementation that
 > uses 32-bit arithmetic to 64-bit arithmetic.  The source files attached
 > to this mail contain compile time switches, that check if the data type
 > long long is available and choose a 64-bit implementation if
 > appropriate.

Hello,

Thanks, I'll update the documentation.  For the simple generators I
don't think it is worth trying to optimise the code itself for
64-bits, as they are only examples.  If there are some optimisations
for ranlux I'd add them.

-- 
Brian Gough

Re: Random number generators

[Heiko Bauke]

Hello,

On Mon, 9 Jan 2006 21:14:15 +0000
Brian Gough <bjg@network-theory.co.uk> wrote:

> If there are some optimisations
> for ranlux I'd add them.

unfortunately there isn't much room for optimasation. The ranlux-family
is based on a generator with quite bad statistical properties, a so
called subtract-with-carry (SWC) generator. A quallity enhancement is
achieved by throwing away large chunks of the SWC sequence. If the
chunks of discarded numbers are too small, systematic erros may occur in
large scale simulations [1].  This makes ranlux-family of pseudorandom
number genrators intrinsically slow.


	Heiko


[1] http://de.arxiv.org/abs/hep-lat/9805017

-- 
-- Geld fällt nicht vom Himmel. Man muß es sich hier auf Erden verdienen.
-- (Margaret Thatcher, brit. Politikerin)
-- Cluster Computing @ http://www.clustercomputing.de
--       Heiko Bauke @ http://www.uni-magdeburg.de/bauke