Essential Math Weblog Thoughts on math for games

4/8/2013

New Thoughts on Random Numbers, Part One

Filed under: Erratical,Mathematical — Jim @ 9:00 am

I recently (December 2012) switched jobs from being an Engine Programmer at Insomniac Games, to being a Software Engineer at Google. At Google, I’m now working on Skia, which is the 2D graphics library that underlies Chrome, Firefox and parts of Android. One of the first things that came to my attention when I arrived was the pseudorandom number generator (PRNG) used to generate test cases for regressions — namely, that there was some concern that it wasn’t very random. In particular, the least significant bit flips back and forth, and possibly other lower-order bits weren’t very random. “Aha,” I thought, “Here’s something small and isolated that I can take on as a new hire. And it won’t take long; I can just draw on the random number chapter from our book.” Turns out that was partially right.

The first step was determining how good or bad the original PRNG was. Looking at it, it was clear that it was a linear congruential generator (LCG), which do have notoriously poor randomness in lower-order bits. They also fail the spectral test, i.e. if you generate points in space they tend to fall along visible planes. Not so good for generating tests for a graphics library. But how to verify this?

In the book I discuss some batteries of tests, such as Marsaglia’s Diehard and Brown’s DieHarder. In doing some research I found a couple more. First, there’s TestU01, which is a more extensive suite released in 2009. And Marsaglia and Tsang have created a smaller set of tests called tuftests, which they claim are nearly as rigorous as the large suites — i.e. if a PRNG passes tuftests, it’s highly likely to pass Diehard. For our case, we aren’t trying to find the ultimate PRNG, just something fast and reasonably random. So tuftests should suffice.

Tuftests consists of only three tests: the GCD test (as opposed to the GDC test, which probably involves giving a coherent talk after a night of parties), the Gorilla test, and the Birthday Spacings test. The GCD computes a large series of two pseudorandom variables, finds their greatest common denominators, and then compares the distribution of cycles necessary to compute the GCDs to the cycles needed for truly random variables. The Gorilla test is a variant of the Monkey test, where random strings of bits are generated using a single bit position of a random variable. This is done multiple times. The count of strings not generated should fall in a normal distribution. The Birthday Spacings test generates a set of birthdays in a “year”, and then determines the spacings between them, which should fall in a Poisson distribution. For all of these, the generated distribution is compared with the expected distribution, using chi square, Anderson-Darling or other method.

Testing the LCD used by Skia, it was clear that it failed the Gorilla test for all but the highest order bits (it may have also failed the Birthday test, I don’t recall now). So the belief that Skia’s PRNG needed improvement was verified. The next step was to find a decent replacement that doesn’t require a lot of overhead (important for testing on mobile devices). And I’ll cover my search for that next time.

4/1/2013

GDC 2013

Filed under: Tutorial — Jim @ 7:46 pm

So GDC 2013 has come and gone, and with it another tutorial session. This year I did not run the Physics Tutorial, passing that on to Erin Catto’s more than capable hands. Instead, I organized the Math Tutorial for the first day, with the following lineup:

  • Interpolation and Splines – Squirrel Eiserloh (The Guildhall at SMU)
  • Matrix Transformations – Squirrel Eiserloh (The Guildhall at SMU)
  • Understanding Quaternions – Jim Van Verth (Google)
  • Dual Numbers – Gino van den Bergen (Dtecta)
  • Orthogonal Matching Pursuit and K-SVD for Sparse Encoding – Robin Green (Microsoft) and Manny Ko (Imaginations Technologies)
  • Computational Geometry – Graham Rhodes (Applied Research Associates Inc.)
  • Interaction with 3D Geometry – Stan Melax (Intel)

Overall, I thought it was a good mix of beginning and advanced topics. So a big thank you to all the speakers — I learn something from them every year, and without them it wouldn’t be possible. And as time goes on, I’ll add links to the slides as they come in.

Before I close, I have one comment on my talk. As I was discussing the matrix form of the quaternion, I mentioned that multiplying by a rotation on the left is the same as multiplying by the inverse of the rotation on the right. As I think I made clear later, this is not true. I was trying to convey how I originally — and incorrectly — thought about it but I fear I may have misled some in the audience. What was thinking was that if you multiply a column vector on the right by a rotation matrix, i.e. Rv, this is the same as multiplying a row vector on the left by the inverse, i.e. vTR-1. But of course, we’re not multiplying vectors, we’re multiplying a matrix Q which represents a quaternion, which in turn represents a vector. So, not quite the same thing, and the end the result is not the same. I’ve modified the notes in the slides to make this clearer.

Powered by WordPress