Jump to page: 1 2
Thread overview
std.random and mersenne twister
Jul 20, 2012
Andrea Fontana
Jul 20, 2012
monarch_dodra
Jul 20, 2012
Andrea Fontana
Jul 20, 2012
Craig Dillabaugh
Jul 20, 2012
Andrea Fontana
Jul 20, 2012
Craig Dillabaugh
Jul 21, 2012
monarch_dodra
Jul 21, 2012
David Nadlinger
Jul 24, 2012
monarch_dodra
Jul 24, 2012
Andrea Fontana
Jul 24, 2012
Jonathan M Davis
Jul 25, 2012
Andrea Fontana
Jul 25, 2012
monarch_dodra
Jul 25, 2012
Andrea Fontana
Jul 30, 2012
monarch_dodra
July 20, 2012
I read that default RNG in phobos is Mersenne Twister.

I think it would be a good idea to replace it with
complementary-multiply-with-carry (cmwc). CMWC is faster (use simpler
math), has a longer period (standard implementation has a 2^131104
period vs 2^19937 of current MT implementation in phobos) and passed
diehard tests (mt passes them too)

And of course it's very easy to implement: http://en.wikipedia.org/wiki/Multiply-with-carry#Implementation


July 20, 2012
On Friday, 20 July 2012 at 09:47:52 UTC, Andrea Fontana wrote:
> I read that default RNG in phobos is Mersenne Twister.
>
> I think it would be a good idea to replace it with
> complementary-multiply-with-carry (cmwc). CMWC is faster (use simpler
> math), has a longer period (standard implementation has a 2^131104
> period vs 2^19937 of current MT implementation in phobos) and passed
> diehard tests (mt passes them too)
>
> And of course it's very easy to implement:
> http://en.wikipedia.org/wiki/Multiply-with-carry#Implementation

I'd say the problem is that it is not a very widespread or known PRNG.

While I wouldn't be against adding it to the library ("I see no reason not to add it"), making it the _default_ PRNG is a whole other story.

Users that choose "default" want something reliable, documented, trustworthy etc...

Multiply With Carry seems like it is Cutting Edge to me, not yet widespread, known or tested. I'd say it should only be used by those that explicitly request it's usage.
July 20, 2012
On 20/07/12 11:47, Andrea Fontana wrote:
> I think it would be a good idea to replace it with
> complementary-multiply-with-carry (cmwc). CMWC is faster (use simpler math), has
> a longer period (standard implementation has a 2^131104 period vs 2^19937 of
> current MT implementation in phobos) and passed diehard tests (mt passes them too)

That reminds me ... it might be an idea to implement the Diehard tests for D, as part of a test suite for std.random.

Rigorously testing pseudorandom functionality is not really my area of expertise, but it's something that is important to do for any code that might have a scientific application (quite early on in my experience of writing simulations, I had the lovely experience of having to rewrite and rerun a whole load of code because of poor RNG choice; fortunately it didn't affect anything that had been published).  Some years ago, there was an observed departure from randomness in the default MATLAB RNG which must have resulted in all kinds of false conclusions and results being out there in the scientific literature.

On the subject of default RNG -- the use of Mersenne Twister is very widespread as a default method (used in MATLAB/Octave, R, and it's the recommended method in GSL and Boost).  So it may be a good default choice for D just by virtue of easy comparison with other tools.
July 20, 2012
CMWC is  proven to be a valid method and it passes diehard tests. It was written by prof. George Marsiglia (he developed xorshift too - included in std.random). He was one of the best experts in PRNG.

He also developed the "Marsiglia's Theorem" where he demonstrate that
LCG (that is the default algorithm for many languages  for ex: glibc and
vc++ lib, ...) has big issues.
LCG is very widespread but d doesn't use it (phew!). If a user know
difference between PRNG algorithms can use MT, but as default for people
that use weak C rand() function as default (that neither passes diehard
tests) it can just be a good improvement (why should we give them MT
that is slower than CMWC if they neither know default rand() weakness?)

MT has a complex implementation, I hope std.random MT was tested :)

Il giorno ven, 20/07/2012 alle 13.16 +0200, monarch_dodra ha scritto:

> On Friday, 20 July 2012 at 09:47:52 UTC, Andrea Fontana wrote:
> > I read that default RNG in phobos is Mersenne Twister.
> >
> > I think it would be a good idea to replace it with
> > complementary-multiply-with-carry (cmwc). CMWC is faster (use
> > simpler
> > math), has a longer period (standard implementation has a
> > 2^131104
> > period vs 2^19937 of current MT implementation in phobos) and
> > passed
> > diehard tests (mt passes them too)
> >
> > And of course it's very easy to implement: http://en.wikipedia.org/wiki/Multiply-with-carry#Implementation
> 
> I'd say the problem is that it is not a very widespread or known PRNG.
> 
> While I wouldn't be against adding it to the library ("I see no reason not to add it"), making it the _default_ PRNG is a whole other story.
> 
> Users that choose "default" want something reliable, documented, trustworthy etc...
> 
> Multiply With Carry seems like it is Cutting Edge to me, not yet widespread, known or tested. I'd say it should only be used by those that explicitly request it's usage.




July 20, 2012
On 20/07/12 14:51, Andrea Fontana wrote:
> He also developed the "Marsiglia's Theorem" where he demonstrate that LCG (that
> is the default algorithm for many languages  for ex: glibc and vc++ lib, ...)
> has big issues.

C and C++ have the bad luck to have been created before many of the high-quality PRNGs were developed.  A lot of scientific software now has MT as the default. I'd personally never heard of CMWC before this email exchange -- a nice discovery :-)

> MT has a complex implementation, I hope std.random MT was tested :)

I doubt there's anything wrong with the MT implementation per se; it looks largely like a close match to that in the Boost C++ random library, and they certainly generate identical output.  There is an issue with the seeding, that D's MT can only take a number as seed, not a sequence of numbers -- see:
http://forum.dlang.org/thread/jr0luj$1ctj$1@digitalmars.com

But I agree that there should be a proper set of unittests for the PRNGs that really check their implementation.

Personally if there is a flaw in the current D random number generation, my money would be on the unpredictableSeed being responsible.  It's a hunch rather than something I can justify technically, but the method of generating that seed looks too simple to me -- I'd be worried that for some PRNGs, different threads might wind up with correlated random sequences by accident, because the different unpredictableSeeds would not be different enough.

So, given that D looks to be gaining traction in various areas of scientific simulation, I think it'd be well worth trying to make sure that multithreaded pseudo-random number generation is really rigorously tested.  Unfortunately I don't know what kinds of test would be appropriate here.
July 20, 2012
On Friday, 20 July 2012 at 12:51:25 UTC, Andrea Fontana wrote:
> CMWC is  proven to be a valid method and it passes diehard tests. It was
> written by prof. George Marsiglia (he developed xorshift too - included
> in std.random). He was one of the best experts in PRNG.
>
> He also developed the "Marsiglia's Theorem" where he demonstrate that
> LCG (that is the default algorithm for many languages  for ex: glibc and
> vc++ lib, ...) has big issues.
> LCG is very widespread but d doesn't use it (phew!). If a user know
> difference between PRNG algorithms can use MT, but as default for people
> that use weak C rand() function as default (that neither passes diehard
> tests) it can just be a good improvement (why should we give them MT
> that is slower than CMWC if they neither know default rand() weakness?)
>
> MT has a complex implementation, I hope std.random MT was tested :)
>
> Il giorno ven, 20/07/2012 alle 13.16 +0200, monarch_dodra ha scritto:
>
>> On Friday, 20 July 2012 at 09:47:52 UTC, Andrea Fontana wrote:
>> > I read that default RNG in phobos is Mersenne Twister.
>> >
>> > I think it would be a good idea to replace it with
>> > complementary-multiply-with-carry (cmwc). CMWC is faster (use simpler
>> > math), has a longer period (standard implementation has a 2^131104
>> > period vs 2^19937 of current MT implementation in phobos) and passed
>> > diehard tests (mt passes them too)
>> >
>> > And of course it's very easy to implement:
>> > http://en.wikipedia.org/wiki/Multiply-with-carry#Implementation
>> 
>> I'd say the problem is that it is not a very widespread or known PRNG.
>> 
>> While I wouldn't be against adding it to the library ("I see no reason not to add it"), making it the _default_ PRNG is a whole other story.
>> 
>> Users that choose "default" want something reliable, documented, trustworthy etc...
>> 
>> Multiply With Carry seems like it is Cutting Edge to me, not yet widespread, known or tested. I'd say it should only be used by those that explicitly request it's usage.

But Mersenne Twister has a cooler name :o)

'Multiply with carry' is so blah. You'll need to come up with a
sexy new name for it.

Cheers,
Craig

July 20, 2012
Il giorno ven, 20/07/2012 alle 16.05 +0200, Craig Dillabaugh ha scritto:

> On Friday, 20 July 2012 at 12:51:25 UTC, Andrea Fontana wrote:
> > CMWC is  proven to be a valid method and it passes diehard
> > tests. It was
> > written by prof. George Marsiglia (he developed xorshift too -
> > included
> > in std.random). He was one of the best experts in PRNG.
> >
> > He also developed the "Marsiglia's Theorem" where he
> > demonstrate that
> > LCG (that is the default algorithm for many languages  for ex:
> > glibc and
> > vc++ lib, ...) has big issues.
> > LCG is very widespread but d doesn't use it (phew!). If a user
> > know
> > difference between PRNG algorithms can use MT, but as default
> > for people
> > that use weak C rand() function as default (that neither passes
> > diehard
> > tests) it can just be a good improvement (why should we give
> > them MT
> > that is slower than CMWC if they neither know default rand()
> > weakness?)
> >
> > MT has a complex implementation, I hope std.random MT was tested :)
> >
> > Il giorno ven, 20/07/2012 alle 13.16 +0200, monarch_dodra ha scritto:
> >
> >> On Friday, 20 July 2012 at 09:47:52 UTC, Andrea Fontana wrote:
> >> > I read that default RNG in phobos is Mersenne Twister.
> >> >
> >> > I think it would be a good idea to replace it with
> >> > complementary-multiply-with-carry (cmwc). CMWC is faster
> >> > (use simpler
> >> > math), has a longer period (standard implementation has a
> >> > 2^131104
> >> > period vs 2^19937 of current MT implementation in phobos)
> >> > and passed
> >> > diehard tests (mt passes them too)
> >> >
> >> > And of course it's very easy to implement: http://en.wikipedia.org/wiki/Multiply-with-carry#Implementation
> >> 
> >> I'd say the problem is that it is not a very widespread or known PRNG.
> >> 
> >> While I wouldn't be against adding it to the library ("I see no reason not to add it"), making it the _default_ PRNG is a whole other story.
> >> 
> >> Users that choose "default" want something reliable, documented, trustworthy etc...
> >> 
> >> Multiply With Carry seems like it is Cutting Edge to me, not yet widespread, known or tested. I'd say it should only be used by those that explicitly request it's usage.
> 
> But Mersenne Twister has a cooler name :o)
> 
> 'Multiply with carry' is so blah. You'll need to come up with a sexy new name for it.
> 
> Cheers,
> Craig
> 


Marsaglia Tornado?



July 20, 2012
On Friday, 20 July 2012 at 14:11:18 UTC, Andrea Fontana wrote:
> Il giorno ven, 20/07/2012 alle 16.05 +0200, Craig Dillabaugh ha scritto:
>
>> On Friday, 20 July 2012 at 12:51:25 UTC, Andrea Fontana wrote:
clip...
>> 
>> But Mersenne Twister has a cooler name :o)
>> 
>> 'Multiply with carry' is so blah. You'll need to come up with a
>> sexy new name for it.
>> 
>> Cheers,
>> Craig
>> 
>
>
> Marsaglia Tornado?
Very nice ... and it even uses the same acronym.
Craig

July 20, 2012
On 7/20/12 8:51 AM, Andrea Fontana wrote:
> CMWC is proven to be a valid method and it passes diehard tests. It was
> written by prof. George Marsiglia (he developed xorshift too - included
> in std.random). He was one of the best experts in PRNG.

Would be great if you wanted to contribute an implementation of CMWC to std.random.

Thanks,

Andrei

July 21, 2012
On Friday, 20 July 2012 at 21:45:17 UTC, Andrei Alexandrescu wrote:
> On 7/20/12 8:51 AM, Andrea Fontana wrote:
>> CMWC is proven to be a valid method and it passes diehard tests. It was
>> written by prof. George Marsiglia (he developed xorshift too - included
>> in std.random). He was one of the best experts in PRNG.
>
> Would be great if you wanted to contribute an implementation of CMWC to std.random.
>
> Thanks,
>
> Andrei

That's something I could undertake confidently.

Writing both an actual engine, and creating aliases for pre-optimized schemes.

I'd just have to wait to finish my current development (I don't know how to have parallel forks).
« First   ‹ Prev
1 2