PRNG vs RNG

xorshift.ts

// Run this file with:
//   npx ts-node -T xorshift.ts

const { randomFillSync } = require('crypto');

const enum Hardcode {
	IdBytesLength = 4,
	GeneratorsInParallel = 32,
	TestIterations = 1001,
}

type Xorshift128pState = BigUint64Array & { length: 2 };

/**
 * https://en.wikipedia.org/wiki/Xorshift#xorshift+
 */
function xorshift128p(state: Xorshift128pState): bigint {
	let t: bigint = state[0];
	const s: bigint = state[1];
	state[0] = s;
	t ^= (t << 23n) & 0xFFFFFFFFFFFFFFFFn;
	t ^= t >> 17n;
	t ^= s ^ (s >> 26n);
	state[1] = t;
	return (t + s) & 0xFFFFFFFFFFFFFFFFn;
}


/**
 * Math.random() implemented xorshift128+, seed is cryptographically random.
 * This behavior mimics the implmentation in most browsers.
 */
class Xorshift128PlusRandomSource {
	private readonly _xorshiftState: Xorshift128pState;

	public constructor() {
		this._xorshiftState = randomFillSync(new BigUint64Array(2));
	}

	public random(): number {
		const randBigInt = xorshift128p(this._xorshiftState);
		return Number(randBigInt) * (2 ** -64);
	}
}

interface RandomIdGenerator {
	randomId(): string;
}

/** Test PRNG */
class PrngRandomIdGenerator implements RandomIdGenerator {
	private readonly _pseudoMath: Xorshift128PlusRandomSource;

	public constructor() {
		this._pseudoMath = new Xorshift128PlusRandomSource();
	}

	/** Most of the UUID generations looks like this */
	public randomId(): string {
		let s = '';
		for (let i = 0; i < Hardcode.IdBytesLength * 2; i++) {
			s += Math.floor(this._pseudoMath.random() * 16).toString(16);
		}

		return s;
	}
}

/** Test RNG */
class CryptoRandomIdGenerator implements RandomIdGenerator {
	private readonly _buf: Buffer;

	public constructor() {
		this._buf = Buffer.alloc(Hardcode.IdBytesLength);
	}

	public randomId(): string {
		return randomFillSync(this._buf).toString('hex');
	}
}

/**
 * Runs several generators in parallel util the collision happens.
 * Mimics N browsers each generating random strings.
 * @returns The iteration when the collision happened. Higher is better.
 */
function generateInParallelIntilCollision(generators: RandomIdGenerator[]): number {
	const generatedEarlier = new Set<string>();

	for (let i = 0; i < 1e6 /* guard */; i++) {
		for (const generator of generators) {
			const randomId = generator.randomId();

			if (generatedEarlier.has(randomId)) {
				return i;
			} else {
				generatedEarlier.add(randomId)
			}
		}
	}

	// We've hit into loop guard: return at least something
	return Infinity;
}


/**
 * Do the above several times, each time with a fresh runtime
 */
function runTestCase(IdGeneratorCtor: { new(): RandomIdGenerator }): void {
	const testResults: number[] = [];

	// console.time('Time elapsed');
	for (let i = 0; i < Hardcode.TestIterations; i++) {
		const generators: RandomIdGenerator[] = [];
		for (let i = 0; i < Hardcode.GeneratorsInParallel; i++) {
			generators.push(new IdGeneratorCtor());
		}

		testResults.push(generateInParallelIntilCollision(generators));
	}
	// console.timeEnd('Time elapsed');

	console.log(testResults.join(', '));
	testResults.sort(sortNumeric);
	console.log('10 percentile', percentile(testResults, 10));
	console.log('Median', percentile(testResults, 50));
	console.log('90 percentile', percentile(testResults, 90));
}

function sortNumeric(a: number, b: number): number {
	return a - b;
}

function percentile<T>(sample: T[], perc: number): T {
	return sample[Math.round((sample.length - 1) / 100 * perc)];
}

console.log('== Count of random string generations before the collision happens ==');
console.log(`Running ${Hardcode.GeneratorsInParallel}x crypto random based generators, ${Hardcode.IdBytesLength} bytes each, ${Hardcode.TestIterations} iterations`);
runTestCase(CryptoRandomIdGenerator);

console.log('---');

console.log(`Running ${Hardcode.GeneratorsInParallel}x XorShift based generators, ${Hardcode.IdBytesLength} bytes each, ${Hardcode.TestIterations} iterations`);
runTestCase(PrngRandomIdGenerator);