shioi pseudorandom number generator

Japanese version is here. / 日本語はこちら

I introduce some new LFSR-based pseudorandom number generators.
They have interesting jump characteristics.

Minimal Implementation (C)

uint64_t rotl(uint64_t x, int k) { return (x << k) | (x >> (-k & 63)); }
// State must be initialized with any value except {0, 0}
// Note that it uses arithmetic right shift
uint64_t next(uint64_t state[2]) {
	uint64_t s0 = state[0], s1 = state[1];
	uint64_t result = rotl(s0 * 0xD2B74407B1CE6E93, 29) + s1;
	state[0] = s1;
	state[1] = (s0 << 2) ^ ((int64_t)s0 >> 19) ^ s1;
	return result;
}
// equivalent to 2^64 next() calls
void jump64(uint64_t state[2]) {
	uint64_t s0 = state[0], s1 = state[1];
	state[0] = s0 ^ s1;
	state[1] = (s0 << 2) ^ ((int64_t)s0 >> 19);
}

For more details, see shioi128.c.

Pros

1. It is fast in 64-bit environment.
   • About 3.1 times faster than Mersenne Twister(64 bit version).
2. It is portable and easy to implement.
   • It does not use environment / language dependent instructions such as 128-bit multiplication.
3. Its period is 2^128 - 1, which is mathematically provable.
   • It is sufficient for games and simulations.
4. The output is 1-dimensionally equidistributed. All 64-bit integer values are output with almost equal probability.
5. There are no low quality bits in the output.
   • As with LCG, there is no problem that the lower bits have low randomness.
6. It is space efficient.
   • It uses only 128 bits == 16 bytes.
7. It passes many powerful randomness tests.
   (In the following, "rev" represents the output bit order reversed, and "std" represents the output as it is.)
   • PractRand v0.94 expanded extra ( -tf 2 -te 1 ) 32TB: no anomalies in 2417 test result(s)
   • Hamming-weight dependencies 1.5PB: p = 0.356
   • TestU01 v.1.2.3 BigCrush std/rev: In all tests, p in [1e-10, 1 - 1e-10]
   • gjrand v4.2.1.0
     • testunif 10T ( --ten-tera ): p = std 0.831 / rev 0.283
     • testfunif 1T ( --tera ): p = std 0.526 / rev 0.448
8. It has a fast jump function available. It makes it easy to parallel execution.
   • An operation equivalent to 2^64 next() calls can be performed in same amount of time as next().
   • It provides 2^64 non-overlapping sequences of length 2^64.

Cons

1. It is not cryptographically secure pseudorandom number generator.
   • DO NOT use for cryptographic purposes.
   • I tried to restore the internal state from 3 consecutive raw 64-bit outputs using Z3 solver, but failed in a day.
2. There are variants that use 32-bit words, but the investigation is incomplete.
3. 64-bit constant multiplication is required. In an environment where this is slow, output speed may decrease.
4. Because it is new, it has not been investigated by others.

Comparison

Comparison with major (64-bit output) pseudorandom number generators:

Name	Period	Size(bytes)	Equidistribution	Failed Test	Speed(64-bit/ns)
sfc64	> 2^64	32	0	-	1.21
seiran128	2^128 - 1	16	1	-	1.20
xoroshiro128+	2^128 - 1	16	1	BRank, hwd	1.13
👉 shioi128	2^128 - 1	16	1	-	1.00
xoshiro256**	2^256 - 1	32	4	-	0.99
lehmer128 (LCG)	2^126	16	1	TMFn	0.74
splitmix	2^64	8	1	-	0.68
pcg64_xsh_rr	2^128	16	1	-	0.38
mt19937_64 (Mersenne Twister)	2^19937 - 1	2500	311	BRank	0.32
tinymt64	2^127 - 1	16	1	BRank, hwd	0.24

Harness used in xoshiro/xoroshiro was used for speed measurement. The measurement environment is Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz / gcc 7.3.0.
The speed may vary depending on the environment and circumstances.

License

Public Domain (CC0)