Re: Mersenne Twister -- A Revised C++ Implementation

From: galathaea (galathaea_at_excite.com)
Date: 01/06/04 

Date: Tue, 06 Jan 2004 01:16:16 GMT

"Scott Robert Ladd" wrote:
: I've posted my revised C++ implementation of the Mersenne Twister at:
:
: http://www.coyotegulch.com/libcoyote/TwistedRoad/TwistedRoad.html
:
: This is "free-as-in-liberty" and "free-as-in-beer" code.

Just a few comments about your site and code:

First, I wanted to thank you for taking the time to put this on the
internet. I believe making educational materials freely available is an
extremely important undertaking, and anyone who spends some free time to
publish an article explaining anything gets a thumbs up from me. The style
of your article is relaxed and an easy read, which is an additional
accomplishment. However, there are some technical inaccuracies that should
be pointed out.

First, you state:
"In this article, I'm concerned with the needs of stochastic algorithms,
games, and simulations. For those applications, a useful PRNG produces a
sequence of values such that every number in a given range has an equal
chance of being produced. This is what numericists refer to as a uniform
deviate."

And yet your code:

//--------------------------------------------------------------------------
-
// Obtain a psuedorandom integer in the range [lo,hi]
inline mtprng::int_type mtprng::get_rand_range(mtprng::int_type lo,
mtprng::int_type hi)
{
        // Local working storage
        real_type range = hi - lo + 1.0;

        // Use real value to caluclate range
        return lo + int_type(floor(range * get_rand_real2()));
}

displays the common error of nonuniform range mapping. This discrepancy
should probably be corrected (either your stated goals or your
implementation).

You also state, later, concerning the sample c implementation in the
standard:
"That algorithm is a slight elaboration on the basic linear congruential
algorithm, in that it uses a long (32-bit signed integer) for the seed, but
returns only a positive int (16-bit signed integer)."

That particular statement should be qualified (or perhaps less qualified).
The seed bit size is not explicit to that implementation, and in fact
compiling that algorithm in various environments will give different bit
sizes for the seed. You shouldn't stress the types at all (in fact srand
takes an int, and an int on the target you seem to be developing on --
VC++ -- is actually the same size as a long, both 32 bit -- it is only the
taken modulus which restricts the output range).

Also, you state:
"The ANSI rand function returns values between 0 and 32,767."

which is similarly incorrect, unless you qualify it by stressing that you
are referring to the sample implementation, as the range required by the ISO
/ IEC standard only defines RAND_MAX as the upper bound.

There are some more nitpicks I might state, but they are similar in scope
and reasoning (like your use of the unsigned long as 32 bit type without any
conditional compilation). However, a more blanket suggestion might be to
just take all the VC++ specific stuff out of your assumptions (and
#ifdef's!), as it is mostly unneeded and where you need a specific bit size,
either use some library like boost's or insert your own conditional
compilation to pick the appropriate type in a more general manner.

Finally, I just wanted to ask if you have considered using template
metaprogramming to ensure the unrolling of your statically-sized loops and
avoid the need for a counter and its manipulation / testing at runtime.
Although profiling and such should always be checked prior and during
optimisation, this is certainly code where one of the main goals is speed.

Just some comments. Again I thank you for your time and effort. 

-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
galathaea: prankster, fablist, magician, liar

Relevant Pages

  • Re: C++ more efficient than C?
    ... If you want to do language comparisons, ... complicated algorithm, though). ... int compare ... not been in C's standard library. ...
    (comp.lang.c)
  • Re: Creating an operating system
    ... > Do not mix compilation for the computer with source hiding. ... > A different story is a software patent: ... > an algorithm compared to outright copying of it. ... and you can imagine there is enought freedom to create new all the time. ...
    (comp.programming)
  • Re: Creating an operating system
    ... > Do not mix compilation for the computer with source hiding. ... > A different story is a software patent: ... > an algorithm compared to outright copying of it. ... and you can imagine there is enought freedom to create new all the time. ...
    (comp.os.linux.development.system)
  • Re: Non-restoring binary square root and convergence
    ... I took the algorithm from "Algorithms for Extracting Square Roots and Cube ... % sqrt 9 16 ... int main ...
    (comp.programming)
  • Re: Non-restoring binary square root and convergence
    ... I took the algorithm from "Algorithms for Extracting Square Roots and Cube ... % sqrt 9 16 ... int main ...
    (sci.math)
Loading