A fast random generator in c#

Question

I need random numbers for procedural terrains etc. in a game. The game is based on the seed. I was told not to rely on the .NET frameworks Random class because the implementation may change and the seed may result in other values in other versions. (This already happened... .NET 1.1 has a different implementation)

The most Random alternatives out there are for cryptography where the focus relies on very good numbers instead of performance.

So what I look for is a very fast seed based pseudo random number generator that is independent from .NET versions, with average quality randomness.

Answer 1

Don't re-invent the wheel. Borrow/steal what works:

• Decompiled .NET implemlementation of the Random class
• Mono source for Random
• Java source for Random (Slightly riskier since it would require porting to .NET and therefore some code changes that have not been tested in the wild a million times over.)

Just use one of the existing, decompiled implementations and fold it into your own library to make sure it doesn't change:

using System;
using System.Runtime;
using System.Runtime.InteropServices;
namespace System
{
    /// <summary>Represents a pseudo-random number generator, a device that produces a sequence of numbers that meet certain statistical requirements for randomness.</summary>
    /// <filterpriority>1</filterpriority>
    [ComVisible(true)]
    [Serializable]
    public class Random
    {
        private const int MBIG = 2147483647;
        private const int MSEED = 161803398;
        private const int MZ = 0;
        private int inext;
        private int inextp;
        private int[] SeedArray = new int[56];
        /// <summary>Initializes a new instance of the <see cref="T:System.Random" /> class, using a time-dependent default seed value.</summary>
        public Random() : this(Environment.TickCount)
        {
        }
        /// <summary>Initializes a new instance of the <see cref="T:System.Random" /> class, using the specified seed value.</summary>
        /// <param name="Seed">A number used to calculate a starting value for the pseudo-random number sequence. If a negative number is specified, the absolute value of the number is used. </param>
        public Random(int Seed)
        {
            int num = (Seed == -2147483648) ? 2147483647 : Math.Abs(Seed);
            int num2 = 161803398 - num;
            this.SeedArray[55] = num2;
            int num3 = 1;
            for (int i = 1; i < 55; i++)
            {
                int num4 = 21 * i % 55;
                this.SeedArray[num4] = num3;
                num3 = num2 - num3;
                if (num3 < 0)
                {
                    num3 += 2147483647;
                }
                num2 = this.SeedArray[num4];
            }
            for (int j = 1; j < 5; j++)
            {
                for (int k = 1; k < 56; k++)
                {
                    this.SeedArray[k] -= this.SeedArray[1 + (k + 30) % 55];
                    if (this.SeedArray[k] < 0)
                    {
                        this.SeedArray[k] += 2147483647;
                    }
                }
            }
            this.inext = 0;
            this.inextp = 21;
            Seed = 1;
        }
        /// <summary>Returns a random number between 0.0 and 1.0.</summary>
        /// <returns>A double-precision floating point number greater than or equal to 0.0, and less than 1.0.</returns>
        [TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
        protected virtual double Sample()
        {
            return (double)this.InternalSample() * 4.6566128752457969E-10;
        }
        private int InternalSample()
        {
            int num = this.inext;
            int num2 = this.inextp;
            if (++num >= 56)
            {
                num = 1;
            }
            if (++num2 >= 56)
            {
                num2 = 1;
            }
            int num3 = this.SeedArray[num] - this.SeedArray[num2];
            if (num3 == 2147483647)
            {
                num3--;
            }
            if (num3 < 0)
            {
                num3 += 2147483647;
            }
            this.SeedArray[num] = num3;
            this.inext = num;
            this.inextp = num2;
            return num3;
        }
        /// <summary>Returns a nonnegative random number.</summary>
        /// <returns>A 32-bit signed integer greater than or equal to zero and less than <see cref="F:System.Int32.MaxValue" />.</>/returns>
        /// <filterpriority>1</filterpriority>
        [TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
        public virtual int Next()
        {
            return this.InternalSample();
        }
        private double GetSampleForLargeRange()
        {
            int num = this.InternalSample();
            bool flag = this.InternalSample() % 2 == 0;
            if (flag)
            {
                num = -num;
            }
            double num2 = (double)num;
            num2 += 2147483646.0;
            return num2 / 4294967293.0;
        }
        /// <summary>Returns a random number within a specified range.</summary>
        /// <returns>A 32-bit signed integer greater than or equal to <paramref name="minValue" /> and less than <paramref name="maxValue" />; that is, the range of return values includes <paramref name="minValue" /> but not <paramref name="maxValue" />. If <paramref name="minValue" /> equals <paramref name="maxValue" />, <paramref name="minValue" /> is returned.</returns>
        /// <param name="minValue">The inclusive lower bound of the random number returned. </param>
        /// <param name="maxValue">The exclusive upper bound of the random number returned. <paramref name="maxValue" /> must be greater than or equal to <paramref name="minValue" />. </param>
        /// <exception cref="T:System.ArgumentOutOfRangeException">
        ///   <paramref name="minValue" /> is greater than <paramref name="maxValue" />. </exception>
        /// <filterpriority>1</filterpriority>
        public virtual int Next(int minValue, int maxValue)
        {
            if (minValue > maxValue)
            {
                throw new ArgumentOutOfRangeException("minValue", Environment.GetResourceString("Argument_MinMaxValue", new object[]
                {
                    "minValue", 
                    "maxValue"
                }));
            }
            long num = (long)maxValue - (long)minValue;
            if (num <= 2147483647L)
            {
                return (int)(this.Sample() * (double)num) + minValue;
            }
            return (int)((long)(this.GetSampleForLargeRange() * (double)num) + (long)minValue);
        }
        /// <summary>Returns a nonnegative random number less than the specified maximum.</summary>
        /// <returns>A 32-bit signed integer greater than or equal to zero, and less than <paramref name="maxValue" />; that is, the range of return values ordinarily includes zero but not <paramref name="maxValue" />. However, if <paramref name="maxValue" /> equals zero, <paramref name="maxValue" /> is returned.</returns>
        /// <param name="maxValue">The exclusive upper bound of the random number to be generated. <paramref name="maxValue" /> must be greater than or equal to zero. </param>
        /// <exception cref="T:System.ArgumentOutOfRangeException">
        ///   <paramref name="maxValue" /> is less than zero. </exception>
        /// <filterpriority>1</filterpriority>
        public virtual int Next(int maxValue)
        {
            if (maxValue < 0)
            {
                throw new ArgumentOutOfRangeException("maxValue", Environment.GetResourceString("ArgumentOutOfRange_MustBePositive", new object[]
                {
                    "maxValue"
                }));
            }
            return (int)(this.Sample() * (double)maxValue);
        }
        /// <summary>Returns a random number between 0.0 and 1.0.</summary>
        /// <returns>A double-precision floating point number greater than or equal to 0.0, and less than 1.0.</returns>
        /// <filterpriority>1</filterpriority>
        [TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
        public virtual double NextDouble()
        {
            return this.Sample();
        }
        /// <summary>Fills the elements of a specified array of bytes with random numbers.</summary>
        /// <param name="buffer">An array of bytes to contain random numbers. </param>
        /// <exception cref="T:System.ArgumentNullException">
        ///   <paramref name="buffer" /> is null. </exception>
        /// <filterpriority>1</filterpriority>
        public virtual void NextBytes(byte[] buffer)
        {
            if (buffer == null)
            {
                throw new ArgumentNullException("buffer");
            }
            for (int i = 0; i < buffer.Length; i++)
            {
                buffer[i] = (byte)(this.InternalSample() % 256);
            }
        }
    }
}

Answer 2

Standard Random (or your own copy of) might be OK for terrains and many things, but you need to be careful with some games that you use a generator that produces enough randomness.

Take a pack of cards, if you use a 32 bit generator, it can only produce 4 billion first pack (see below) permutations (2^32). However there are actually 52! (factorial that is) possible, which is 8x10^67. That requires a 226 bit number.

So sometimes it can be necessary to use a cryptographic generator.

Why does this apply to the first pack only?

I had made an assumption about the seed for next number being simply the 32 bit value returned last. I've looked at the code now and internally the seed is a far higher bit count. The 32 bit external seed value you give it is only used as a way to generate a starting point for the larger seed. It maintains and modifies this internal seed, while producing random values. What this all means is that yes there are only 4 billion sequences, but those sequences are unique, they don't overlap the way I assumed. This means there can only be 4 billion packs initially, but more can follow.