Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Mersenne Twister -- A Revised C++ Implementation

Reply
Thread Tools

Mersenne Twister -- A Revised C++ Implementation

 
 
Scott Robert Ladd
Guest
Posts: n/a
 
      01-05-2004
I've posted my revised C++ implementation of the Mersenne Twister at:

http://www.coyotegulch.com/libcoyote...istedRoad.html

This is "free-as-in-liberty" and "free-as-in-beer" code.

The Mersenne Twister is a "random number" generator invented by Makoto
Matsumoto and Takuji Nishimura; their website includes numerous
implementations of the algorithm.

Essentially, the Mersenne Twister is a very large linear-feedback shift
register. The algorithm operates on a 19,937 bit seed, stored in an
624-element array of 32-bit unsigned integers. The value 2^19937-1 is a
Mersenne prime; the technique for manipulating the seed is based on an
older "twisting" algorithm -- hence the name "Mersenne Twister".

An appealing aspect of the Mersenne Twister is its use of binary
operations -- as opposed to time-consuming multiplication -- for
generating numbers. The algorithm also has a very long period, and good
granularity. It is both fast and effective for non-cryptographic
applications.

--
Scott Robert Ladd
Coyote Gulch Productions (http://www.coyotegulch.com)
Software Invention for High-Performance Computing


 
Reply With Quote
 
 
 
 
tom_usenet
Guest
Posts: n/a
 
      01-05-2004
On Mon, 05 Jan 2004 13:31:04 GMT, Scott Robert Ladd
<(E-Mail Removed)> wrote:

>I've posted my revised C++ implementation of the Mersenne Twister at:
>
>http://www.coyotegulch.com/libcoyote...istedRoad.html
>
>This is "free-as-in-liberty" and "free-as-in-beer" code.
>
>The Mersenne Twister is a "random number" generator invented by Makoto
>Matsumoto and Takuji Nishimura; their website includes numerous
>implementations of the algorithm.
>
>Essentially, the Mersenne Twister is a very large linear-feedback shift
>register. The algorithm operates on a 19,937 bit seed, stored in an
>624-element array of 32-bit unsigned integers. The value 2^19937-1 is a
>Mersenne prime; the technique for manipulating the seed is based on an
>older "twisting" algorithm -- hence the name "Mersenne Twister".
>
>An appealing aspect of the Mersenne Twister is its use of binary
>operations -- as opposed to time-consuming multiplication -- for
>generating numbers. The algorithm also has a very long period, and good
>granularity. It is both fast and effective for non-cryptographic
>applications.


There is a mersenne twister in the new standard library extension
draft. It started out it boost - www.boost.org

Tom

C++ FAQ: http://www.parashift.com/c++-faq-lite/
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
 
Reply With Quote
 
 
 
 
Scott Robert Ladd
Guest
Posts: n/a
 
      01-05-2004
On Mon, 05 Jan 2004 15:35:13 +0000, tom_usenet wrote:

> On Mon, 05 Jan 2004 13:31:04 GMT, Scott Robert Ladd
> There is a mersenne twister in the new standard library extension
> draft. It started out it boost - www.boost.org


The library extension draft isn't an official part of any available
compiler. While it is possible to download and install the Boost
libraries, I know many people who have problems with the Boost licensing
and design.

Diversity is good; I wish Boost well.

--
Scott Robert Ladd
Coyote Gulch Productions (http://www.coyotegulch.com)
Software Invention for High-Performance Computing


 
Reply With Quote
 
Carsten Hansen
Guest
Posts: n/a
 
      01-05-2004

"Scott Robert Ladd" <(E-Mail Removed)> wrote in message
news(E-Mail Removed) m...
> I've posted my revised C++ implementation of the Mersenne Twister at:
>
> http://www.coyotegulch.com/libcoyote...istedRoad.html
>
> This is "free-as-in-liberty" and "free-as-in-beer" code.
>
> The Mersenne Twister is a "random number" generator invented by Makoto
> Matsumoto and Takuji Nishimura; their website includes numerous
> implementations of the algorithm.
>
> Essentially, the Mersenne Twister is a very large linear-feedback shift
> register. The algorithm operates on a 19,937 bit seed, stored in an
> 624-element array of 32-bit unsigned integers. The value 2^19937-1 is a
> Mersenne prime; the technique for manipulating the seed is based on an
> older "twisting" algorithm -- hence the name "Mersenne Twister".
>
> An appealing aspect of the Mersenne Twister is its use of binary
> operations -- as opposed to time-consuming multiplication -- for
> generating numbers. The algorithm also has a very long period, and good
> granularity. It is both fast and effective for non-cryptographic
> applications.
>
> --
> Scott Robert Ladd
> Coyote Gulch Productions (http://www.coyotegulch.com)
> Software Invention for High-Performance Computing
>
>


Your web page is full of errors.

The C/C++ Standard does not define rand.
Multiplication is not slow on today's processors. Bit shifting is on x86.
The Mersenne Twister is relative slow because it does
four table lookups
five shifts
eight bitwise operations
for each number.

Carsten Hansen


 
Reply With Quote
 
Ron Natalie
Guest
Posts: n/a
 
      01-05-2004

"Carsten Hansen" <(E-Mail Removed)> wrote in message news:_rhKb.283567$Ec1.9734887@bgtnsc05-
> The C/C++ Standard does not define rand.


It does define rand(). It doesn't however mandate the implementation
he includes in his document. The function that appears in the C standard
is not normative and exists just to show a possible impelementation. They
are for illustration purposes only (mostly showing that given the same starting
seed the requirement that the same pseudo-random sequence is generated).

 
Reply With Quote
 
Carsten Hansen
Guest
Posts: n/a
 
      01-05-2004

"Ron Natalie" <(E-Mail Removed)> wrote in message
news:3ff9a569$0$32305$(E-Mail Removed) m...
>
> "Carsten Hansen" <(E-Mail Removed)> wrote in message

news:_rhKb.283567$Ec1.9734887@bgtnsc05-
> > The C/C++ Standard does not define rand.

>
> It does define rand(). It doesn't however mandate the implementation
> he includes in his document. The function that appears in the C standard
> is not normative and exists just to show a possible impelementation.

They
> are for illustration purposes only (mostly showing that given the same

starting
> seed the requirement that the same pseudo-random sequence is generated).
>


You are of course correct.

I objected to Scott's claim on his web site that
"Standard C (and thus Standard C++) explicitly defines the following linear
congruential generator for implementing the rand and srand functions:"

Carsten Hansen




 
Reply With Quote
 
Scott Robert Ladd
Guest
Posts: n/a
 
      01-05-2004
On Mon, 05 Jan 2004 12:56:58 -0500, Ron Natalie wrote:

> It does define rand(). It doesn't however mandate the implementation
> he includes in his document. The function that appears in the C standard
> is not normative and exists just to show a possible impelementation. They
> are for illustration purposes only (mostly showing that given the same
> starting seed the requirement that the same pseudo-random sequence is
> generated).


No mandate exists, but I have seen compilers that use the "reference"
implementation. Unlike a function like sin, which should return consistent
results across platforms, rand() is quite variable -- and its use of
global values makes it unsuitable for many applications.

--
Scott Robert Ladd
Coyote Gulch Productions (http://www.coyotegulch.com)
Software Invention for High-Performance Computing


 
Reply With Quote
 
Scott Robert Ladd
Guest
Posts: n/a
 
      01-05-2004
On Mon, 05 Jan 2004 18:08:13 +0000, Carsten Hansen wrote:
> I objected to Scott's claim on his web site that
> "Standard C (and thus Standard C++) explicitly defines the following linear
> congruential generator for implementing the rand and srand functions:"


Explicit it *not* a synonym for mandated. rand() is one of the every few
fucntions for which the standard "suggests" a specific implementation.
Don't make a suggestion if you don't want people to follow it...

--
Scott Robert Ladd
Coyote Gulch Productions (http://www.coyotegulch.com)
Software Invention for High-Performance Computing


 
Reply With Quote
 
Scott Robert Ladd
Guest
Posts: n/a
 
      01-05-2004
On Mon, 05 Jan 2004 17:48:42 +0000, Carsten Hansen wrote:
> The C/C++ Standard does not define rand.


Yes it does; however, that is debated elsewhere in this thread.

> Multiplication is not slow on today's processors. Bit shifting is on x86.
> The Mersenne Twister is relative slow because it does
> four table lookups
> five shifts
> eight bitwise operations
> for each number.


Okay, I can write a one-line generator function that is vastly faster than
the Mersenne Twister -- of course, it won't be a very good generator (like
the one suggested in the C standard), but it will be fast.

The "minimal standard", as suggested by Knuth and others, involve many
operations; in general, Mersenne Twister is as faster or faster than any
other generator that has similar statistical properties. And a whole lot
of people seem to agree; you can find the cites in the article.

Two "errors", one of which isn't and the other a platform dependence.
Doesn't sound very "full of errors" to me. But thanks for the pointers.

--
Scott Robert Ladd
Coyote Gulch Productions (http://www.coyotegulch.com)
Software Invention for High-Performance Computing


 
Reply With Quote
 
Carsten Hansen
Guest
Posts: n/a
 
      01-05-2004

"Scott Robert Ladd" <(E-Mail Removed)> wrote in message
news(E-Mail Removed). ..
> On Mon, 05 Jan 2004 17:48:42 +0000, Carsten Hansen wrote:
> > The C/C++ Standard does not define rand.

>
> Yes it does; however, that is debated elsewhere in this thread.
>
> > Multiplication is not slow on today's processors. Bit shifting is on

x86.
> > The Mersenne Twister is relative slow because it does
> > four table lookups
> > five shifts
> > eight bitwise operations
> > for each number.

>
> Okay, I can write a one-line generator function that is vastly faster than
> the Mersenne Twister -- of course, it won't be a very good generator (like
> the one suggested in the C standard), but it will be fast.
>
> The "minimal standard", as suggested by Knuth and others, involve many
> operations; in general, Mersenne Twister is as faster or faster than any
> other generator that has similar statistical properties. And a whole lot
> of people seem to agree; you can find the cites in the article.
>
> Two "errors", one of which isn't and the other a platform dependence.
> Doesn't sound very "full of errors" to me. But thanks for the pointers.
>
> --
> Scott Robert Ladd
> Coyote Gulch Productions (http://www.coyotegulch.com)
> Software Invention for High-Performance Computing
>
>


Your claims about "a" and "m" in LCM, "a and m can take on only a very few
values" and "m most certainly being a prime", are false.
You claim about best LCM for 32-bit numbers is inconsistent. Is it a=16807
and m = 2147483647 or a=42871 and m=69621.
Knuth calls the first "adequate but less outstanding". Its result from the
spectral test is far below other 32-bit LCMs.

The random number generator Knuth has on his web site involves two table
lookups and one bitwise operation. Hence it is much faster than the Mersenne
Twister.

Marsaglia has many high quality random number generators involving far less
operations than the Mersenne Twister.
Here is a quote about the Mersenne Twister by Marsaglia: "But it requires an
elaborate C program and is slower than many RNGs that do as well in tests,
have comparable or longer periods and require only a few lines of code."

The Mersenne Twister claim to fame is mostly because of its cute name.

Your code show that you don't understand random number generation.
In get_rand_range you basically map [0, 4294963695] onto the range. That
cannot be done uniformly. That is part of the C FAQ.

Carsten Hansen



 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mac using Mersenne Twister in C g000we C Programming 3 03-05-2011 09:19 AM
Naive parallel implementation of Mersenne Twister random numbergenerator mjm2114@columbia.edu C Programming 0 06-04-2008 01:58 PM
Fast Mersenne Twister bearophileHUGS@lycos.com Python 0 05-15-2008 05:46 PM
Another Mersenne Twister question Simon C Programming 11 10-26-2006 04:12 AM
larger seeds for Mersenne jt Python 0 02-05-2004 04:41 AM



Advertisments