473,320 Members | 1,865 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Mersenne Twister -- A Revised C++ Implementation

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
Jul 22 '05 #1
31 4380
On Mon, 05 Jan 2004 13:31:04 GMT, Scott Robert Ladd
<sc***@coyotegulch.com> 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
Jul 22 '05 #2
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
Jul 22 '05 #3

"Scott Robert Ladd" <sc***@coyotegulch.com> wrote in message
news:pa****************************@coyotegulch.co 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
Jul 22 '05 #4

"Carsten Hansen" <ha******@worldnet.att.net> 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).

Jul 22 '05 #5

"Ron Natalie" <ro*@sensor.com> wrote in message
news:3f***********************@news.newshosting.co m...

"Carsten Hansen" <ha******@worldnet.att.net> 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


Jul 22 '05 #6
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
Jul 22 '05 #7
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
Jul 22 '05 #8
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
Jul 22 '05 #9

"Scott Robert Ladd" <sc********@coyotegulch.com> wrote in message
news:pa**************************@coyotegulch.com. ..
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

Jul 22 '05 #10
On Mon, 05 Jan 2004 20:44:27 +0000, Carsten Hansen wrote:
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.
Indeed, a and m can take on any value, but only very specific values
produce a useful random number generator. I could have made that clearer
in the article, and will likely make a small revision tonight.
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.
And a fine generator it is; I've never made any claim that the Mersenne
Twister is "the best", and, in fact, I provide links to sites that
compare many algorithms. The Mersenne Twister has many adherents and
supporters, most of whom have far more credentials than you or I. The
algorithm performs excellently on the most demanding statistical tests.

You are welcome, of course, to use any algorithm you wish. Have fun.
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."
I has not seen this quote, though I certainly won't deny its existence. It
may or may not be valid; I have respect for Mr. Marsaglia, but he is only
one voice of many. And in my opinion, the Mersenne Twister does *not*
require "an elaborate C program."
The Mersenne Twister claim to fame is mostly because of its cute name.
Ah -- so in your opinion, good algorithms must have dull and academic
sounding names?
Your code show that you don't understand random number generation.
Hmmm... and your comments here clearly show that you can't read, or that
you lead an active fantasy life. As in...
In get_rand_range you basically map [0, 4294963695] onto the range. That
cannot be done uniformly. That is part of the C FAQ.


Where do I say that the results are uniform? Since I never claim that the
result is uniform, you accuse me of a non-existent error.

I must point out that the given technique is a common one used for
obtaining a "random" value within a given range; you'll find it in many
text books, papers, and articles. It is imperfect; if you have divined a
superior technique, please illuminate us.

--
Scott Robert Ladd
Coyote Gulch Productions (http://www.coyotegulch.com)
Software Invention for High-Performance Computing
Jul 22 '05 #11
> 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.


I must have overlooked it. Please point out where he claims uniformity.

Thank you

Stephen Howe
Jul 22 '05 #12

"Scott Robert Ladd" <sc********@coyotegulch.com> wrote in message
news:pa***************************@coyotegulch.com ...
On Mon, 05 Jan 2004 20:44:27 +0000, Carsten Hansen wrote:
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.


Indeed, a and m can take on any value, but only very specific values
produce a useful random number generator. I could have made that clearer
in the article, and will likely make a small revision tonight.
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.


And a fine generator it is; I've never made any claim that the Mersenne
Twister is "the best", and, in fact, I provide links to sites that
compare many algorithms. The Mersenne Twister has many adherents and
supporters, most of whom have far more credentials than you or I. The
algorithm performs excellently on the most demanding statistical tests.

You are welcome, of course, to use any algorithm you wish. Have fun.
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."


I has not seen this quote, though I certainly won't deny its existence. It
may or may not be valid; I have respect for Mr. Marsaglia, but he is only
one voice of many. And in my opinion, the Mersenne Twister does *not*
require "an elaborate C program."


You can do your own search on Google.
Of course, insinuating that I made up the quote, shows something about your
ethics.
The Mersenne Twister claim to fame is mostly because of its cute name.


Ah -- so in your opinion, good algorithms must have dull and academic
sounding names?


You logic is flawed. I expressed no such opinion.
Your code show that you don't understand random number generation.


Hmmm... and your comments here clearly show that you can't read, or that
you lead an active fantasy life. As in...
In get_rand_range you basically map [0, 4294963695] onto the range. That
cannot be done uniformly. That is part of the C FAQ.


Where do I say that the results are uniform? Since I never claim that the
result is uniform, you accuse me of a non-existent error.

I must point out that the given technique is a common one used for
obtaining a "random" value within a given range; you'll find it in many
text books, papers, and articles. It is imperfect; if you have divined a
superior technique, please illuminate us.


A random number generator that does not generate uniformly distributed
numbers is of very questionable use. If that is what you are looking for,
you have definitely found it.
Koenig and Moo's "Accelerated C++" contains a better way of generating
numbers from a range. That is an introductory text. Maybe it is too advanced
for you.

Carsten Hansen
Jul 22 '05 #13
"Scott Robert Ladd" 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.

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
Jul 22 '05 #14
On Tue, 06 Jan 2004 01:16:16 +0000, galathaea wrote:
//--------------------------------------------------------------------------
// 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)

displays the common error of nonuniform range mapping. This discrepancy
should probably be corrected (either your stated goals or your
implementation).
I'm aware that this one routine does not fall within the definition of
"uniform"; however, given the usual range of numbers I need, say [0..100),
the statistical anomaly is very small. The modulus operation is quite
common in this context, and I never really considered doing anything more
sophisticated, given the limited impact on my applications.

Be that as it may, I've already modified the function (internally) to use
something a bit more sophisticated that does maintain uniformity. I'll
post a revised version of the code in a few days.
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).
You are very correct; in fact, I may remove the entire discussion of the
"suggested" C implementation, given that almost no current compilers use
it.
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.
I should have stated that 32,767 is an *example* of a maximum range --
although it is the most common value for RAND_MAX on small systems (in my
experience).
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.
I much prefer C99 or Fortran 95, where I can portably and explicitly
request a specific bit size without the need for little tricks. For
example, when working in C99, I use int32_t from stdint.h. I note that the
reference implementation uses unsigned long, as do many published
algorithms -- but that doesn't mean I shouldn't be smarter ;)

The VC++-specific #ifdefs work around a bug in older Visual C++ compilers
that do not support the assignment of values to member constants within
the class definitions. I don't see any point in removing this, since many
people still use older tools. Perhaps I should make it non-compiler
specific with a compile-time definition; frankly, I do so little coding on
Windows anymore, I'd forgotten it was there.
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.
I've done my share of template metaprogramming (DSP, linear algebra), and
find that its efficacies are often offset by the obscurity of the syntax.
In the case of the Mersenne Twister, some of my programs use it to
generate trillions of numbers -- and profiling shows that the Twister is a
very minor contributor to execution time.

I'll consider the issue, though.
Just some comments. Again I thank you for your time and effort.


I appreciate the thoughtful comments.

--
Scott Robert Ladd
Coyote Gulch Productions (http://www.coyotegulch.com)
Software Invention for High-Performance Computing
Jul 22 '05 #15
Scott Robert Ladd writes:
You are very correct; in fact, I may remove the entire discussion of the
"suggested" C implementation, given that almost no current compilers use
it.
I much prefer that you leave the code there and correct the weasel words.
It's code that a lot of people would like to see.
The VC++-specific #ifdefs work around a bug in older Visual C++ compilers
that do not support the assignment of values to member constants within
the class definitions. I don't see any point in removing this, since many
people still use older tools. Perhaps I should make it non-compiler
specific with a compile-time definition; frankly, I do so little coding on
Windows anymore, I'd forgotten it was there.


I would have really appreciated a comment as to what the #ifdef was all
about. BFTSLK loses more and more meaning as time goes on.
----
Thanks for posting this. Unfortunately, the response has been such as to
inhibit any similar posts for the next few months.


Jul 22 '05 #16

"Carsten Hansen" <ha******@worldnet.att.net> wrote in message
news:iC**********************@bgtnsc05-news.ops.worldnet.att.net...
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."

I has not seen this quote, though I certainly won't deny its existence. It may or may not be valid; I have respect for Mr. Marsaglia, but he is only one voice of many. And in my opinion, the Mersenne Twister does *not*
require "an elaborate C program."

You can do your own search on Google.
Of course, insinuating that I made up the quote, shows something about

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


Ah -- so in your opinion, good algorithms must have dull and academic
sounding names?


You logic is flawed. I expressed no such opinion.


His logic was flawed, as was yours when you said he insinuated you made up
the quote. Isn't it time you stopped bickering? Your arguments are
becoming weaker and more desperate - the sign that it's over.
Jul 22 '05 #17

"Carsten Hansen" <ha******@worldnet.att.net> wrote in message
news:iC**********************@bgtnsc05-news.ops.worldnet.att.net...
[SNIP]> >
A random number generator that does not generate uniformly distributed
numbers is of very questionable use. If that is what you are looking for,
you have definitely found it.
Koenig and Moo's "Accelerated C++" contains a better way of generating
numbers from a range. That is an introductory text. Maybe it is too advanced for you.


Sit back and relax. There is no need for both of you to get personal here.
If you want to be knitpicking then the statement that a RNG that does not
generate uniformly distributed numbers is of questionable use, is simply not
correct in that form. Such a RNG is certainly useless as a basis to obtain
arbitrarily specified distributions but especially in the field of Monte
Carlo simulations RNGs producing non-uniform distributions are wanted.
Although of course one must be aware which distribution is obtained and
control over this distribution is mandatory.

Cheers
Chris

Jul 22 '05 #18
On Tue, 06 Jan 2004 10:47:02 -0500, jeffc wrote:
His logic was flawed, as was yours when you said he insinuated you made up
the quote. Isn't it time you stopped bickering? Your arguments are
becoming weaker and more desperate - the sign that it's over.


I never insinuated that he made up the quote! I simply said I'd never seen
the quote -- two totally different assertions.

--
Scott Robert Ladd
Coyote Gulch Productions (http://www.coyotegulch.com)
Software Invention for High-Performance Computing
Jul 22 '05 #19

"Scott Robert Ladd" <sc********@coyotegulch.com> wrote in message
news:pa****************************@coyotegulch.co m...
On Tue, 06 Jan 2004 10:47:02 -0500, jeffc wrote:
His logic was flawed, as was yours when you said he insinuated you made up the quote. Isn't it time you stopped bickering? Your arguments are
becoming weaker and more desperate - the sign that it's over.


I never insinuated that he made up the quote! I simply said I'd never seen
the quote -- two totally different assertions.


That's what I just said.
Jul 22 '05 #20
> A random number generator that does not generate uniformly distributed
numbers is of very questionable use.


Not at all. I could have a random number generator returning doubles that
generates a random number between 0 and 1 with a Normal distribution, mean
0.5, standard deviation 1. I can think of a use for that. I can think of
other non-uniform random number generator distributions, all statistical
that are of use.

Your mathematical credentials are suspect. You seem to be way more
incompetent than the OP.

Stephen Howe
Jul 22 '05 #21

"Stephen Howe" <NO**********@dial.pipex.com> wrote in message
news:3f***********************@reading.news.pipex. net...
A random number generator that does not generate uniformly distributed
numbers is of very questionable use.


Not at all. I could have a random number generator returning doubles that
generates a random number between 0 and 1 with a Normal distribution, mean
0.5, standard deviation 1. I can think of a use for that. I can think of
other non-uniform random number generator distributions, all statistical
that are of use.

Your mathematical credentials are suspect. You seem to be way more
incompetent than the OP.

Stephen Howe


A normal distribution has infinite range. So, generating random numbers
between 0 and 1 with a Normal distribution doesn't make sense.
Yes, you can have a truncated Normal distribution, but that is not what you
are writing.

I'm well aware that there are non-uniform random number distributions. In
the fall I corrected two errors in Knuth's Vol. 2 about non-uniform RNG. I
have the check to prove it.
I commented about the code which is intended to generate a uniform
distribution. I doesn't as others have pointed out.
As for my credentials, I have a Ph.D. in Mathematics (Penn State '89).

Carsten Hansen
Jul 22 '05 #22
> A normal distribution has infinite range. So, generating random numbers
between 0 and 1 with a Normal distribution doesn't make sense.


It does if you are returning cumulative probabilites. So

_ x
|
p(x) = 1.0 / (sqrt (2.0 * pi))I exp(- (x * x) / 2.0)
_I
-Inf

That will lie between 0.0 and 1.0.

Stephen Howe
Jul 22 '05 #23

"Stephen Howe" <NO**********@dial.pipex.com> wrote in message
news:3f***********************@news.dial.pipex.com ...
A normal distribution has infinite range. So, generating random numbers
between 0 and 1 with a Normal distribution doesn't make sense.


It does if you are returning cumulative probabilites. So

_ x
|
p(x) = 1.0 / (sqrt (2.0 * pi))I exp(- (x * x) / 2.0)
_I
-Inf

That will lie between 0.0 and 1.0.

Stephen Howe


That is not a distribution. That is a probability. You don't generate that.
You calculate that.
You talked about generating random numbers between 0 and 1 with a Normal
distribution.
Now you are changing it to cumulative probabilities. Something very
different.
But nice try. Maybe you will get partial credit.

Carsten Hansen
Jul 22 '05 #24

"Carsten Hansen" <ha******@worldnet.att.net> wrote in message
news:4G*******************@bgtnsc05-news.ops.worldnet.att.net...

"Stephen Howe" <NO**********@dial.pipex.com> wrote in message
news:3f***********************@news.dial.pipex.com ...
A normal distribution has infinite range. So, generating random numbers between 0 and 1 with a Normal distribution doesn't make sense.
It does if you are returning cumulative probabilites. So

_ x
|
p(x) = 1.0 / (sqrt (2.0 * pi))I exp(- (x * x) / 2.0)
_I
-Inf

That will lie between 0.0 and 1.0.

Stephen Howe


That is not a distribution. That is a probability. You don't generate

that. You calculate that.
IMHO you also "calculate" numbers following a distribution, don´t you? I
mean we´re talking about distributions given in analytical form and not some
stochastic processes.
You talked about generating random numbers between 0 and 1 with a Normal
distribution.
Now you are changing it to cumulative probabilities. Something very
different.
To be exact he is talking about cumulative distributions (CDF) and not
cumulative probabilities, though in principle you are right as the
discussion is about PDF and not CDF.
But nice try. Maybe you will get partial credit.


Thanks :-) But don´t you think that this discussion will lead to nowhere and
that comp.lang.c++ might not be the place to discuss statistical issues?

Regards
Chris
Jul 22 '05 #25

"Chris Theis" <Ch*************@nospam.cern.ch> wrote in message
news:vK*********************@news.chello.at...

"Carsten Hansen" <ha******@worldnet.att.net> wrote in message
news:4G*******************@bgtnsc05-news.ops.worldnet.att.net...

"Stephen Howe" <NO**********@dial.pipex.com> wrote in message
news:3f***********************@news.dial.pipex.com ...
> A normal distribution has infinite range. So, generating random numbers > between 0 and 1 with a Normal distribution doesn't make sense.

It does if you are returning cumulative probabilites. So

_ x
|
p(x) = 1.0 / (sqrt (2.0 * pi))I exp(- (x * x) / 2.0)
_I
-Inf

That will lie between 0.0 and 1.0.

Stephen Howe
That is not a distribution. That is a probability. You don't generate

that.
You calculate that.


IMHO you also "calculate" numbers following a distribution, don´t you? I
mean we´re talking about distributions given in analytical form and not

some stochastic processes.
You talked about generating random numbers between 0 and 1 with a Normal
distribution.
Now you are changing it to cumulative probabilities. Something very
different.

To be exact he is talking about cumulative distributions (CDF) and not
cumulative probabilities, though in principle you are right as the
discussion is about PDF and not CDF.
But nice try. Maybe you will get partial credit.
Thanks :-) But don´t you think that this discussion will lead to nowhere

and that comp.lang.c++ might not be the place to discuss statistical issues?

Regards
Chris

Generating random numbers with a given distribution has a well-established
meaning. Generating random numbers with a Normal distribution between 0 and
1 doesn't makes sense. I'm not supposed to correct that?

Carsten Hansen
Jul 22 '05 #26

"Carsten Hansen" <ha******@worldnet.att.net> wrote in message
news:mPRKb.2745$Ub6.81689@bgtnsc04-
[SNIP]

Generating random numbers with a given distribution has a well-established
meaning. Generating random numbers with a Normal distribution between 0 and 1 doesn't makes sense. I'm not supposed to correct that?

Carsten Hansen


Hi Carsten,

relax :-) Of course you should correct wrong statements, this is the way
that people reading these postings are supposed to obtain wider & better
knowledge. However, I wouldn´t be so quick to say that generating a normal
distribution between 0 & 1 (Stephen proposed a mean value of 0.5) doesn´t
make sense. If you want to study for example a special case of a biased
Wiener-Levy process you might resort to such random numbers (whether this
study makes any sense or not is a different thing!).

Chris
Jul 22 '05 #27

"Chris Theis" <Ch*************@nospam.cern.ch> wrote in message
news:jj***************@news.chello.at...

"Carsten Hansen" <ha******@worldnet.att.net> wrote in message
news:mPRKb.2745$Ub6.81689@bgtnsc04-
[SNIP]

Generating random numbers with a given distribution has a well-established meaning. Generating random numbers with a Normal distribution between 0

and
1 doesn't makes sense. I'm not supposed to correct that?

Carsten Hansen


Hi Carsten,

relax :-) Of course you should correct wrong statements, this is the way
that people reading these postings are supposed to obtain wider & better
knowledge. However, I wouldn´t be so quick to say that generating a normal
distribution between 0 & 1 (Stephen proposed a mean value of 0.5) doesn´t
make sense. If you want to study for example a special case of a biased
Wiener-Levy process you might resort to such random numbers (whether this
study makes any sense or not is a different thing!).

Chris


Generating random numbers with a given distribution has a well-established
meaning.
Using that well-established meaning and given that a Normal distribution has
an infinite range, it does not make sense to talk about generating random
numbers with a Normal distribution between 0 and 1.
You can calculate other things. But if you use a well-established phrase,
you better qualify it.

That is all I'm saying.

Carsten Hansen
Jul 22 '05 #28
Carsten Hansen writes:
Generating random numbers with a given distribution has a well-established
meaning.
Using that well-established meaning and given that a Normal distribution has an infinite range, it does not make sense to talk about generating random
numbers with a Normal distribution between 0 and 1.
You can calculate other things. But if you use a well-established phrase,
you better qualify it.


I read Ladd's whole post as "good enough for government work". If I had
seen a similar thing in some high-falutin' mathematics journal, I would have
applied different standards. After all, the computers I have seen have
been unable to express infinity in a reasonable fashion, anyway, one of the
popular OSes limits RAM to only 2^29 bytes. Computers of the kind being
discussed here (that is, a machine, not a human) deal with approximations
for the real numbers encountered in the field of mathematics. C++, as used
here, does not deal with symbolic mathematics.

I saw, and see, no reason for further qualification as to the use of the
phrase, considering the context in which it was provided.

It is pretty clear that you are the kind of person that has to have the last
word. So post it, I don't expect to express any answer.
Jul 22 '05 #29

"kevin collins" <ke********@hotmail.com> wrote in message
news:pXTKb.766883$Tr4.2203330@attbi_s03...
Carsten Hansen writes:
Generating random numbers with a given distribution has a well-established meaning.
Using that well-established meaning and given that a Normal distribution has
an infinite range, it does not make sense to talk about generating random numbers with a Normal distribution between 0 and 1.
You can calculate other things. But if you use a well-established phrase, you better qualify it.


I read Ladd's whole post as "good enough for government work". If I had
seen a similar thing in some high-falutin' mathematics journal, I would

have applied different standards. After all, the computers I have seen have
been unable to express infinity in a reasonable fashion, anyway, one of the popular OSes limits RAM to only 2^29 bytes. Computers of the kind being
discussed here (that is, a machine, not a human) deal with approximations
for the real numbers encountered in the field of mathematics. C++, as used here, does not deal with symbolic mathematics.

I saw, and see, no reason for further qualification as to the use of the
phrase, considering the context in which it was provided.

It is pretty clear that you are the kind of person that has to have the last word. So post it, I don't expect to express any answer.


This has nothing to do with how big a number you can represent on a
computer. When you have an infinite range and you claim it falls between 0
and 1 you are talking nonsense.

Carsten Hansen
Jul 22 '05 #30

"Carsten Hansen" <ha******@worldnet.att.net> wrote in message
news:_1*******************@bgtnsc05-news.ops.worldnet.att.net...

"kevin collins" <ke********@hotmail.com> wrote in message
news:pXTKb.766883$Tr4.2203330@attbi_s03...
Carsten Hansen writes:
Generating random numbers with a given distribution has a well-established meaning.
Using that well-established meaning and given that a Normal
distribution
has
an infinite range, it does not make sense to talk about generating random numbers with a Normal distribution between 0 and 1.
You can calculate other things. But if you use a well-established phrase, you better qualify it.


I read Ladd's whole post as "good enough for government work". If I had
seen a similar thing in some high-falutin' mathematics journal, I would

have
applied different standards. After all, the computers I have seen have
been unable to express infinity in a reasonable fashion, anyway, one of

the
popular OSes limits RAM to only 2^29 bytes. Computers of the kind being
discussed here (that is, a machine, not a human) deal with

approximations for the real numbers encountered in the field of mathematics. C++, as

used
here, does not deal with symbolic mathematics.

I saw, and see, no reason for further qualification as to the use of the phrase, considering the context in which it was provided.

It is pretty clear that you are the kind of person that has to have the

last
word. So post it, I don't expect to express any answer.


This has nothing to do with how big a number you can represent on a
computer. When you have an infinite range and you claim it falls between 0
and 1 you are talking nonsense.


Okay if you want to stick to knit-picking then so be it. Stephen never
claimed that the infinite range falls between 0 and 1. He was only talking
about a normal distribution with mean 0.5 between the limits of 0 and 1. It
is of course correct that the Stiltjes-integral applied in mathematical
statistics is defined from -\inf to \inf. However, if you want to calculate
anything reasonable you will have to specify limits as infinity is a
mathematical construct that doesn´t play very well with practical
applications (to see this we only have to resort to Quantum Mechanics, which
is OT here and I don´t wanna get into that now). Specifying limits does
bring us back to numerical accuracy which depends on your machine and
therefore any applied limit is valid (see my previous post about the
Wiener-Levy process).

Regards
Chris

Jul 22 '05 #31

"Chris Theis" <Ch*************@nospam.cern.ch> wrote in message
news:%k*****************@news.chello.at...

"Carsten Hansen" <ha******@worldnet.att.net> wrote in message
news:_1*******************@bgtnsc05-news.ops.worldnet.att.net...

"kevin collins" <ke********@hotmail.com> wrote in message
news:pXTKb.766883$Tr4.2203330@attbi_s03...
Carsten Hansen writes:

> Generating random numbers with a given distribution has a well-established
> meaning.
> Using that well-established meaning and given that a Normal distribution has
> an infinite range, it does not make sense to talk about generating

random
> numbers with a Normal distribution between 0 and 1.
> You can calculate other things. But if you use a well-established

phrase,
> you better qualify it.

I read Ladd's whole post as "good enough for government work". If I had seen a similar thing in some high-falutin' mathematics journal, I would
have
applied different standards. After all, the computers I have seen
have been unable to express infinity in a reasonable fashion, anyway, one of
the
popular OSes limits RAM to only 2^29 bytes. Computers of the kind
being discussed here (that is, a machine, not a human) deal with

approximations for the real numbers encountered in the field of mathematics. C++, as

used
here, does not deal with symbolic mathematics.

I saw, and see, no reason for further qualification as to the use of the phrase, considering the context in which it was provided.

It is pretty clear that you are the kind of person that has to have

the last
word. So post it, I don't expect to express any answer.


This has nothing to do with how big a number you can represent on a
computer. When you have an infinite range and you claim it falls between 0 and 1 you are talking nonsense.


Okay if you want to stick to knit-picking then so be it. Stephen never
claimed that the infinite range falls between 0 and 1. He was only talking
about a normal distribution with mean 0.5 between the limits of 0 and 1.

It is of course correct that the Stiltjes-integral applied in mathematical
statistics is defined from -\inf to \inf. However, if you want to calculate anything reasonable you will have to specify limits as infinity is a
mathematical construct that doesn´t play very well with practical
applications (to see this we only have to resort to Quantum Mechanics, which is OT here and I don´t wanna get into that now). Specifying limits does
bring us back to numerical accuracy which depends on your machine and
therefore any applied limit is valid (see my previous post about the
Wiener-Levy process).

Regards
Chris


You can have a truncated normal distribution. If you do, you specify the
mean, the standard deviation and the limits for the truncation.
That is fine. But that is not what Stephen wrote. He is calculating
something else (a cumulative probability).
Using the same name, generating random numbers with a Normal distribution,
for two different things is confusing and misleading.
There are no numerical accuracy issues here.

Carsten Hansen

Jul 22 '05 #32

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

31
by: Raymond Hettinger | last post by:
Based on your extensive feedback, PEP 322 has been completely revised. The response was strongly positive, but almost everyone preferred having a function instead of multiple object methods. The...
4
by: Shufen | last post by:
Hi, I'm a newbie that just started to learn python, html and etc. I have some questions to ask and hope that someone can help me on. I'm trying to code a python script (with HTML) to get...
7
by: Jan Roland Eriksson | last post by:
I'm posting a revised version of the meta FAQ for this NG. Beware that there are a few links in there that does not have a resource available for them yet but, over and all, this following document...
2
by: Martin Ho | last post by:
Hi Everyone, I have this code of Mersenne twister, which produces the random numbers, one of the fastest codes as far as I know to produce random numbers. Anyways, it's writen in c# and I need to...
26
by: CBFalconer | last post by:
I have modified my ggets utility, to simplify the code and reduce the requirements on the standard library. The external action is totally unchanged, so there is no real need for anyone to...
0
by: Kurt B. Kaiser | last post by:
Patch / Bug Summary ___________________ Patches : 420 open ( +4) / 3410 closed ( +2) / 3830 total ( +6) Bugs : 915 open (+17) / 6186 closed ( +6) / 7101 total (+23) RFE : 235 open...
11
by: Simon | last post by:
I have a quick question on the Mersenne Twister (hereinafter MT) I'm using the standard C code downloaded from the MT website (http://tinyurl.com/6d8t3). It's being used for a game to generate...
0
by: bearophileHUGS | last post by:
This may be interesting for Python developers of the random module, "SIMD-oriented Fast Mersenne Twister (SFMT): twice faster than Mersenne Twister": ...
1
by: mjm2114 | last post by:
Hi there, I have a question on a naive implementation of a parallel MT that I've done using the fortran version of MT19937ar.f posted in Prof. Matsumoto's website....
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.