From a147a1be246472d079f72fc22e065080d1588e29 Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Wed, 16 Dec 2020 10:58:04 +0100 Subject: Reverted back API to easier naming scheme of crandom.h types and methods. Highly optimized generation of unbiased uniform bounded random numbers. Only 33% overhead. --- docs/cpqueue_api.md | 6 +++--- docs/crandom_api.md | 57 +++++++++++++++++++++++++++++------------------------ 2 files changed, 34 insertions(+), 29 deletions(-) (limited to 'docs') diff --git a/docs/cpqueue_api.md b/docs/cpqueue_api.md index 1e92277a..ac33e68f 100644 --- a/docs/cpqueue_api.md +++ b/docs/cpqueue_api.md @@ -63,13 +63,13 @@ using_cpqueue(i, cvec_i, >); // adaptor type, '>' = min-heap int main() { size_t N = 10000000; - cstc64_t rng = cstc64_init(1234); - cstc64_uniform_t dist = cstc64_uniform_init(0, N * 10); + crand_t rng = crand_init(1234); + crand_uniform_t dist = crand_uniform_init(0, N * 10); cpqueue_i heap = cpqueue_i_init(); // Push ten million random numbers to priority queue, plus some negative ones. c_forrange (N) - cpqueue_i_push(&heap, cstc64_uniform(&rng, &dist)); + cpqueue_i_push(&heap, crand_uniform(&rng, &dist)); c_push_items(&heap, cpqueue_i, {-231, -32, -873, -4, -343}); // Extract and display the fifty smallest. diff --git a/docs/crandom_api.md b/docs/crandom_api.md index 57697067..53e8a0d1 100644 --- a/docs/crandom_api.md +++ b/docs/crandom_api.md @@ -5,12 +5,12 @@ This describes the API of module **crand**. It contains *pcg32* created by Melis ## Types -| Name | Type definition | Used to represent... | -|:--------------------|:--------------------------------------------|:-----------------------------| -| `cstc64_t` | `struct {uint64_t state[4];}` | The PRNG engine type | -| `cstc64_uniform_t` | `struct {int64_t offset; uint64_t range;}` | Integer uniform distribution | -| `cstc64_uniformf_t` | `struct {double offset, range;}` | Real number uniform distr. | -| `cstc64_normalf_t` | `struct {double mean, stddev;}` | Normal distribution type | +| Name | Type definition | Used to represent... | +|:-------------------|:-------------------------------------------|:-----------------------------| +| `crand_t` | `struct {uint64_t state[4];}` | The PRNG engine type | +| `crand_uniform_t` | `struct {int64_t offset; uint64_t range;}` | Integer uniform distribution | +| `crand_uniformf_t` | `struct {double offset, range;}` | Real number uniform distr. | +| `crand_normalf_t` | `struct {double mean, stddev;}` | Normal distribution type | ## Header file @@ -22,28 +22,33 @@ All cstr definitions and prototypes may be included in your C source file by inc ## Methods ```c - 1) cstc64_t cstc64_with_seq(uint64_t seed, uint64_t seq); - 2) cstc64_t cstc64_init(uint64_t seed); - 3) uint64_t cstc64_rand(cstc64_t* rng); - 4) double cstc64_randf(cstc64_t* rng); - 5) cstc64_uniform_t cstc64_uniform_init(int64_t low, int64_t high); - 6) int64_t cstc64_uniform(cstc64_t* rng, cstc64_uniform_t* dist); - 7) cstc64_uniformf_t cstc64_uniformf_init(double low, double high); - 8) double cstc64_uniformf(cstc64_t* rng, cstc64_uniformf_t* dist); - 9) cstc64_normalf_t cstc64_normalf_init(double mean, double stddev); -10) double cstc64_normalf(cstc64_t* rng, cstc64_normalf_t* dist); + 1) crand_t crand_init(uint64_t seed); + 2) crand_t crand_with_seq(uint64_t seed, uint64_t seq); + 3) uint64_t crand_next(crand_t* rng); + 4) double crand_nextf(crand_t* rng); + 5) crand_uniform_t crand_uniform_init(int64_t low, int64_t high); + 6) int64_t crand_uniform(crand_t* rng, crand_uniform_t* dist); + 7) crand_uniformf_t crand_uniformf_init(double low, double high); + 8) double crand_uniformf(crand_t* rng, crand_uniformf_t* dist); + 9) crand_normalf_t crand_normalf_init(double mean, double stddev); +10) double crand_normalf(crand_t* rng, crand_normalf_t* dist); ``` `1-2)` PRNG 64-bit engine initializers. `3)` Integer generator, range \[0, 2^64). `4)` Double RNG with range \[0, 1). `5-6)` Uniform integer RNG with range \[*low*, *high*]. `7-8)` Uniform double RNG with range \[*low*, *high*). `9-10)` Normal-distributed double -RNG, around 68% of the values are within the range [*mean* - *stddev, *mean* + *stddev*]. +RNG, around 68% of the values fall within the range [*mean* - *stddev, *mean* + *stddev*]. -The method `cstc64_rand(cstc64_t* rng)` is an extremely fast PRNG by Tyge Løvset, suited for parallel usage. -It features a Weyl-sequence as part of the state. It is faster than *sfc64*, *wyhash64*, *pcg64*, and almost -50% faster than *xoshiro256\*\** on GCC. It does not require fast multiplication or 128-bit integer operations. -It has a 256 bit state, but updates only 192 bit per generated number. There is no *jump function*, but incrementing -the Weyl-increment by 2, initializes a new unique 2^64 *minimum* length period. 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. +**crand** is an extremely fast PRNG by Tyge Løvset, suited for parallel usage. It features a +Weyl-sequence as part of the state. It is faster than *sfc64*, *wyhash64*, *pcg64*, and almost +50% faster than *xoshiro256\*\** compiled with GCC. It does not require fast multiplication or +128-bit integer operations. It has a 256 bit state, but updates only 192 bit per generated +number. There is no *jump function*, but by incrementing the Weyl-increment by 2, it initializes +a new unique 2^64 *minimum* length period. Note that for each Weyl-increment, the expected period +length is about 2^126. For a single thread, a minimum period of 2^127 is generated if the +Weyl-increment is incremented by 2 every 2^64 number output. + +*crand* 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. ## Example ```c @@ -75,13 +80,13 @@ int main() // Setup random engine with normal distribution. uint64_t seed = time(NULL); - cstc64_t rng = cstc64_init(seed); - cstc64_normalf_t dist = cstc64_normalf_init(Mean, StdDev); + crand_t rng = crand_init(seed); + crand_normalf_t dist = crand_normalf_init(Mean, StdDev); // Create histogram map cmap_i mhist = cmap_i_init(); for (size_t i = 0; i < N; ++i) { - int index = (int) round( cstc64_normalf(&rng, &dist) ); + int index = (int) round( crand_normalf(&rng, &dist) ); cmap_i_emplace(&mhist, index, 0).first->second += 1; } -- cgit v1.2.3