GhostProxiesGhostProxies PRNG 32 B: The Fastest 32-Bit, Long-Period PRNG That Obsoletes 32-Bit Mersenne Twister
GhostProxies PRNG 32 B is a 32-bit, long-period pseudorandom number generator algorithm as a substantial improvement to both SIMD and standard 32-bit Mersenne Twister, MRG32k3a and WELL.
Library
Source
#ifndef GHOSTPROXIES_PRNG_32_B_H
#define GHOSTPROXIES_PRNG_32_B_H
#include <stdint.h>
struct ghostproxies_prng_32_b_s {
uint32_t blocks[1024];
uint32_t blocks_selector;
uint32_t increment;
uint32_t increment_offset;
};
uint32_t ghostproxies_prng_32_b(struct ghostproxies_prng_32_b_s *s);
#endif#include "ghostproxies_prng_32_b.h"
uint32_t ghostproxies_prng_32_b(struct ghostproxies_prng_32_b_s *s) {
uint32_t block = s->blocks[s->blocks_selector & 1023];
const uint32_t increment_offset_capture = s->increment_offset ^ s->increment;
s->blocks[s->blocks_selector & 1023] += increment_offset_capture;
s->increment_offset = ((s->increment_offset << 17)
| (s->increment_offset >> 15)) + s->increment;
s->increment += 1111111111;
s->blocks_selector++;
block += s->increment + increment_offset_capture;
s->blocks[block & 1023] += s->blocks_selector + block;
return block;
}Reference
ghostproxies_prng_32_b() is the randomization function that accepts the following argument.
1: s is the struct ghostproxies_prng_32_b_s pointer with 3 uint32_t integers s->a, s->b and s->increment. Each must be initialized with any combination of values.
The return value data type is uint32_t.
It returns the 32-bit unsigned integer pseudorandom number result.
Example
#include <stdio.h>
#include "ghostproxies_prng_32_b.h"
int main(void) {
struct ghostproxies_prng_32_b_s s;
unsigned short i = 0;
while (i != 1024) {
s.blocks[i] = 0;
i++;
}
s.blocks_selector = 0;
s.increment = 0;
s.increment_offset = 0;
i = 0;
while (i != 10) {
i++;
printf("Result %u is %u.\n", i, ghostproxies_prng_32_b(&s));
}
return 0;
}Requirements
It adheres to the C99 standard draft (ISO/IEC 9899:1999), although it's convertible to other programming languages and standards.
License
GhostProxies PRNG 32 B usage is subject to proprietary Skeleton Key licensing restrictions.
Evaluation is permitted for a reasonable, short period of time.
Explanation
GhostProxies PRNG 32 B passes statistical tests with efficient resource usage, fast speed and a long period relative to non-cryptographic, one-at-a-time PRNGs in applications requiring a large count of possible subsequent randomness results to emulate the properties of non-deterministic randomness.
It has faster speed with more flexibility, simplicity and consistent statistical quality than the optimized SIMD version of Mersenne Twister.
It's portable for both 32-bit and 64-bit systems.
It meets strict compliance, portability and security requirements.
It doesn't use modulus, multiplication or division arithmetic operations.
32-bit deterministic randomness is generated with a 32864-bit auxiliary state.
The period is adjustable to any halved amount by adjusting the 1024 state blocks, meaning the additional possible state sizes are 512, 256, 128, 64, 32, 16, 8, 4 and 2. If the blocks count is adjusted, the & 1023 mask instances must be adjusted accordingly. These varying state sizes may result in better or worse statistical quality by a small margin.
The estimated full cycle is 2³²⁷⁶⁸ numbers at almost double the period of Mersenne Twister, so re-seeding the initial state isn't required in most applications.
Furthermore, when all state bits are 0, the next pseudorandom number escapes zeroland quickly, making it impossible to have a broken state with any combination of numbers.
A round-robin number selector is incremented before assigning an additive XOR state to the selected s->blocks number, ensuring the closest thing to equal distribution across all possible cycles.
32 bits of state are summed with 1111111111 after each random number generation result and mixed in with the bit shuffling sequence. All state variable assignments are additive to emulate the properties of minimal rolling hash functions.
After 4294967295 random numbers are generated, the aforementioned 32 bits of state in s->increment completes a full cycle and the s->blocks bits avoid a full cycle, as demonstrated in the first 10 instances with the following code example.
#include <stdio.h>
#include "ghostproxies_prng_32_b.h"
int main(void) {
struct ghostproxies_prng_32_b_s s;
uint32_t increment_capture;
unsigned long i = 0;
while (i != 1024) {
s.blocks[i] = 0;
i++;
}
s.blocks_selector = 0;
s.increment = 0;
s.increment_offset = 0;
i = 0;
while (i != 10) {
ghostproxies_prng_32_b(&s);
increment_capture = s.increment;
ghostproxies_prng_32_b(&s);
while (s.increment != increment_capture) {
ghostproxies_prng_32_b(&s);
}
printf("%10lu %10lu %10lu %10lu %10lu %10lu %10lu %10lu\n",
s.blocks[0], s.blocks[1], s.blocks[2], s.blocks[3],
s.blocks[4], s.blocks[5], s.blocks[6], s.blocks[7]);
i++;
}
}The following output demonstrates a visual confirmation of good distribution among the first 10 blocks in s->blocks after each full cycle of s->increment.
145856490 74702479 1720334699 294391738 86623391 3122682911 623201601 956794711
1745367367 3905647329 1459227067 3707860734 3155451325 2271359762 271691890 1846523303
1676268354 2883564636 1196365818 1042241768 3431606807 1316059030 3105198913 2744281925
934763163 996062814 1590988578 2617803725 1166180205 1370804170 2712710613 3952334541
2123767113 4205114485 2720222887 3129488732 3396124387 374042849 2491509927 1230498270
3749987167 1918974978 2230643662 672820129 3863070173 1273479074 1381631644 3989966130
1365694205 2897959613 2769648881 3002480049 3428922824 1380501933 1580346077 2200621789
3335794959 2621990106 3458074297 3726482569 2480556323 1495858055 2104203597 1129934169
3171935274 125088466 2472675384 743176396 3495366937 855799645 1068118167 3203923756
1306368612 1193505014 979049283 1536395443 2295790904 4010444325 2939254578 302301034A wrapping additive constant added to each state block isn't enough to ensure a 2³²⁷⁶⁸ period, so each previous state block value is used as an offset to assign a combined pseudorandom value to a secondary state block.
The following code example demonstrates good distribution across s->blocks instead of brute-forcing millions of statistical tests.
#include <stdint.h>
#include <stdio.h>
struct ghostproxies_prng_32_b_s {
uint32_t blocks[1024];
uint32_t blocks_offset_assignment_counts[1024];
uint32_t blocks_selector;
uint32_t increment;
uint32_t increment_offset;
};
uint32_t ghostproxies_prng_32_b(struct ghostproxies_prng_32_b_s *s) {
uint32_t block = s->blocks[s->blocks_selector & 1023];
const uint32_t increment_offset_capture = s->increment_offset ^ s->increment;
s->blocks[s->blocks_selector & 1023] += increment_offset_capture;
s->increment_offset = ((s->increment_offset << 17)
| (s->increment_offset >> 15)) + s->increment;
s->increment += 1111111111;
s->blocks_selector++;
block += s->increment + increment_offset_capture;
s->blocks[block & 1023] += s->blocks_selector + block;
s->blocks_offset_assignment_counts[block & 1023]++;
return block;
}
int main(void) {
struct ghostproxies_prng_32_b_s s;
unsigned char blocks_offset_assignment_duplicate_states[1024];
unsigned long blocks_offset_assignment_duplicates_count = 0;
unsigned long i = 0;
unsigned short j = 0;
while (i != 1024) {
s.blocks[i] = 0;
s.blocks_offset_assignment_counts[i] = 0;
blocks_offset_assignment_duplicate_states[i] = 0;
i++;
}
s.blocks_selector = 0;
s.increment = 0;
s.increment_offset = 0;
while (i != 1111111111) {
ghostproxies_prng_32_b(&s);
i++;
}
i = 0;
while (i != 1024) {
j = 0;
while (j != 1024) {
if (
i != j &&
s.blocks_offset_assignment_counts[i]
== s.blocks_offset_assignment_counts[j] &&
blocks_offset_assignment_duplicate_states[i] != 1
) {
blocks_offset_assignment_duplicate_states[j] = 1;
blocks_offset_assignment_duplicates_count++;
}
j++;
}
i++;
}
i = 0;
while (i != 1024) {
printf("Block %lu is assigned by an offset %lu times.\n",
i + 1,
s.blocks_offset_assignment_counts[i]);
i++;
}
printf("\nThere are %lu duplicate offset block assignments.\n",
blocks_offset_assignment_duplicates_count);
return 0;
}The following first 20 offset assignment counts demonstrate the semi-linear, yet semi-randomized offset assignments distributed throughout the state in s->blocks.
Block 1 is assigned by an offset 1083842 times.
Block 2 is assigned by an offset 1083792 times.
Block 3 is assigned by an offset 1086149 times.
Block 4 is assigned by an offset 1085322 times.
Block 5 is assigned by an offset 1085457 times.
Block 6 is assigned by an offset 1086610 times.
Block 7 is assigned by an offset 1084757 times.
Block 8 is assigned by an offset 1086702 times.
Block 9 is assigned by an offset 1085031 times.
Block 10 is assigned by an offset 1085576 times.
Block 11 is assigned by an offset 1083659 times.
Block 12 is assigned by an offset 1085423 times.
Block 13 is assigned by an offset 1086734 times.
Block 14 is assigned by an offset 1084253 times.
Block 15 is assigned by an offset 1084380 times.
Block 16 is assigned by an offset 1083285 times.
Block 17 is assigned by an offset 1085566 times.
Block 18 is assigned by an offset 1085682 times.
Block 19 is assigned by an offset 1083464 times.
Block 20 is assigned by an offset 1085869 times.Furthermore, there are 145 colliding offset block increments in the aforementioned instance out of 1024 total blocks.
As the count of generated numbers increases, the number of blocks with the same amount of offset increments decreases.
There are 93 collisions after generating 2222222222 numbers, then 78 collisions after generating 3333333333 numbers.
The following test results are performed with all state bits initialized to 0.
It passes all TestU01 BigCrush battery tests as the fastest long-period Mersenne Twister alternative that passes BigCrush.
It's tested with all values initialized to 0.
When initializing using 1024 random TRNG numbers manually assigned to s->blocks, the results are similar with between 98% to 100% of BigCrush tests passed consistently due to the proven distribution properties.
Furthermore, Mersenne Twister is known to exhibit multiple consistent 32-bit test failures with small and large random number tests.
Compared to MRG32k3a, the average speed is 1370% faster.
Compared to 32-bit Mersenne Twister, the average speed is at least 40% faster than the unoptimized variant and 25% faster than the SIMD-optimized variant.
Compared to WELL, the average speed is 81% faster.
Compared to all Xoroshiro and Xorshift algorithms, it's at least 3% faster.
Furthermore, most of these compared PRNGs are vulnerable to several confirmed broken cycles when seeded with specific values, including 0.
When efficient memory usage and faster speed are required for 32-bit PRNG usage within a large number of processes, GhostProxies PRNG 32 A is the fastest 32-bit sequential PRNG that passes BigCrush tests with a short period.
All speed tests generate and access 1 billion numbers.