Wednesday, August 28, 2013

Pseudo-Random Number Generation (Seeded) in JavaScript

What, no seed on Math.random()? But I could've sworn...

I was faced with a situation where I wanted to produce random numbers from a seeded generator in JavaScript, and I noticed (strangely for the first time) that Math.random() is a random number generator, but not a pseudo-random number generator (PRNG). The problem I was trying to solve is that I wanted to create random numbers, but I wanted to be able to recreate the same series of random numbers.


The Mersenne Twister

So I hit the Googles, and immediately came across this post on StackOverflow that had a few solutions for PRNG. The post suggested that Mersenne Twister was one of the better algorithms for PRNG, but didn't really offer up code for that in JavaScript. So I Googled further and found that there was a JavaScript implemenation of Messente Twister, but I didn't like it, really. No offense meant to the original authors, but it seemed to be a port of a C or C++ implementation straight to JavaScript, and was a little bulky and not factored out enough for me.


TL;DR: I made an open source Mersenne Twister implementation in JavaScript

It's here on GitHub, hopefully someone else finds it useful. The goal was to keep it concise and compact.

What does it do? It produces evenly distributed random integers between 0 and 4,294,967,296 (aka 0x100000000) from a seeded generator.

BTW: If anyone is an expert in cryptography or mathematics please review my implementation.

4 comments:

  1. Your implementation is broken. JS bitwise operators are signed, the algo is not. You're getting some other sequence with unknown properties.

    ReplyDelete
    Replies
    1. Awesome! Thanks for your feedback!

      I'm not sure what you mean by a "signed bitwise operator". Perhaps you're talking about how JS converts the operands to signed 32-bit integers (and then back to 64-bit floats)?

      I'm also not able to locate documents specifying that this algorithm is "unsigned" which I presume to mean it only works when manipulating unsigned integers.

      If you are correct, this should still work for randomization, it just wouldn't be a Mersenne Twister, I guess, just a ... psuedo-mersenne twister? Haha... I dunno.

      So how would you fix it? I'd love to see a pull request.

      Thanks again!

      Delete
    2. I could see (sort of) what you mean. I've made a few quick changes to the code base, but I'm not sure if they will really "fix" the issue. It will require some research to be sure. Thanks again! THIS is why I do this blog.

      Delete
  2. What happens is that when a bitwise operator changes bit 32, the resulting number becomes negative for the subsequent arithmetic. It's a pain in the butt to fix. You basically need to write your own functions in JS for unsigned 32-bit arithmetic. Also use >>> 0.

    ReplyDelete

This form allows some basic HTML. It will only create links if you wrap the URL in an anchor tag (Sorry, it's the Blogger default)