www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - std.random and mersenne twister

reply Andrea Fontana <nospam example.com> writes:
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

I read that default RNG in phobos is Mersenne Twister.=20

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
Jul 20 2012
next sibling parent reply "monarch_dodra" <monarchdodra gmail.com> writes:
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.
Jul 20 2012
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Jul 20 2012
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 7/21/12 6:28 AM, monarch_dodra wrote:
 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).

That would be awesome (both RNG and getting fluent with parallel forks). Andrei
Jul 21 2012
prev sibling next sibling parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
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.
Jul 20 2012
prev sibling next sibling parent Andrea Fontana <nospam example.com> writes:
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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?)=20

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

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=20
 simpler
 math), has a longer period (standard implementation has a=20
 2^131104
 period vs 2^19937 of current MT implementation in phobos) and=20
 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=20 PRNG. =20 While I wouldn't be against adding it to the library ("I see no=20 reason not to add it"), making it the _default_ PRNG is a whole=20 other story. =20 Users that choose "default" want something reliable, documented,=20 trustworthy etc... =20 Multiply With Carry seems like it is Cutting Edge to me, not yet=20 widespread, known or tested. I'd say it should only be used by=20 those that explicitly request it's usage.

Jul 20 2012
prev sibling next sibling parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
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.
Jul 20 2012
prev sibling next sibling parent "Craig Dillabaugh" <cdillaba cg.scs.carleton.ca> writes:
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
Jul 20 2012
prev sibling next sibling parent Andrea Fontana <nospam example.com> writes:
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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=20
 tests. It was
 written by prof. George Marsiglia (he developed xorshift too -=20
 included
 in std.random). He was one of the best experts in PRNG.

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

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

 Il giorno ven, 20/07/2012 alle 13.16 +0200, monarch_dodra ha=20
 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=20
 (use simpler
 math), has a longer period (standard implementation has a=20
 2^131104
 period vs 2^19937 of current MT implementation in phobos)=20
 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=20 known PRNG. =20 While I wouldn't be against adding it to the library ("I see=20 no reason not to add it"), making it the _default_ PRNG is a=20 whole other story. =20 Users that choose "default" want something reliable,=20 documented, trustworthy etc... =20 Multiply With Carry seems like it is Cutting Edge to me, not=20 yet widespread, known or tested. I'd say it should only be=20 used by those that explicitly request it's usage.


But Mersenne Twister has a cooler name :o) =20 'Multiply with carry' is so blah. You'll need to come up with a sexy new name for it. =20 Cheers, Craig =20

Marsaglia Tornado?
Jul 20 2012
prev sibling next sibling parent "Craig Dillabaugh" <cdillaba cg.scs.carleton.ca> writes:
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:


 
 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?

Craig
Jul 20 2012
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
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).
Jul 21 2012
prev sibling next sibling parent "David Nadlinger" <see klickverbot.at> writes:
On Saturday, 21 July 2012 at 10:28:58 UTC, monarch_dodra wrote:
 I'd just have to wait to finish my current development (I don't 
 know how to have parallel forks).

Just create a single GitHub fork with multiple branches, one for each feature/bug you are working on. After pushing them to GitHub, you can create separate pull requests for each of them. David
Jul 21 2012
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Saturday, 21 July 2012 at 16:32:56 UTC, Andrei Alexandrescu 
wrote:
 On 7/21/12 6:28 AM, monarch_dodra wrote:
 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).

That would be awesome (both RNG and getting fluent with parallel forks). Andrei

I gave it a shot, but I just couldn't find enough documentation on CMWC to write a correctly parametrizable engine. I honestly don't have much to go by other than wikipedia's example. I could force the implementation, but I'd have zero faith in it's reliability. That said, I don't think it would be a bad idea to add a Lagged Fibonacci generator first. The generator already exists in boost, and is much more documented. The actual development would just require a port. I'll try to get *that* done, but for CMWC, I'm out. Sorry. The bright side is I learned to parallel fork :D
Jul 24 2012
prev sibling next sibling parent "Andrea Fontana" <nospam example.com> writes:
On Tuesday, 24 July 2012 at 16:09:15 UTC, monarch_dodra wrote:
 On Saturday, 21 July 2012 at 16:32:56 UTC, Andrei Alexandrescu 
 wrote:
 On 7/21/12 6:28 AM, monarch_dodra wrote:
 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).

That would be awesome (both RNG and getting fluent with parallel forks). Andrei

I gave it a shot, but I just couldn't find enough documentation on CMWC to write a correctly parametrizable engine. I honestly don't have much to go by other than wikipedia's example. I could force the implementation, but I'd have zero faith in it's reliability. That said, I don't think it would be a bad idea to add a Lagged Fibonacci generator first. The generator already exists in boost, and is much more documented. The actual development would just require a port. I'll try to get *that* done, but for CMWC, I'm out. Sorry. The bright side is I learned to parallel fork :D

I see there's an implementation in tango for d1, with params too :) Have you looked for Marsaglia's paper?
Jul 24 2012
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Wednesday, July 25, 2012 00:01:03 Andrea Fontana wrote:
 I see there's an implementation in tango for d1, with params too

Which does Phobos no good unless you can get permission from the author(s) of that code to switch the license to Boost. Without that, you should probably avoid even looking at it if you're going to be working on an implementation for it so that you eliminate any risk of licensing issues. There's a lot of great work which went into Tango, but as long as its license is incompatible with Boost, it can't be put into Phobos at all, though it can still obviously be used by those who want to (especially now that there's a D2 fork of Tango). - Jonathan M Davis
Jul 24 2012
prev sibling next sibling parent Andrea Fontana <nospam example.com> writes:
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

He want docs, here he can understand how it works.=20

Some good params for CMWC can be found here and was provided by G.
Marsaglia:
http://blacklen.wordpress.com/2011/05/15/prng-3-complementary-multiply-with=
-carry/

A code for java "you're free to use this code as you want" can be find
here:
http://www.javaprogrammingforums.com/blogs/helloworld922/11-complimentary-m=
ultiply-carry-better-way-generate-pseudo-random-numbers.html

Here some code and overview from george marsaglia:
http://school.anhb.uwa.edu.au/personalpages/kwessen/shared/Marsaglia03.html

Some considerations:
http://www.powerbasic.com/support/pbforums/showthread.php?t=3D50216


Il giorno mar, 24/07/2012 alle 18.18 -0400, Jonathan M Davis ha scritto:

 On Wednesday, July 25, 2012 00:01:03 Andrea Fontana wrote:
 I see there's an implementation in tango for d1, with params too

Which does Phobos no good unless you can get permission from the author(s=

 that code to switch the license to Boost. Without that, you should probab=

 avoid even looking at it if you're going to be working on an implementati=

 for it so that you eliminate any risk of licensing issues. There's a lot =

 great work which went into Tango, but as long as its license is incompati=

 with Boost, it can't be put into Phobos at all, though it can still obvio=

 be used by those who want to (especially now that there's a D2 fork of Ta=

=20
 - Jonathan M Davis

Jul 25 2012
prev sibling next sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
Thanks for the links, and the info regarding copyrights. I'll 
stick with my decision to *start* with Lagged Fibonacci. I'll let 
the experience of that decide for me if I want to tackle CMWC or 
not (provided I even succeed with LF).

PS: I like the name Marsaglia Tornado, but the initials are mt...
Jul 25 2012
prev sibling next sibling parent Andrea Fontana <nospam example.com> writes:
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Of course it was a joke :)

Il giorno mer, 25/07/2012 alle 10.41 +0200, monarch_dodra ha scritto:

 PS: I like the name Marsaglia Tornado, but the initials are mt...

Jul 25 2012
prev sibling parent "monarch_dodra" <monarchdodra gmail.com> writes:
On Tuesday, 24 July 2012 at 16:09:15 UTC, monarch_dodra wrote:
 That said, I don't think it would be a bad idea to add a Lagged 
 Fibonacci generator first. The generator already exists in 
 boost, and is much more documented. The actual development 
 would just require a port.

Hi There! I wrote the port. https://github.com/D-Programming-Language/phobos/pull/727 It works as intended, AFAIK, as it generates the exact same sequence that boost does. I'd be mighty pleased to have code review done on it. The details are on the pull page, but I guess you can also leave some feedback here.
Jul 30 2012