Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Generating 64-bit values with a 32-bit Mersenne Twister

According to this Boost documentation page, the 64-bit variant of the Mersenne Twister is much slower than its 32-bit counterpart (which makes sense). As I understand, a lot of the features introduced in C++11, including random number generation, are basically Boost in the standard library. This leads me to believe that 32-bit MT performance in standard C++ is also better.

I'm writing a raytracer (for fun, mostly), and speed is one of my primary concerns. Essentially all the numerical values are represented as double precision floats. My question is, since the 32-bit MT is considerably faster, can I use it to generate doubles? What drawbacks (precision loss, performance, etc.) can I expect?

like image 645
More Axes Avatar asked Sep 14 '13 22:09

More Axes


People also ask

What is the maximum number that you can get from the Mersenne Twister PRNG?

It supports various periods from 2607 − 1 to 2216091 − 1.

What is the Mersenne Twister algorithm?

The Mersenne Twister is a strong pseudo-random number generator. In non-rigorous terms, a strong PRNG has a long period (how many values it generates before repeating itself) and a statistically uniform distribution of values (bits 0 and 1 are equally likely to appear regardless of previous values).

What is mt19937ar?

Here putted is a new standard code of MT19937, mt19937ar. c (ar for ARray) solving this shortcoming. This code includes another initialization admitting an array of arbitrary length as a seed. Please use init_genrand(seed) instead of previous initializing routines.

Is Mersenne Twister cryptographically secure?

Mersenne Twister is not cryptographically secure. (MT is based on a linear recursion. Any pseudorandom number sequence generated by a linear recursion is insecure, since from sufficiently long subsequence of the outputs, one can predict the rest of the outputs.)


1 Answers

For this I am adding one assumption that you did not mention: I am assuming you are doing one random draw per double. Obviously you can get twice the randomness by doing two draws.

The first question is really "does 32-bits of pseudorandomness have enough randomness for my ray tracer." My guess is yes. Most raytracers are only shooting out a few million rays, so you wont notice that there's only 4 billion bits of pseudorandomness.

Second question is "can I distribute the pseudorandomness across the domain of double values I care about." Again, my guess is yes. If you are shooting rays in a 90 degree field, and there are 4 billion possible results from one pseudorandom draw. For perspective, a sniper looking through a high power scope sees millions of times less angular precision than the average difference between those pseudorandom vectors.

All that being said, profile your code. I'd give a 99.9998% chance that your raytracing code itself takes much longer than the pseudorandom generation unless your scenes all consist of single non-reflective spheres

like image 86
Cort Ammon Avatar answered Oct 15 '22 21:10

Cort Ammon