6
\$\begingroup\$

I took the basic structure from this link and wrote the following class.

Can you review the code?

Can you find a silent bug?

using System;

namespace Lib
{
    /// <summary>
    /// A PCG-based random number generator that is interchangeable with System.Random.
    /// </summary>
    public sealed class Pcg32Rng : Random
    {
        public ulong Seed { get; private set; }
        public ulong Increment { get; }

        /// <summary>
        /// Initializes a new instance of the <see cref="Pcg32Rng"/> class with a default seed.
        /// </summary>
        public Pcg32Rng() : this((ulong)Environment.TickCount) { }

        /// <summary>
        /// Initializes a new instance of the <see cref="Pcg32Rng"/> class with a specified seed and stream ID.
        /// </summary>
        /// <param name="seed">State initializer (a.k.a. seed).</param>
        /// <param name="streamID">Sequence selection constant (a.k.a. stream ID). Defaults to 0.</param>
        public Pcg32Rng(ulong seed, ulong streamID = 0)
        {
            Seed = 0ul;
            Increment = (streamID << 1) | 1ul;
            PCG32();
            Seed += seed;
            PCG32();
        }

        public Pcg32Rng(ulong seed, ulong increment, bool dummy)
        {
            Seed = seed;
            Increment = increment;
        }

        /// <summary>
        /// Generates a uniformly distributed 32-bit unsigned integer.
        /// </summary>
        /// <returns>A uniformly distributed 32-bit unsigned integer.</returns>
        private uint PCG32()
        {
            ulong oldState = Seed;
            Seed = unchecked(Seed * 6364136223846793005ul + Increment);
            uint xorshifted = (uint)(((oldState >> 18) ^ oldState) >> 27);
            int rot = (int)(oldState >> 59);
            return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
        }

        /// <summary>
        /// Generates a uniformly distributed 32-bit unsigned integer less than the specified bound.
        /// </summary>
        /// <param name="bound">Exclusive upper bound.</param>
        /// <returns>A uniformly distributed 32-bit unsigned integer strictly less than <paramref name="bound"/>.</returns>
        private uint PCG32(uint bound)
        {
            uint threshold = ((uint)-bound) % bound;

            while (true)
            {
                uint r = PCG32();
                if (r >= threshold)
                    return r % bound;
            }
        }

        /// <inheritdoc />
        public override int Next()
        {
            return Next(int.MaxValue);
        }

        /// <inheritdoc />
        public override int Next(int maxValue)
        {
            if (maxValue <= 0)
                throw new ArgumentOutOfRangeException(nameof(maxValue), "maxValue must be greater than 0.");
            return (int)PCG32((uint)maxValue);
        }

        /// <inheritdoc />
        public override int Next(int minValue, int maxValue)
        {
            if (minValue > maxValue)
                throw new ArgumentOutOfRangeException(nameof(minValue), "minValue must be less than or equal to maxValue.");

            long range = (long)maxValue - minValue;
            return (int)(minValue + PCG32((uint)range));
        }

        /// <inheritdoc />
        protected override double Sample()
        {
            // Generate a random double in the range [0, 1).
            return PCG32() * (1.0 / uint.MaxValue);
        }

        /// <inheritdoc />
        public override double NextDouble()
        {
            return Sample();
        }

        /// <inheritdoc />
        public override void NextBytes(byte[] buffer)
        {
            if (buffer == null) throw new ArgumentNullException(nameof(buffer));

            for (int i = 0; i < buffer.Length; i++)
            {
                buffer[i] = (byte)PCG32();
            }
        }
    }
}

\$\endgroup\$

1 Answer 1

6
\$\begingroup\$

Issues in checked mode

I noticed the use of the unchecked keyword here, unchecked(Seed * 6364136223846793005ul + Increment) so it seems that the code is intended to work in checked mode. There are a couple of problems though:

(uint)(((oldState >> 18) ^ oldState) >> 27)

The cast to uint can spuriously fail in checked mode. It's obviously intended to simply truncate so an unchecked cast is appropriate.

((uint)-bound) % bound

Again the cast to uint can spuriously fair in checked mode. It's not as obvious, but I know what you're doing and an unchecked cast is appropriate here as well. Alternatively you could write (0u - bound) % bound, subtracting from zero doesn't implicitly convert to long.

(byte)PCG32()

Same issue, an unchecked cast is appropriate. By the way if you want, you could also reduce the number of PCG32 calls here by a factor of 4 by splitting the result over 4 bytes.

Normally I don't expect code to work in checked mode to begin with, but the explicit use of the unchecked keyword makes it look like it is intended to work. If it's not intended, then that unchecked keyword is redundant.

NextDouble can return exactly 1.0

The comment and the code here are not consistent:

    // Generate a random double in the range [0, 1).
    return PCG32() * (1.0 / uint.MaxValue);

Although rare, PCG32() can return 0xffffffff aka uint.MaxValue and it turns out that uint.MaxValue * (1.0 / uint.MaxValue) == 1.0 (that's not completely trivial because of the floating point rounding that's going on, but does work out that way). You could multiply by 1.0 / (1L << 32) to avoid that.

Bonus

The rotate (xorshifted >> rot) | (xorshifted << ((-rot) & 31)) is from the original C (or is it C++?) code and C doesn't have direct access to bitwise rotates until C23 (so much for being a low level language) (admittedly there are various platform-specific intrinsics), in modern C# you can write BitOperations.RotateRight(xorshifted, rot). That's nicer, right? Also fewer instructions for now (until the JIT compiler learns about this pattern), as seen on sharplab.io we have:

L002f: shrx ecx, eax, edx
L0034: neg edx
L0036: shlx eax, eax, edx
L003b: or eax, ecx

vs

L0032: ror eax, cl

But whether that's actually better, it's not trivial. There are various µarch specific details to consider.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.