C# PRNG class based on xoshiro256**

Question

Background

I'm creating a (probably bad) map-generation utility in C# to generate fractal terrain and similar. Nothing I do probably needs special treatment, but I thought it best to start with a good source of random values.

My understanding is that C# only has two built-in sources of random numbers:

1. System.Security.Cryptography.RandomNumberGenerator
2. System.Random

The problem with (1) is there's no way to manually seed the state, meaning each map is completely random, instead of being able to perfectly recreate a previous map at the earlier stages, then change variables at later stages for subtle differences. It also prevents easily sharing a map using seed values. (Conflicting literature also makes me unsure if that source even uses PRNG algorithms or is entirely hardware RNG.)

The problem with (2) is that it isn't very random. I've read it actually uses the xoshiro256 algorithm if you don't seed it, but not if you manually seed it. I believe it's also 32-bit by design, which is probably fine, but might be problematic with large map sizes.

The second case also has the potential problem that (should my program ever see the light of day) different implementations might not produce the same sequence, even given the same seed values.

So I decided to create a 64-bit implementation of xoshiro256**. This is supposed to give good randomness with a large state (256 bits, as the name implies), be quite fast, and, since all the math is contained in my class, 100% reproducible across platforms. It also allows me to use it in other programs where similar constraints might be at play.

I found some code on GitHub that's clearly based on the original C code from the author's site. Then I converted it from static functions to a proper class, explicitly set ulong types to UInt64, and wrote my own public interface methods.

How It Works

The external interface consists of two constructors. The first uses the existing Cryptography class to generate a nice, random seed so subsequent calls should create different sequences. The second uses a supplied seed so calling functions can replicate earlier sequences.

There are several functions that convert the next 64-bit output to usable numbers, and update the state variable so it's ready for the subsequent calls. NextUInt64 just uses the existing function's output, NextUInt32 grabs the top 32 bits of the output, NextBytes converts the 64-bit output to an 8-byte array, and NextDouble converts the output to a float between 0 and 1.

Nothing super fancy, and basic testing shows subsequent runs with the default constructor give different outputs, as expected. Manually specifying a number of different seeds gives identical output on subsequent runs of each seed, as expected. Back-to-back calls of new MyRandom() on different instances generate different runs, confirming the Cryptography.RandomNumberGenerator instantiation is giving unique seeds, even in close temporal proximity, unlike the default Random class.

Potential Problems

1. My first concern is at lines 73 and 74, in the function xorshift256_init. The original code I found called splitmix64 on the uninitialized (presumably all-zero) array elements result[2] and result[3], then assigned those results into the same array elements. I modified it so result[2] gets a mixed result[1], then result[3] gets a mixed result[2], which made sense to me, but maybe I'm just dumb.

Old code:

private void xorshift256_init(UInt64 seed)
{
    UInt64[] result = new UInt64[4];
    result[0] = splitmix64(seed);
    result[1] = splitmix64(result[0]);
    result[2] = splitmix64(result[2]);  // Seems wrong.
    result[3] = splitmix64(result[3]);  // Again seems wrong.
    this.state = result;
}

My code:

private void xorshift256_init(UInt64 seed)
{
    UInt64[] result = new UInt64[4];
    result[0] = splitmix64(seed);
    result[1] = splitmix64(result[0]);
    result[2] = splitmix64(result[1]);  // Seem right.
    result[3] = splitmix64(result[2]);  // Again seems right.
    this.state = result;
}

2. The second concern is my NextDouble function. I can't find any place that actually gives me the exact range of possible values of the xoshiro256p function (the function is called next in the original C implementation). Typically, I would use the NextDouble function to generate an integer range between A and B with something like this:

    int diff = B - A;
    return Math.Floor(A + rand.NextDouble * (diff+1) );
   

As long as NextDouble is guaranteed to be less than 1, that code gives me a very even distribution of values. But if NextDouble could return exactly 1, there's a (very small) chance I could end up returning B+1, which is undesirable.

If the output of xoshiro256p excludes 0, but includes UInt64.MaxValue, I could just subtract 1 first. If it excludes both, I can just leave it (any error from excluding 0 is very small and doesn't notably affect my use cases). If it includes both, I could just do a test and set the output to 0 if the output is exactly 1 (or try to divide by UInt64.MaxValue+1 somehow to avoid this, but that's probably overly complex for no good reason).

But without knowing the exact minimum and maximum values of the original algorithm, I'm not sure the best way to ensure compliance with the intended range.

3. I'm not sure BitConverter is cross-platform compliant. I feel like it probably is, since everything should be using the same integer standards, floating point specifications, etc.

My biggest concern here is Endianness of the platform. Do I need to start at index 4 when converting to UInt32 on a little Endian platform and start at index 0 on a big Endian platform (or vice versa)?

Similarly, would it be best to check Endianness, then reverse the byte order in one case? Then NextBytes always returns bytes in the same order regardless of platform, so any function using those bytes will get the same result regardless of platform?

The Code

using System;
using System.Security.Cryptography;

namespace MapGenerator
{

    /// <summary>
    /// A random number generator using xoshiro256** algorithms.
    /// Based on code from GitHub: https://gist.github.com/i-e-b/a585fc2b9cea1e3d6221451529597145
    /// Itself from a Wikipedia description of the original C code: https://prng.di.unimi.it/xoshiro256starstar.c
    /// </summary>
    class MyRandom
    {
        
        private UInt64[] state;  /// The current state of the generator, from which new bytes are generated.
        

        /// <summary>
        /// Seed the instance with a cryptographically-secure seed from the operating system for hard-to-guess sequences of pseudo-random numbers.
        /// </summary>
        public MyRandom()
        {
            // Use the cryptography class to generate a good, random seed (ultimately from the OS's implementation of hardware seeding).
            RandomNumberGenerator rand = RandomNumberGenerator.Create();

            // Pull the next 64 bits (8 bytes) into an array.
            byte[] randBytes = new byte[8];
            rand.GetBytes(randBytes, 0, 8);

            // Convert the 64 bits into a single 64-bit unsigned int and return it.
            UInt64 seed = BitConverter.ToUInt64(randBytes, 0);

            // Initialize state using the generated seed. 
            xorshift256_init(seed);
        }

        /// <summary>
        /// Seed the class with a known seed to reproduce previous sequences of pseudo-random numbers.
        /// </summary>
        /// <param name="seed">A 64-bit seed with which to seed this instance of the class.</param>
        public MyRandom(UInt64 seed)
        {
            // Initialize state using the provided value. 
            xorshift256_init(seed);
        }

        /// <summary>
        /// Helper function for xorshift256_init, mixes up seed values to get a pseudo-random starting state.
        /// </summary>
        /// <param name="partialstate">The state portion to splitmix.</param>
        /// <returns>The splitmixed state portion.</returns>
        private UInt64 splitmix64(UInt64 partialstate)
        {
            partialstate = partialstate + 0x9E3779B97f4A7C15;
            partialstate = (partialstate ^ (partialstate >> 30)) * 0xBF58476D1CE4E5B9;
            partialstate = (partialstate ^ (partialstate >> 27)) * 0x94D049BB133111EB;
            return partialstate ^ (partialstate >> 31);
        }

        /// <summary>
        /// Initialize the generator's state with the given seed value.
        /// </summary>
        /// <param name="seed">A 64-bit seed with which to seed this instance of the class.</param>
        private void xorshift256_init(UInt64 seed)
        {
            UInt64[] result = new UInt64[4];
            result[0] = splitmix64(seed);
            result[1] = splitmix64(result[0]);
            result[2] = splitmix64(result[1]);  // Was result[2] = splitmix64(result[2]), which seemed wrong.
            result[3] = splitmix64(result[2]);  // Was result[3] = splitmix64(result[3]), which again seemed wrong.
            this.state = result;
        }

        /// <summary>
        /// Helper function for xoshiro256p, rotates some bits around.
        /// </summary>
        /// <param name="x">The state portion being modified.</param>
        /// <param name="k">The number of bits to shift around.</param>
        /// <returns>The modified state portion.</returns>
        private UInt64 rotl64(UInt64 x, int k)
        {
            return (x << k) | (x >> (64 - k));
        }

        /// <summary>
        /// Generates the next 64-bit integer in the sequence, then updates the state to be ready for another call.
        /// </summary>
        /// <returns>The next 64-bit integer in the sequence.</returns>
        private UInt64 xoshiro256p()
        {
            UInt64 result = rotl64(this.state[1] * 5, 7) * 9;
            UInt64 t = this.state[1] << 17;

            this.state[2] ^= this.state[0];
            this.state[3] ^= this.state[1];
            this.state[1] ^= this.state[2];
            this.state[0] ^= this.state[3];

            this.state[2] ^= t;
            this.state[3] = rotl64(this.state[3], 45);

            return result;
        }

        /// <summary>
        /// Get the next value in the sequence as an array of 8 bytes.
        /// </summary>
        /// <returns>The next 8 bytes in the sequence.</returns>
        public byte[] NextBytes()
        {
            UInt64 nextInt64 = xoshiro256p();

            // Get and return the bytes of the 64-bit value (there will be 8 bytes).
            return BitConverter.GetBytes(nextInt64);
        }

        /// <summary>
        /// Get the next value in the sequence as a 64-bit unsigned integer.
        /// </summary>
        /// <returns>The next 64-bit unsigned integer in the sequence.</returns>
        public UInt64 NextUInt64()
        {
            return xoshiro256p();
        }

        /// <summary>
        /// Get the next value in the sequence as a 32-bit unsigned integer.
        /// </summary>
        /// <returns>The next 32-bit unsigned integer in the sequence.</returns>
        public UInt32 NextUInt32()
        {
            // Get the next 8 bytes in the sequence.
            byte[] randBytes = NextBytes();
            
            // Use the first 4 bytes to generate and return a 32-bit value.
            return BitConverter.ToUInt32(randBytes, 0);

        }

        /// <summary>
        /// Get the next value in the sequence as a double-precision floating point number in the range [0, 1).
        /// </summary>
        /// <returns>The next number in the sequence, constrained to the range [0, 1). Low bound is inclusive, upper bound is exclusive.</returns>
        public Double NextDouble()
        {
            // Get the next UInt64.
            UInt64 nextInt64 = xoshiro256p();

            // Divide the generated integer by a slightly larger value to guarantee the result includes 0 but not 1.
            return (double)nextInt64 / (double)(UInt64.MaxValue);

        }

    }

}

Answer 1

The corrections applied to xorshift256_init totally make sense. Otherwise half the internal state would always be the same, regardless what seed is used.

In xoshiro256p you can remove the all the this.. They are not needed and don't help for clarity.

I would also rename xosiro256p to xoshiro256ss to follow the sources we can find on https://en.wikipedia.org/wiki/Xorshift.

"xoshiro256p" stands for (Plus) xoshiro256+

"xoshiro256ss" stands for (Star Star), xoshiro256**

        private UInt64 xoshiro256ss()
        {
            UInt64 result = rotl64(state[1] * 5, 7) * 9;
            UInt64 t = state[1] << 17;

            state[2] ^= state[0];
            state[3] ^= state[1];
            state[1] ^= state[2];
            state[0] ^= state[3];

            state[2] ^= t;
            state[3] = rotl64(state[3], 45);

            return result;
        }