Batched random for the CSPRNG (and System.Random)

Background and motivation

When generating many small random numbers, it is more efficient to generate them in one bulk operation. The most obvious example would be 8 coin-flips can be generated from just one random byte.

Several algorithms exist for extracting multiple bounded integers from a pull of an RNG, without sacrificing a loss of entropy. For example, if one needs two integers in the range [0, 6), they independently compose to a single integer in the range [0, 12). These algorithms can significantly speed up throughput on systems with a slow random number generator.

API Proposal

namespace System.Security.Cryptography
{
    // Batched random
    public partial class RandomNumberGenerator
    {
        // Fill a homogeneous set of bounded integers.
        // Target: RNG.GetItems, dice roll simulations.
        public static void FillInt32(int toExclusive, Span<int> destination);
        public static void FillInt32(int fromInclusive, int toExclusive, Span<int> destination);
        public static void FillUInt32(uint toExclusive, Span<uint> destination);
        
        // Fill a heterogeneous set of bounded integers.
        // Target: Fisher-Yates Shuffle
        public static void FillUInt32(ReadOnlySpan<uint> toExclusives, Span<uint> destination);

        // Fully squaring off the feature:
        // T: Int32, UInt32, Int64, UInt64
        // public static void FillT(T toExclusive, Span<T> destination);
        // public static void FillT(T fromInclusive, T toExclusive, Span<T> destination);
        // public static void FillT(ReadOnlySpan<T> toExclusives, Span<T> destination);
        // public static void FillT(ReadOnlySpan<T> fromInclusives, ReadOnlySpan<T> toExclusives, Span<T> destination);

        public static void FillUInt32(uint fromInclusive, uint toExclusive, Span<uint> destination);
        public static void FillInt64(long toExclusive, Span<long> destination);
        public static void FillInt64(long fromInclusive, long toExclusive, Span<long> destination);
        public static void FillUInt64(ulong toExclusive, Span<ulong> destination);
        public static void FillUInt64(ulong fromInclusive, ulong toExclusive, Span<ulong> destination);
        public static void FillUInt32(ReadOnlySpan<uint> fromInclusives, ReadOnlySpan<uint> toExclusives, Span<uint> destination);
        public static void FillInt32(ReadOnlySpan<int> toExclusives, Span<int> destination);
        public static void FillInt32(ReadOnlySpan<int> fromInclusives, ReadOnlySpan<int> toExclusives, Span<uint> destination);
        public static void FillInt64(ReadOnlySpan<long> toExclusives, Span<long> destination);
        public static void FillInt64(ReadOnlySpan<long> fromInclusives, ReadOnlySpan<long> toExclusives, Span<long> destination);
        public static void FillUInt64(ReadOnlySpan<ulong> toExclusives, Span<ulong> destination);
        public static void FillUInt64(ReadOnlySpan<ulong> fromInclusives, ReadOnlySpan<ulong> toExclusives, Span<ulong> destination);
    }
    
    // Helper routines that would have made investigating this space easier
    public partial class RandomNumberGenerator
    {
        public static ulong GetUInt64();
        public static ulong GetUInt64(uint toExclusive);
    
        // The rest of these are "squaring the circle"
    
        public static int GetInt32();
    
        public static uint GetUInt32();
        public static uint GetUInt32(uint toExclusive);
        public static uint GetUInt32(uint fromInclusive, uint toExclusive);
    
        public static long GetInt64();
        public static long GetInt64(long toExclusive);
        public static long GetInt64(long fromInclusive, long toExclusive);
    
        public static ulong GetUInt64(uint fromInclusive, uint toExclusive);
    }
}

namespace System
{
    public partial class Random
    {
        // Only one exception case: toExclusive == 0
        public virtual void NextBatchUInt32(uint toExclusive, Span<uint> destination);
        // Only one exception case: toExclusives.Any(x => x == 0);
        public virtual void NextBatchUInt32(ReadOnlySpan<uint> toExclusives, Span<uint> destination);

        // Non-virtual, implemented in terms of NextBatchUInt32
        public void NextBatch(int toExclusive, Span<int> destination);
        public void NextBatch(int fromInclusive, int toExclusive, Span<int> destination);

        // squaring off
        public void NextBatchUInt32(uint fromInclusive, uint toExclusive, Span<uint> destination);
        public void NextBatchUInt32(ReadOnlySpan<uint> fromInclusives, ReadOnlySpan<uint> toExclusives, Span<uint> destination);
        public void NextBatchInt32(ReadOnlySpan<int> toExclusives, Span<int> destination);
        public void NextBatchInt32(ReadOnlySpan<int> fromInclusives, ReadOnlySpan<int> toExclusives, Span<int> destination);
        public void NextBatchInt64(long toExclusive, Span<long> destination);
        public void NextBatchInt64(long fromInclusive, long toExclusive, Span<long> destination);
        public void NextBatchInt64(ReadOnlySpan<long> toExclusives, Span<long> destination);
        public void NextBatchInt64(ReadOnlySpan<long> fromInclusives, ReadOnlySpan<long> toExclusives, Span<long> destination);
        public virtual void NextBatchUInt64(ulong toExclusive, Span<ulong> destination);
        public void NextBatchUInt64(ulong fromInclusive, ulong toExclusive, Span<ulong> destination);
        public virtual void NextBatchUInt64(ReadOnlySpan<ulong> toExclusives, Span<ulong> destination);
        public void NextBatchUInt64(ReadOnlySpan<ulong> fromInclusives, ReadOnlySpan<ulong> toExclusives, Span<ulong> destination);
    }
}

API Usage

int[] dice = new int[5];
RandomNumberGenerator.FillInt32(6, dice);

for (int i = 0; i < 6; i++)
{
   if (dice.All(die => die == i))
   {
       return "Yahtzee!";
   }
}

Alternative Designs

• FillInt32 and friends can be int returning instead of void, to indicate how many items they processed in a single batch.
  • For the virtuals on System.Random we might want to encapsulate that with the template method pattern to ensure they don't return negative, or zero.