-
-
Notifications
You must be signed in to change notification settings - Fork 3
/
XorShift.ts
85 lines (82 loc) · 2.71 KB
/
XorShift.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import { RandomGenerator } from './RandomGenerator';
// XorShift128+ with a=23, b=18, c=5
// - http://vigna.di.unimi.it/ftp/papers/xorshiftplus.pdf
// - http://vigna.di.unimi.it/xorshift/xorshift128plus.c
// - https://docs.rs/crate/xorshift/0.1.3/source/src/xorshift128.rs
//
// NOTE: Math.random() of V8 uses XorShift128+ with a=23, b=17, c=26,
// See https://github.com/v8/v8/blob/4b9b23521e6fd42373ebbcb20ebe03bf445494f9/src/base/utils/random-number-generator.h#L119-L128
class XorShift128Plus implements RandomGenerator {
constructor(
private s01: number,
private s00: number,
private s11: number,
private s10: number,
) {}
clone(): XorShift128Plus {
return new XorShift128Plus(this.s01, this.s00, this.s11, this.s10);
}
next(): [number, XorShift128Plus] {
const nextRng = new XorShift128Plus(this.s01, this.s00, this.s11, this.s10);
const out = nextRng.unsafeNext();
return [out, nextRng];
}
unsafeNext(): number {
const a0 = this.s00 ^ (this.s00 << 23);
const a1 = this.s01 ^ ((this.s01 << 23) | (this.s00 >>> 9));
const b0 = a0 ^ this.s10 ^ ((a0 >>> 18) | (a1 << 14)) ^ ((this.s10 >>> 5) | (this.s11 << 27));
const b1 = a1 ^ this.s11 ^ (a1 >>> 18) ^ (this.s11 >>> 5);
const out = (this.s00 + this.s10) | 0;
this.s01 = this.s11;
this.s00 = this.s10;
this.s11 = b1;
this.s10 = b0;
return out;
}
jump(): XorShift128Plus {
const nextRng = new XorShift128Plus(this.s01, this.s00, this.s11, this.s10);
nextRng.unsafeJump();
return nextRng;
}
unsafeJump() {
// equivalent to 2^64 calls to next()
// can be used to generate 2^64 non-overlapping subsequences
let ns01 = 0;
let ns00 = 0;
let ns11 = 0;
let ns10 = 0;
const jump = [0x635d2dff, 0x8a5cd789, 0x5c472f96, 0x121fd215];
for (let i = 0; i !== 4; ++i) {
for (let mask = 1; mask; mask <<= 1) {
// Because: (1 << 31) << 1 === 0
if (jump[i] & mask) {
ns01 ^= this.s01;
ns00 ^= this.s00;
ns11 ^= this.s11;
ns10 ^= this.s10;
}
this.unsafeNext();
}
}
this.s01 = ns01;
this.s00 = ns00;
this.s11 = ns11;
this.s10 = ns10;
}
getState(): readonly number[] {
return [this.s01, this.s00, this.s11, this.s10];
}
}
function fromState(state: readonly number[]): RandomGenerator {
const valid = state.length === 4;
if (!valid) {
throw new Error('The state must have been produced by a xorshift128plus RandomGenerator');
}
return new XorShift128Plus(state[0], state[1], state[2], state[3]);
}
export const xorshift128plus = Object.assign(
function (seed: number): RandomGenerator {
return new XorShift128Plus(-1, ~seed, seed | 0, 0);
},
{ fromState },
);