From 69fdd621d2bb57e7145f242e9facc996f76562bc Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Sat, 19 Jun 2021 20:31:22 +0200 Subject: Changed stc64. Similar to sfc64, but a different output functions and 320 bit state (256 mutable). This is equally fast as the previous, but likely better quality because the 16-bit version is good, opposed to previous which failed PractRand. --- docs/crandom_api.md | 20 +++++++++++--------- include/stc/crandom.h | 38 +++++++++++++++++++------------------- 2 files changed, 30 insertions(+), 28 deletions(-) diff --git a/docs/crandom_api.md b/docs/crandom_api.md index a943f7ea..4093204e 100644 --- a/docs/crandom_api.md +++ b/docs/crandom_api.md @@ -8,25 +8,27 @@ See [random](https://en.cppreference.com/w/cpp/header/random) for similar c++ fu ## Description -**stc64** is a novel, extremely fast PRNG by Tyge Løvset, suited for parallel usage. It features a -Weyl-sequence as part of the state. In general testing, **stc64** is the fastest among *pcg64*, -*xoshiro256`**`*, *sfc64*, and *lehmer64*. +**stc64** is a novel, extremely fast PRNG by Tyge Løvset, suited for parallel usage. It features +Weyl-sequences as part of its state. It is inspired on *sfc64*, but has a different output function +and state size. -*wyrand* is faster on platforms with fast 128-bit multiplication, and has 2^64 period length -(https://github.com/lemire/SwiftWyhash/issues/10). However, *wyrand* is not suited for massive +**sfc64** is the fastest among *pcg*, *xoshiro`**`*, and *lehmer*. It is equally fast as *sfc64* on +most platforms. *wyrand* is faster on platforms with fast 128-bit multiplication, and has 2^64 period +length (https://github.com/lemire/SwiftWyhash/issues/10). However, *wyrand* is not suited for massive parallel usage due to its limited total minimal period length. -**stc64** does not require multiplication or 128-bit integer operations. It has 256 bit state, -but updates only 192 bit per generated number. +**stc64** does not require multiplication or 128-bit integer operations. It has 320 bit state, +but updates only 256 bit per generated number. -There is no *jump function*, but each odd number Weyl-increment (state[3]) starts a new +There is no *jump function*, but each odd number Weyl-increment (state[4]) starts a new unique 2^64 *minimum* length period. For a single thread, a minimum period of 2^127 is generated when the Weyl-increment is incremented by 2 every 2^64 output. **stc64** passes *PractRand* (tested up to 8TB output), Vigna's Hamming weight test, and simple correlation tests, i.e. *n* interleaved streams with only one-bit differences in initial state. +Also 32-bit and 16-bit versions passes PractRand up to their size limits. -For more, see the PRNG shootout by Vigna: http://prng.di.unimi.it and the debate between the authors of +For more, see the PRNG shootout by Vigna: http://prng.di.unimi.it and a debate between the authors of xoshiro and pcg (Vigna/O'Neill) PRNGs: https://www.pcg-random.org/posts/on-vignas-pcg-critique.html ## Header file diff --git a/include/stc/crandom.h b/include/stc/crandom.h index 073048ee..b6bd0c93 100644 --- a/include/stc/crandom.h +++ b/include/stc/crandom.h @@ -43,26 +43,37 @@ int main() { #include #include -typedef struct {uint64_t state[4];} stc64_t; +typedef struct {uint64_t state[5];} stc64_t; typedef struct {int64_t lower; uint64_t range, threshold;} stc64_uniform_t; typedef struct {double lower, range;} stc64_uniformf_t; typedef struct {double mean, stddev, next; unsigned has_next;} stc64_normalf_t; +/* PRNG stc64. + * Extremely fast PRNG suited for parallel usage with Weyl-sequence parameter. + * 320bit state, 256bit mutable. + * Noticable faster than xoshiro and pcg, but slighly slower than wyrand64, + * which only has a single 64-bit state and is unfit when longer periods or + * multiple threads are required. + * stc64 supports 2^63 unique threads with a minimum 2^64 period lengths each. + * Passes PractRand tested up to 8TB output, Vigna's Hamming weight test, + * and simple correlation tests, i.e. interleaved streams with one-bit diff state. + * The 16-bit version with LR=6, RS=5, LS=3 passes PractRand to multiple TB input. + */ -/* Stc64: random number generator, range [0, 2^64). PRNG copyright Tyge Løvset, NORCE Research, 2020 */ STC_API stc64_t stc64_init(uint64_t seed); STC_API stc64_t stc64_with_seq(uint64_t seed, uint64_t seq); STC_INLINE uint64_t stc64_rand(stc64_t* rng) { - uint64_t *s = rng->state; - const uint64_t b = s[1], result = s[0] ^ (s[2] += s[3]|1); - s[0] = (b + (b << 3)) ^ (b >> 11); - s[1] = ((b << 24) | (b >> (64 - 24))) + result; + uint64_t *s = rng->state; enum {LR=24, RS=11, LS=3}; + const uint64_t result = (s[0] ^ (s[3] += s[4]|1)) + s[1]; + s[0] = s[1] ^ (s[1] >> RS); + s[1] = s[2] + (s[2] << LS); + s[2] = ((s[2] << LR) | (s[2] >> (64 - LR))) + result; return result; } /* Global random() */ -static stc64_t stc64_global = {{0x26aa069ea2fb1a4d, 0x70c72c95cd592d04, 0x504f333d3aa0b359, 0x6a09e667a754166b}}; +static stc64_t stc64_global = {{0x26aa069ea2fb1a4d, 0x70c72c95cd592d04, 0x504f333d3aa0b359, 0x26aa069ea2fb1a4d, 0x6a09e667a754166b}}; STC_INLINE void stc64_srandom(uint64_t seed) { stc64_global = stc64_init(seed); } STC_INLINE uint64_t stc64_random(void) { return stc64_rand(&stc64_global); } @@ -103,22 +114,11 @@ STC_API double stc64_normalf(stc64_t* rng, stc64_normalf_t* dist); #if !defined(STC_HEADER) || defined(STC_IMPLEMENTATION) -/* PRNG crandom: by Tyge Løvset, NORCE Research, 2020. - * Extremely fast PRNG suited for parallel usage with Weyl-sequence parameter. - * 256bit state, updates 192bit per rng. - * Faster than pcg, sfc64, xoshiro256** on most platforms. - * wyrand64 is slightly faster, but has only 64-bit state, - * unfit when longer periods or multiple threads are required. - * stc64 supports 2^63 unique threads with a minimum 2^64 period lengths each. - * Passes PractRand tested up to 8TB output, Vigna's Hamming weight test, - * and simple correlation tests, i.e. interleaved streams with one-bit diff state. - */ - STC_DEF stc64_t stc64_init(uint64_t seed) { return stc64_with_seq(seed, seed + 0x3504f333d3aa0b34); } STC_DEF stc64_t stc64_with_seq(uint64_t seed, uint64_t seq) { - stc64_t rng = {{seed, seed, seed, (seq << 1u) | 1u}}; + stc64_t rng = {{seed, seed, seed, seed, (seq << 1) | 1}}; for (int i = 0; i < 12; ++i) stc64_rand(&rng); return rng; } -- cgit v1.2.3