commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
Subject Re: [math] Improving tests and performance of RandomGenerator implementations
Date Mon, 01 Aug 2011 08:31:57 GMT
Hi Phil,

----- Mail original -----
> In my own applications, I noticed what appears to be poor
> performance in the nextInt(int) method of the Mersenne twister,
> which I was using to *improve* speed.  I think that for small n, the
> default implementation in BistreamGenerator may be running too many
> iterations.

Mersenne twister uses a quite large pool. It creates pseudo-random bits
by twisting it and creates large bunches at a time (624 words at a time).
Hence when you ask for large sets, you should have several calls that
return fast, and one call that takes a longer time to generate another
large pool.

So good performances are obtained for generating large sets, not small sets.

Well generators should be faster and are preferred over Mersenne twister now,
which is now an old generator. Well generators also have large pools, but they
don't generate bits in large batches in advance, they do generate a few words
at a time.

> I am still figuring out how the code works, but I
> thought it would be good to run some benchmarks - using Gilles' new
> stuff - against the Harmony implementation in java.util.Random of
> this method.  That led me to notice that there are no unit tests for
> BitstreamGenerator.  I propose that we add
>  0) RandomGeneratorAbstractTest with an abstract makeGenerator
> method including fixed seed tests for all RandomGenerator methods
>  1) BitstreamGeneratorTest extending RandomGeneratorAbstractTest
> implementing makeGenerator with a BitStreamGenerator that uses the
> JDK generator for next(int)
>  2) Make the test classes for Mersenne and Weil generators extend
> RandomGeneratorAbstractTest, moving redundant tests up into the base
> class
> Sound reasonable?


> Also, any recollection why we are using a
> different implementation in BitStreamGenerator for next(int) than
> Harmony and the JDK use?

I don't understand what you mean. next(int) is used to generate the raw
bits and is the heart of each generator. Each generator has its own
implementation. Replacing next(int) by the JDK generation would imply
dropping completely Mersenne twister and Well generators.

Mersenne twister and Well should be fast for generating large sets, but
most importantly they have very good and *proven* properties (equidistribution
on large dimensions, null correlation, maximal period ...). These properties
are essential for example in Monte-Carlo simulations with lots of variables that
must be independent or have controlled correlations.


> The Harmony impl is almost identical to
> what is documented in the JDK javadoc.
> Phil
> ---------------------------------------------------------------------
> To unsubscribe, e-mail:
> For additional commands, e-mail:

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message