C# Am I doing "Bays & Durham Randomization by Shuffling" correctly?

Question

I tried to improvise a random number generator by using the "Bays & Durham Randomization by Shuffling" algorithm. I followed a tutorial online and made this code:

 public int[] GenerateRandomSequence_Improved(int n, int min, int max)
 {
       int[] seq = new int[n];
       for(int i = 0; i < n; i++)
       {
           int rand = GenerateNextRandomNumber(min, max);

           rand = min + rand % (max + 1 - min);
           seq[i] = rand;
       }
       return seq;
 }

I wanna know if I did it correctly or not..

EDIT: This is the code for the GenerateNextRandomNumber method

public int GenerateNextRandomNumber(int min, int max)
{
       return cSharpRNG.Next(min,max);
}

I think `rand = min + rand % (max + 1 - min);` is not necessary, as [Random.Next(Int32, Int32)](https://learn.microsoft.com/en-us/dotnet/api/system.random.next?view=netframework-4.8#System_Random_Next_System_Int32_System_Int32_) already returns a value in the requested range. (lower bound inclusive, upper bound exclusive). And I don't see any shuffling. You're just initializing the array with random numbers. — Olivier Jacot-Descombes, Jun 01 '19 at 15:45

score 1 · Answer 1 · answered Jun 02 '19 at 02:16

Here is what I believe proper implementation of the Bays-Durham shuffling. Warning wrt bias in indexing due to modulo operation is right though.

.NET Core 2.2, x64 Win10

using System;
using System.Diagnostics;

namespace BaysDurhamShuffling
{
    public class BaysDurhamRNG
    {
        public int[] _table;
        public int   _xnext;

        public Random _rng = null;

        public BaysDurhamRNG(int n, int seed = 312357) {
            Debug.Assert(n > 1);

            _rng = new Random(seed);
            _table = new int [n];
            for(int k = 0; k != n; ++k) {
                _table[k] = _rng.Next();
            }
            _xnext = _rng.Next();
        }

        public int next() {
            var x = _xnext; // store return value

            var j  = _xnext % _table.Length; // form the index j into the table
            _xnext = _table[j];              // get jth element of table and to copy it to the output stream on next call
            _table[j] = _rng.Next();         // replace jth element of table with next random value from input stream

            return x; // return what was stored in next value
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var rng = new BaysDurhamRNG (16, 12345);

            for(int k = 0; k != 30; ++k) {
                var x = rng.next();
                Console.WriteLine($"RV = {x}");
            }
        }
    }
}

Samuel Vidal · Accepted Answer · 2019-06-03T19:56:58.020

According to Knuth TAOCP Vol. 2 p. 34 Algorithm B, the proper algorithm is the following,

public class BaysDurham
{
    private readonly int[] t;
    private int y;      // auxiliary variable

    // Knuth TAOCP Vol. 2 p. 34 Algorithm B

    public BaysDurham(int k)
    {
        t = new int[k];

        for (int i = 0; i < k; i++)
        {
            t[i] = rand.Next();
        }

        y = rand.Next();
    }

    public int Next()
    {
        var i = (int)((t.Length * (long) y) / int.MaxValue);   // mitigates the bias
        y = t[i];
        t[i] = rand.Next();
        return y;
    }

    private readonly Random rand = new Random();
}

I let you adapt the range of the output, but just know that the formula you use with the modulo introduce significant bias and makes the distribution non-uniform please look at this.

C# Am I doing "Bays & Durham Randomization by Shuffling" correctly?

2 Answers2