Xoroshiro32ppg

[Chris Rutz]

ON HOLD PENDING REVIEW... SEE TO DO LIST

I have modified Xoroshiro32++ to improve escape from zero behavior and general statistical properties: Xoroshiro32ppg

The modification required only three minor changes:

1. Added a Boolean negation character '~' to one of the s1 occurrences.

2. Reversed the direction of the shift from '<<' to '>>'.

3. Adapted the constants to the above changes, most notably setting B = 1 to form an Inverted Gray Code with changes #1 and #2.

TO DO LIST:

1. Calculate invalid seed for each candidate set of triplets, as 0,0 no longer applies when negation/not is used. TEDIOUS... HOWEVER, BRUTE-FORCE AT 32-BIT TAKES ONLY A FEW SECONDS PER CANDIDATE SET.

2. Calculate output correction for each candidate set, as the normal output short by a single missing zero is now missing a single non-zero value. DONE: PASS INVALID SEED HALVES TO OUTPUT SCRAMBLER.

3. Re-evaluate the reversal of the shift and the recommendation of B = 1, when in fact other choices may be superior. LIKELY SHIFT IN EITHER DIRECTION CAN WORK WELL - BUT MUST ANALYZE REVERSE BITS ALSO.

Escape-from-zero behavior with only 1 state bit set (in average bits set per for 10 consecutive 16-bit outputs):


Xoroshiro32pp  1.5     5.375    6.96875    7.96875    8.75       8.1875     7.46875    8.6875    8.375     8.5

Xoroshiro32ppg 1.5    10.375    6.5        7.34375    8.59375    8.03125    7.875      8.25      8.0625    7.59375

Here are the standard (+) and Gray modified (+g) escape-from-zero values for comparison:

Xoroshiro32+    1      3.1875   5.125      8.28125    7.59375    7.625      8.34375    8.40625   8         7.625    
Xoroshiro32+g   1     13.375    7.84375    8.3125     8          8          8.03125    8.15625   8.09375   8.53125    

C++ Code (based on original Parallax example source, still containing both their comments and mine):   

// Xoroshiro32ppg (variation of XoroshiroPlusPlus from Vigna/Blackman), by CRutz, free for all uses

#include <stdint.h>

#define  ACCUM_SIZE  16
#define  CONSTANT_A  5
#define  CONSTANT_B  1 // 1 is required for inverted Gray Code modification below
#define  CONSTANT_C  14
#define  CONSTANT_D  9 // 9 seems optimal when the underlying x/y distribution is optimal and correlation is minimized

typedef  uint16_t  rngword_t;

static inline rngword_t  rotl( rngword_t value, int shift )  {
        return (value << shift) | (value >> (ACCUM_SIZE - shift));
}

// Seed the state array.  Seed MUST not be all zero. THIS IS WRONG... NEED TO FIND SEED CORRECTIONS!!! 
static rngword_t  s[2] = {1, 0};

static rngword_t  nextxoro( void )
{
        rngword_t  s0 = s[0];
        rngword_t  s1 = s[1];
        rngword_t  result = s0 + s1;  // output hash (scrambler) for Xoroshiro+
//New addition from authors:  Rotation and second summing
        result = rotl( result, CONSTANT_D ) + s0; // NEED TO FIND OUTPUT CORRECTION TO RESTORE MISSING ZERO!!!

        s1 ^= s0;
        s[0] = rotl( s0, CONSTANT_A ) ^ ~s1 ^ (s1 >> CONSTANT_B); // Note '~s1' is equivalent to '0xffff ^ s1', and '~s1 ^ (s1 >> 1)' forms an inverted Gray Code; SHIFT DIRECTION MAY NOT BE OPTIMAL
        s[1] = rotl( s1, CONSTANT_C );

        return( result );
}