For a Path Tracing application I need to generate good quality pseudo random numbers in the closed range [0~1]. Because I'm doing this on the GPU (HLSL Shader Model 5) I can only use 32bit variables. My initial approach is the following set-up:

  1. Ever Frame the pixel shader receive a good pseudo random number ([0~1]) from the CPU using C++'s std::mt19937 generator and std::uniform_real_distribution.

  2. Because for each pixel this number is the same I also use the screen coordinates u and v of each pixel these are also in [0~1].

  3. I then call the Multiply With Carry method like below.


// seed is the value given from the cpu
float3 random = Random(seed + u, seed + v)l

// Multiply With Carry, returns 3 floating point values {x, y, z}
// x: the random number
// y, z: new seeds for the next time we need a random number
float3 Random(float seed_a, float seed_b)
    uint m_z = asuint(seed_a);
    uint m_w = asuint(seed_b);

    m_z = 36969 * (m_z & 65535) + (m_z >> 16);
    m_w = 18000 * (m_w & 65535) + (m_w >> 16);  

    float r = ((m_z << 16) + m_w) / (float)0xFFFFFFFF;
    return float3(r, asfloat(m_z), asfloat(m_w));

This produces the following output. (The left part is the random number obtained from the Random method for this pixel, the right part is the visualization of u and v as Red and Green.


Not so random

As you can see there is clearly a pattern, so the randomness is not good at all. Which hurts the performance of my algorithm tremendously. This is probably due to the fact that the original Multiply with Carry method assumes m_z and m_w are 64 bit integers, not 32 bit ones.

What I want

What I'm looking for is a way to fix my implementation of the Multiply with Carry method so that it produces reasonably good pseudo random numbers and works in the closed [0~1] interval instead of the open [0~1] interval. However since it is quite possible that this method can only work right using 64 bits integers I'm would also be really glad if someone can suggest another pseudo random number generator algorithm that:

  • Works with 32 bit numbers
  • Produces uniformly distributed results in the closed [0~1] interval
  • Does not require too much state information, (this is why I chose MwC since it only needs to store 2 variables) since that is hard on the GPU. 16 32 bit variables would be the maximum I think since I can store that in 4x4 matrix which is easy to pass around.
  • 4
    $\begingroup$ It's badly wrong to re-seed a PRNG each time you need a random number -- that means that the randomness you end up with does not really come from the PRNG itself, but just from how random you can make each new seed (which, in this case, is "not very"). With SIMD parallelism you'll probably want to seed a PRNG for each processing unit once and for all, and then keep carrying that seed forwards through the entire computation. (But I don't know how easy it is to express this if you otherwise let the compiler parallelize your loops for you). $\endgroup$ Mar 22, 2013 at 10:35
  • $\begingroup$ Unfortunately I cant share information between pixels using a shader so I need to seed each pixel individually. Shaders also do not retain information between frames so that makes everything a lot harder. Still I do believe that the performance I'm getting now is really abysmal. Note that for this example I only take one random number from the PRNG but usually I take hundreds per pixel. $\endgroup$
    – Roy T.
    Mar 22, 2013 at 10:44
  • $\begingroup$ So the code you're showing is not what actually runs? Your comment says "new seeds for the next time we need a random number". If you're using "hundreds" of random numbers for each seed, you should have plenty of time to run the initial seed through, say, one of the integer hashes from burtleburtle.net, which ought to get rid of the most visually obvious patterns in the first outputs. $\endgroup$ Mar 22, 2013 at 10:51
  • $\begingroup$ No wait, that is how MwC works, the two seeds are its state. I mean I only seed them using the number from the CPU and the U and V variables once each frame. $\endgroup$
    – Roy T.
    Mar 22, 2013 at 11:00
  • 1
    $\begingroup$ You might be interested in this site proposal $\endgroup$
    – Daniel
    Nov 18, 2013 at 18:49

2 Answers 2


I queried fellow students and they brought my attention to this paper: https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch37.html

Since the paper is quite long and might not be online forever below is the general idea:

Linear Congruent Generators are ideal for use on the GPU because they are simple and do not require much state (only the previously generated number). but they are not 'random enough' for, for example, Monte Carlo based simulation. A generator like a Mersenne Twister would be better but requires way too much state to be stored.

The solution proposed by the paper is combining several LCGs using a combined Tausworthe Generator (as used by the Mersenne Twister) this guarantees a much better randomness without having to store as much state as the Mersenne Twister. The final algorithm looks like this:

struct RandomResult
    uint4 state;
    float value;

uint TausStep(uint z, int S1, int S2, int S3, uint M)
    uint b = (((z << S1) ^ z) >> S2);
    return (((z & M) << S3) ^ b);    

uint LCGStep(uint z, uint A, uint C)
    return (A * z + C);    

RandomResult Random(uint4 state)
    state.x = TausStep(state.x, 13, 19, 12, 4294967294);
    state.y = TausStep(state.y, 2, 25, 4, 4294967288);
    state.z = TausStep(state.z, 3, 11, 17, 4294967280);
    state.w = LCGStep(state.w, 1664525, 1013904223);

    RandomResult result;
    result.state = state;
    result.value = 2.3283064365387e-10 * (state.x ^ state.y ^ state.z ^ state.w);

    return result;

Note that the initial seed values for state should be larger than 128! (For background information reed the paper) and that you should fill the seed with 4 good random numbers from the CPU + four values unique for that pixel to get a nice result.

  • $\begingroup$ Your answer is great! In what range will output numbers be? And how can I store state so it will be shared among processes on GPU? $\endgroup$
    – kelin
    Jun 9, 2016 at 10:03
  • $\begingroup$ @kelin the numbers are in [0..1]. Not sure how to share state, but why would you want to? Making it different makes it more random :) $\endgroup$
    – Roy T.
    Jun 9, 2016 at 10:12
  • $\begingroup$ Actually, no. Here is a test texture generated with simple algorithm intended to show how state-based algorithms will behave: i.imgur.com/RtekQSJ.png It draws first pixel with 0 intensity first then toggles to 1 and so on. You can see black lines on the picture where I suppose GPU started a new thread for each pixel. Implemented on OpenGL ES 2.0, global variable was used to store the state. $\endgroup$
    – kelin
    Jun 15, 2016 at 12:47
  • $\begingroup$ That kinda was what I had first but this algorithm above completely fixed it for me. The randomness I got here was even good enough for a nice raytracer. Are you sure you haven't made an implementation error? Maybe you did new Random() a couple of times instead of using a sole one. or maybe OpenGL does something different. Its probably best to ask your own separate question where you show us your code that you have now. $\endgroup$
    – Roy T.
    Jun 15, 2016 at 15:19

There's some Perlin noise code on the following site that produces a number between -1 and +1 that I have used in the past. I am sure it could be changed to produce 0 to 1. http://www.gamedev.net/page/resources/_/technical/game-programming/simple-clouds-part-1-r2085

  • $\begingroup$ Hey MistyManor, I tried those links, and they indeed give me nice noisy image but it has a really low period which in the end was insufficient for the Monte Carlo simulation which is why I kept searching for something better. I answered my own question now after some searching, but I wish I could accept your answer as well since it is certainly not wrong and will be sufficient for most uses. $\endgroup$
    – Roy T.
    Mar 24, 2013 at 21:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .