Saturday, December 22, 2018

This is the first of a 3 part review of the "PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation" paper by Melissa O'Neill. I go over the major parts of the paper and try and recreate the core results.
 
Random numbers are used throughout computer science but what is a random number? This is hard to define but we know about randomness in the real world so we desire a system that produces results that match our expectations of those systems. The problem is that computers are deterministic which means they are very poor at doing random things. There are two general ways of generating random numbers on computers: use external "true" random sources or use pseudo-random numbers.

An external source of entropy allows you to take readings from a random system that produces results in an unpredictable manner but does so in a way that when measured you are equally likely to get one of a range (two for binary) of results. There have been a number of systems used for such devices with a lava lamp being the most interesting. Random.org uses weather as their source of random numbers. The downside to this is that readings from natural sources of randomness can only be taken at a slow rate which can be problematic when you need a lot of random numbers and need them quickly as is the case with games. Another issue is that in order to repeat a sequence of random numbers, as you would want to do for testing purposes, you need to save all the bits that you generate.

A pseudo-random system is a deterministic system that produces results that resemble true randomness but can be recreated if the state of the system is determined. This also means that the same starting value will produce same sequence of numbers so testing can be done by using the same seed value. There are a number of different algorithms that can be used to generate random numbers with the methods available covering a variety of needs.  Not all generators are good! So how can we tell what generators are good?

Randograms are an informal way of looking at random number generators. They are generated by creating a 256x256 grid and then taking 32768 pairs of numbers,  plotting them on the grid. The more times a grid is hit with a number, the darker that representation becomes. Here is some Kotlin code that demonstrates how to generate a randogram.

fun generate() {
for (cntr in 0..32767) {
val x = rng.nextUByte()
val y = rng.nextUByte()
++grid[x][y]
}
}

fun drawToCanvas(canvas:Canvas, scale:Double) {
val gc = canvas.graphicsContext2D
for (cntrX in 0..255)
for (cntrY in 0..255) {
gc.fill = Color.gray(1.0 / (grid[cntrX][cntrY].toDouble() + 1.0))
gc.fillRect(cntrX.toDouble()*scale, cntrY.toDouble()*scale, scale, scale)
}
}

The image below are some images that I generated.



With simple random number generators, it is easy to see that they are not random. Better generators, such as Java's random number generator, are not a clear. Java's random number generator is actually not that great but simply looking at the randograms would not reaveal this so better ways of testing are required.

No comments:

Post a Comment