Random.ts

// Copyright 2016 Erik Neumann.  All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the 'License');
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an 'AS IS' BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

import { Util } from "./Util.js";

/** Pseudo-random number generator.
*/
export interface Random {

/** Returns the modulus of the random number generator.
@return the modulus of the random number generator
*/
getModulus(): number;

/** Returns the seed of the random number generator.
@return the seed of the random number generator
*/
getSeed(): number;

/** Returns random floating point number in range `[0,1]`.
@return random floating point number in range `[0,1]`
*/
nextFloat(): number;

/** Returns next random integer in range 0 (inclusive) to modulus (exclusive).
@return next the pseudo-random number
*/
nextInt(): number;

/** Returns random integer in range 0 (inclusive) to n (exclusive).
@param n the limit of the range
@return random integer in range 0 (inclusive) to n (exclusive)
*/
nextRange(n: number): number;

/** Returns an array of integers from 0 to `n-1`, in random order.
@param n the size of the array to create
@return an array of integers from 0 to `n-1`, in random order.
*/
randomInts(n: number): number[];

/** Sets the seed of the random number generator; must be an integer between 0
(inclusive) and modulus (exclusive).
@param seed  the seed to start the random number generator with
@throws if seed is not an integer between 0 (inclusive) and modulus
    (exclusive).
*/
setSeed(seed: number): void;
}

/** Pseudo-random number generator using a Linear Congruential Generator (LCG).

This class is designed to give same numbers in both Java and Javascript, so that
tests using this class will have the same results. In Java we use floating point double
numbers to match how Javascript stores numbers.

Linear Congruential Generator (LCG)
-----------------------------------
From <http://en.wikipedia.org/wiki/Linear_congruential_generator>

>The generator is defined by the recurrence relation:
```text
X_{n+1} = ( a X_n + c ) mod m
```
> where `X` is the sequence of pseudorandom values, and
```text
m, 0 < m  – the 'modulus'
a, 0 < a < m – the 'multiplier'
c, 0 <= c < m – the 'increment'
X_0, 0 <= X_0 < m – the 'seed' or 'start value'
```

Period Length
-------------
From <http://en.wikipedia.org/wiki/Linear_congruential_generator>

>Provided that the offset `c` is nonzero, the LCG will have a full period for all seed
values if and only if:
```text
c and m are relatively prime,
a - 1 is divisible by all prime factors of m,
a - 1 is a multiple of 4 if m is a multiple of 4.
```
>These three requirements are referred to as the Hull-Dobell Theorem. While LCGs are
capable of producing pseudorandom numbers which can pass formal tests for randomness,
this is extremely sensitive to the choice of the parameters `c`, `m`, and `a`.

The numbers chosen for RandomLCG satisfy the above conditions.
```text
m = 2 ^ 32 = 4,294,967,296
```
Here are the prime factors of the multiplier, `a`
```text
a = 1,664,525 = 5 x 5 x 139 x 479
a - 1 = 1664524 = 2 x 2 x 71 x 5861
c = 1,013,904,223 is a prime number
```

Floating Point Number
---------------------
The double number format allows exact representation of all integers with absolute
value less than `2^53`. We need to avoid making numbers larger than `2^53` to avoid
loss of accuracy. Every number generated will be between 0 and `m-1`. The maximum
number that can be made in the algorithm is `(m-1)*a + c`. So we have to ensure that
```text
(m-1)*a + c < 2^53.
```
For the numbers chosen this works out to:
```text
(2^32-1)*1664525 + 1013904223 = 3.5745412314269e15
```
This is less than `2^53 = 9.00719925474099e15`, so we should stay within the range of
exact integers.

Warning About Usage
-------------------
The series of numbers generated by a particular instance of RandomLCG will be
pseudo-random. But if you make another instance of RandomLCG with a seed that is close
to the first, the two RandomLCG instances will produce a highly correlated series. For
example, repeatedly calling the following will produce a pretty much linear non-random
sequence because `Date.now()` returns the current time in milliseconds which doesn't
change much between invocations.
```
new RandomLCG(Date.now()).nextFloat();
```
*/
export class RandomLCG implements Random {
  private seed_: number;

/**
* @param seed starting seed number should be an integer from 0 to `m-1`;
*    otherwise it is manipulated to be in that range.
*/
constructor(seed: number) {
  // Ensure seed is an integer between 0 and modulus.
  seed = Math.floor(Math.abs(seed)) % RandomLCG.m;
  this.seed_ = seed;
  RandomLCG.checkSeed(this.seed_);
  // ensure that maximum number made during the algorithm < 2^53
  Util.assert((RandomLCG.m - 1) * RandomLCG.a + RandomLCG.c < Math.pow(2, 53));
};

/** @inheritDoc */
toString() {
  return 'RandomLCG{seed: '+this.seed_+'}';
};

/** Ensure seed is integer between 0 (inclusive) and modulus (exclusive) */
private static checkSeed(seed: number) {
  const err = 'random seed must be '
  if (seed < 0) {
    throw err + '0 or greater '+seed;
  }
  if (seed >= RandomLCG.m) {
    throw err + 'less than '+RandomLCG.m+' was '+seed;
  }
  if (seed != Math.floor(seed)) {
    throw err + 'an integer '+seed;
  }
};

/** @inheritDoc */
getModulus() {
  return RandomLCG.m;
};

/** @inheritDoc */
getSeed() {
  return this.seed_;
};

/** @inheritDoc */
nextFloat() {
  const x = this.nextInt_();
  if (RandomLCG.DEBUG_RANDOM) {
    console.log(' '+x);
  }
  return x / (RandomLCG.m - 1);
};

/** @inheritDoc */
nextInt() {
  const x = this.nextInt_();
  if (RandomLCG.DEBUG_RANDOM) {
    console.log(' '+x);
  }
  return x;
};

/**
@return next the pseudo-random number
*/
private nextInt_(): number {
  const r = this.seed_ * RandomLCG.a + RandomLCG.c;
  const m = RandomLCG.m;
  this.seed_ = r - Math.floor(r/RandomLCG.m)*RandomLCG.m;
  RandomLCG.checkSeed(this.seed_);
  if (RandomLCG.DEBUG_RANDOM_DEEP) {
    const err = new Error();
  }
  return this.seed_;
};

/** @inheritDoc */
nextRange(n: number) {
  const x = this.nextRange_(n);
  if (RandomLCG.DEBUG_RANDOM) {
    console.log(' '+x);
  }
  return x;
};

/** Returns random integer in range 0 (inclusive) to n (exclusive).
@param n the limit of the range
@return random integer in range 0 (inclusive) to n (exclusive)
*/
private nextRange_(n: number): number {
  if (n <= 0)
    throw 'n must be positive';
  // We don't use modulo because of weak randomness in lower bits.
  const randomUnder1 = this.nextInt_() / RandomLCG.m;
  return Math.floor(randomUnder1 * n);
};

/** @inheritDoc */
randomInts(n: number) {
  const set_ = new Array(n);
  const src = new Array(n);
  for (let i=0; i<n; i++) {
    set_[i] = -1;
    src[i] = i;
  }
  let m = n;
  let setCount = 0;
  // move numbers from src to set, in random sequence
  do {
    const k = this.nextRange_(m--);
    // find the k'th number in src
    let srcCount = 0;
    for (let j=0; j<n; j++) {
      if (src[j]<0)
        continue;
      if (srcCount++ == k) {
        set_[setCount++] = src[j];
        src[j] = -1;
        break;
      }
    }
  } while (set_[n-1]<0);
  // for debugging:  report the set of numbers found
  if (RandomLCG.DEBUG_RANDOM) {
    let s = '';
    for (let i=0; i<set_.length; i++) {
      s += ' '+set_[i];
    }
    console.log(s);
  }
  return set_;
};

/** @inheritDoc */
setSeed(seed: number) {
  RandomLCG.checkSeed(seed);
  this.seed_ = seed;
};

static readonly DEBUG_RANDOM = false;
static readonly DEBUG_RANDOM_DEEP = false;
static readonly m = 0x100000000; // = 2^32 the 'modulus'
static readonly a = 1664525; // the 'multiplier'
static readonly c = 1013904223; // the 'increment' or 'offset'

} // end RandomLCG class

Util.defineGlobal('lab$util$RandomLCG', RandomLCG);