There is a non-deterministic cellular automaton simulation that I have coded in a few in different languages on everything from a Commodore Vic-20 to an Android phone. It's basically a grid populated by various colors that change states based on some random probabilities. Ok, that explanation didn't sound as simple as I hoped, let's try again: It's basically a screen full of squares that shift colors in a random fashion. I like to code it because it is pretty to look at.
The important thing is that for each frame in the simulation I need to generate a random number between 0 and 3 for each colored block. The more colored blocks you can pack on the screen, the better the light show looks. With too many blocks the computer slows down and that doesn't look good at all. My latest implementation was in HTML5 and JavaScript. Since the program needs a lot of random input, I was curious about how quickly JavaScript could pump out a series of random numbers. It turned out to be more than fast enough and my program is actually limited by the display code.
Even though the random number generation wasn't my bottleneck, I was interested in seeing if I could generated the randomness I needed more quickly. You see, I have a special case. I only need 2 bits of randomness to get my number between 0 and 3. The typical JavaScript example for this would look like:
r = Math.floor(Math.random() * 4);
My first thought was that I'm generating a lot of random bits, packing them into a floating point number, then doing a floating point multiplication, then throwing most of the result away. There has to be a better way. First I needed a benchmark to compare my experiments against:
var iterations = 1000000;
function basicRand() {
var r = 0;
for (var i = iterations; i > 0; i--) {
r = Math.floor(Math.random() * 4);
}
}
I used Firefox to profile the script and found that it ran in 85 ms. As I said, more than fast enough for my real purpose, but I was curious.
Experiment #1 was to see if I could speed things up by forgoing the floating point math and converting the random number to a string and extracting the random digits. Sure that's a lot of work, but I could get a lot of significant random digits out of a single random number....and doing this is easy in JavaScript so it was worth a try:
var digitString = "";
function fasterRand() {
var r = 0;
var digit = 0;
for (var i = iterations; i > 0; i--) {
digit = 9;
// throw out any 8s and 9s because they will skew the distribution
while (digit > 7) {
if (digitString == "") {
// we were out of digits, create a new random number and convert to a string
digitString = Math.random().toString().substr(2,12);
}
digit = parseInt(digitString.substr(0, 1)); // grab the first digit
digitString = digitString.substr(1); // shift the first digit out of the string
}
r = digit % 4; // do a mod 4 so the result is in the 0-3 range
}
}
This function was clearly misnamed because it took 258ms to generate the 1 million random numbers. That is about 3 times slower than the standard approach! In retrospect, I think I should have known that all the string manipulation would suck up a lot of cycles.
I did have another idea that involved shifting the random bits around and using bitwise & to get the bits unpacked. Reading some documentation I found that JavaScript is a little funny about giving you access to the underlying bits of your variables. No matter the original type of a variable, the bitwise operators will be converted to 32 bit signed integers. Even still, that means that a randomly generated integer should have 32 accessible bits of randomness. My next try was this:
function shiftRand() {
var r = 0;
var raw = 0;
var maxint = Math.pow(2, 32);
for (var i = iterations; i > 0; i--) {
raw = parseInt(Math.random() * maxint);
for (var j = 0; j < 15; j++) {
r = raw & 3;
raw = raw >> 2;
i--;
}
}
}
Much better! This generated the million random numbers in just 12 ms! That is about 7 times faster than the standard implementation. If I was using this for scientific research I would want to do some analysis of the code to make sure that my results are just as random as the standard implementation. Since this is really just a toy application, I also don't mind if I loose a little of the randomness.
Your mileage may vary: the more random bits you actually need the less the speedup will be. I did some quick tests and found that if if you need 16 bits of randomness it is still faster to break down the 32 bit random integer than to create two unique randoms, but it's something close to 1.25 times faster. Still better, but not nearly so dramatic.
A real JavaScript ninja can probably wring out a faster implementation, but I am quite happy with my 7 fold improvement. If you have any suggestions for faster generation of random numbers, let me know in the comments!
