Pseudo-random distribution in JavaScript

• Pseudo-random distribution in JavaScript
  • Introduction
  • Motivation
  • Approach
  • Results
    • 1. Math.random()
    • 2. Linear congruential generator
      • 2.1 RANDU
    • 3. Counter-based random number generator (CBRNG)
      • 3.1 Squares: A Fast Counter-Based RNG (Random Number Generator)
  • References

Introduction

A goal of this repository is to analyze the distribution of different pseudo-random number generation methods in plain JavaScript.

Motivation

While developing a Phaser video game I needed to randomly place objects in a 2D space. Despite the documentation of Math.random() stating it's a 'approximately uniform distribution' ¹, results looked awfully similar to a normal distribution (objects were generated mostly in the middle of the screen). I decided to investigate the issue and test Math.random(), as well as other pseudo-random number generators.

Approach

A random 1.000.000 numbers ([0, 1]) are generated using each method and saved in a CSV file. Results are then processed by pandas and matplotlib to generate a histogram and calculate a standard deviation. Tests were performed on an Apple M1 MacBook Air with 8GB of RAM and Node.js v20.3.0.

Results

1. Math.random()

The Math.random() static method returns a floating-point, pseudo-random number that's greater than or equal to 0 and less than 1. The implementation selects the initial seed to the random number generation algorithm; it cannot be chosen or reset by the user. ¹

Standard Deviation: 0.28883

2. Linear congruential generator

A linear congruential generator (LCG) is an algorithm that yields a sequence of pseudo-randomized numbers calculated with a discontinuous piecewise linear equation. The method represents one of the oldest and best-known pseudorandom number generator algorithms. ²

2.1 RANDU

RANDU is a linear congruential pseudorandom number generator, defined by the recurrence ³:

$V_{j+1} = 65539\cdot V_j, \bmod, 2^{31},$

Standard Deviation: 0.28847

3. Counter-based random number generator (CBRNG)

A counter-based random number generation (CBRNG, also known as a counter-based pseudo-random number generator, or CBPRNG) is a kind of pseudorandom number generator that uses only an integer counter as its internal state. They are generally used for generating pseudorandom numbers for large parallel computations. ⁴

3.1 Squares: A Fast Counter-Based RNG (Random Number Generator)

This implementation is based on the paper ⁵ by Sebastiano Vigna and is available as a npm package ⁶. GitHub page of the project ⁷.

Standard Deviation: 0.28855

References

Footnotes

1. Math.random Mozilla docs ↩ ↩²

2. Linear congruential generator Wikipedia page ↩

3. RANDU Wikipedia page ↩

4. Counter-based random number generator Wikipedia page ↩

5. Squares: A Fast Counter-Based RNG (Random Number Generator) ↩

6. Squares RNG npm package ↩

7. Squares RNG GitHub page ↩