Darryl's Pixels

Pseudo Random Number Generation

In this post I’ll talk a bit about pseudo random number generation. This will be the first in an assortment of posts regarding monte carlo methods.

I’ll assume you have working knowledge of calculus and some probability and statistics.

The most essential aspect of any form of monte carlo method is the generation of random numbers. Uniformly distributed random numbers on the interval [0,1] are what we’d like to generate first, as they are also what is required for the other types of distributions.

Generating random numbers using a pseudo random number generator (PRNG) means that we generate a sequence of numbers, using some particular seed value (some arbitrary constant) that initializes the random number generation algorithm. We use the term pseudo, because the numbers generated are not truly random but generated deterministically and hence can be replicated if the same seed and the same constants in the function are used. This is ideal for us, so that we can replicate and debug our algorithms. We can think of these algorithms as generating a deterministic sequence which is based on a starting point.

For this sequence to be considered to be of good quality, it should have certain properties, such as lack of predictibility (i.e. if we generate x values, and we can guess the next, this means the predctibility is possible) and equidistribution. For example if the mean of a large sequence of uniformly distributed numbers in the range [0,1] is not 0.5, then it is likely that something is wrong with the PRNG, given that due to the Law of Large Numbers, we would expect the arithmetic mean of this sequence to be similar to the expected mean (the expected mean being 0.5). We won’t focus on hardcore evaluation PRNGs and leave that to other minds, some useful links are “How random is pseudorandom testing pseudorandom number generators and measuring randomness” and TestU01 tests. We’ll look at 2 PRNGs and do some simple tests to measure their quality.

Let’s look at a simple PRNG known as the Linear Congruential Generator (which I’ll now continue referring to as LCG).

The LCG is an easy-to-implement PRNG, the function definition being:

where:

The above constants are all integers. Careful selection of these values ensures that the sequence we get is of a high quality.

Here’s an R listing of what the code for this should look like:

lcgen <- function(x0=4, N, a=1229, c=1, m=2048)
{
  x = c()
  x[1] = x0
  for(n in 2:(N+1))
  {
    x[n] = (a * x[n-1] + c) %% m
  }
  return (x[2:(N+1)]/m)
}

N is the number of random numbers we want to generate. Let’s generate 1000 samples and plot a histogram to look at the distribution.

Hello embree

I’ve been slowly developing a raytracer which has been a lot of fun and a great learning experience both from a technical standpoint and the theoretical side of physically-based rendering.

I’m at a point now where I am importing meshes of a larger nature, and I was not content with my BVH implementation. As much as I would like to read the state of the art papers on BVH construction and traversal and implement them myself, I’ve decided to opt to use embree instead. I would rather focus on the light transport part and focus on getting prettier images and getting them to converge quicker from an algorithmic standpoint. As a friend of mine said, I have to pick my battles, and embree is going to do a lot of heavy lifting for me so that I can focus more on what I’d like to write.

Setting up embree with CMake is quite easy I’ve got the full source code of this post available here , and I won’t go into details into how to set it up - the CMakeLists.txt is quite self explanatory and I’ve added as much comments as I can.

As great and as fleshed out the samples are, there is a lot of boilerplate code, written in different header files. This put me off initially but with a bit of digging, and building the samples with a powerful IDE went long way in help way in helping me zip around the API and the headers.

I thought it would be interesting to write the simplest thing I can think of with embree, a hello world ray tracing example if you will, I’ll explain below what we’ll do.