random number generation algorithms

random number generation algorithms

[Heiko Bauke]

Hi,

quite some time ago (in 2003) I provided some fixes for some random 
number generation algorithms to the GSL.  My implementation was mainly 
focused on correctness and portability.  Thus it was implemented in C89, 
which is portable but does not guarantee to have a 64 bit integer type.

The performance of some random number generation algorithms, however, 
can benefit a lot from an implementation that uses 64 integers for 
intermediate values.  This holds often not only for genuine 64 bit 
architectures but also for 32 bit CPUs where the compiler emits more 
complex code to emulate 64 bit arithmetics.  Thus I reimplemented these 
generators in C99 and 64 bit arithmetics and wrote a simple benchmark 
that generates a few million random floating point numbers, sums them 
up, prints this sum and the elapsed time.  For some generators the 
performance difference is substantial.

How can I submit my revised code?  The code is backward compatible to 
C89 via preprocessor switches.

Here my results to give you an idea of the performance impact of the new 
implementation:  (Note that a substantial amount of time is actually 
spent in making just the function call to the generator's get routine, 
performing the loop and so on.  An empty get function, yields a running 
time of 0.6 sec. on my computer.)

Current code:

generator type: cmrg
time = 3.13553 sec.
sum = 67102809.40374

generator type: mrg
time = 1.85819 sec.
sum = 67103626.29699

generator type: minstd
time = 0.87232 sec.
sum = 67112858.69032

generator type: knuthran2
time = 4.21356 sec.
sum = 67111295.37067

generator type: fishman18
time = 2.28581 sec.
sum = 67112445.93199

generator type: fishman20
time = 0.90139 sec.
sum = 67104902.87940

generator type: lecuyer21
time = 1.05779 sec.
sum = 67107194.15891

generator type: fishman2x
time = 1.14781 sec.
sum = 67118684.47031



New code:

generator type: cmrg
time = 1.03106 sec.
sum = 67102809.40374

generator type: mrg
time = 0.72681 sec.
sum = 67103626.29699

generator type: minstd
time = 0.66231 sec.
sum = 67112858.69032

generator type: knuthran2
time = 0.70982 sec.
sum = 67111295.37067

generator type: fishman18
time = 0.66595 sec.
sum = 67112445.93199

generator type: fishman20
time = 0.66089 sec.
sum = 67104902.87940

generator type: lecuyer21
time = 0.80597 sec.
sum = 67107194.15891

generator type: fishman2x
time = 0.90818 sec.
sum = 67118684.47031


	Regards,

	Heiko

-- 
-- Number Crunch Blog @ https://www.numbercrunch.de
--  Cluster Computing @ http://www.clustercomputing.de
--       Professional @ https://www.mpi-hd.mpg.de/personalhomes/bauke
--  Social Networking @ https://www.researchgate.net/profile/Heiko_Bauke

Re: random number generation algorithms

[Patrick Alken]

Hello, sorry for the late reply. Can you make a patch against the latest
git repository and send it to me?

On 11/14/2017 01:39 AM, Heiko Bauke wrote:
> Hi,
>
> quite some time ago (in 2003) I provided some fixes for some random
> number generation algorithms to the GSL.  My implementation was mainly
> focused on correctness and portability.  Thus it was implemented in
> C89, which is portable but does not guarantee to have a 64 bit integer
> type.
>
> The performance of some random number generation algorithms, however,
> can benefit a lot from an implementation that uses 64 integers for
> intermediate values.  This holds often not only for genuine 64 bit
> architectures but also for 32 bit CPUs where the compiler emits more
> complex code to emulate 64 bit arithmetics.  Thus I reimplemented
> these generators in C99 and 64 bit arithmetics and wrote a simple
> benchmark that generates a few million random floating point numbers,
> sums them up, prints this sum and the elapsed time.  For some
> generators the performance difference is substantial.
>
> How can I submit my revised code?  The code is backward compatible to
> C89 via preprocessor switches.
>
> Here my results to give you an idea of the performance impact of the
> new implementation:  (Note that a substantial amount of time is
> actually spent in making just the function call to the generator's get
> routine, performing the loop and so on.  An empty get function, yields
> a running time of 0.6 sec. on my computer.)
>
> Current code:
>
> generator type: cmrg
> time = 3.13553 sec.
> sum = 67102809.40374
>
> generator type: mrg
> time = 1.85819 sec.
> sum = 67103626.29699
>
> generator type: minstd
> time = 0.87232 sec.
> sum = 67112858.69032
>
> generator type: knuthran2
> time = 4.21356 sec.
> sum = 67111295.37067
>
> generator type: fishman18
> time = 2.28581 sec.
> sum = 67112445.93199
>
> generator type: fishman20
> time = 0.90139 sec.
> sum = 67104902.87940
>
> generator type: lecuyer21
> time = 1.05779 sec.
> sum = 67107194.15891
>
> generator type: fishman2x
> time = 1.14781 sec.
> sum = 67118684.47031
>
>
>
> New code:
>
> generator type: cmrg
> time = 1.03106 sec.
> sum = 67102809.40374
>
> generator type: mrg
> time = 0.72681 sec.
> sum = 67103626.29699
>
> generator type: minstd
> time = 0.66231 sec.
> sum = 67112858.69032
>
> generator type: knuthran2
> time = 0.70982 sec.
> sum = 67111295.37067
>
> generator type: fishman18
> time = 0.66595 sec.
> sum = 67112445.93199
>
> generator type: fishman20
> time = 0.66089 sec.
> sum = 67104902.87940
>
> generator type: lecuyer21
> time = 0.80597 sec.
> sum = 67107194.15891
>
> generator type: fishman2x
> time = 0.90818 sec.
> sum = 67118684.47031
>
>
>     Regards,
>
>     Heiko
>