Generation of (pseudo) random constrained values of (U)Int64 and Decimal

Question

Note: For brevity's sake, the following will not discern between randomness and pseudo-randomness. Also, in this context, 'constrained' means 'between given min and max values')

The System.Random class provides random generation of integers, doubles and byte arrays. Using Random.Next, one can easily generate random constrained values of type Boolean, Char, (S)Byte, (U)Int16, (U)Int32. Using Random.NextDouble(), one can similarly generate constrained values of types Double and Single (as far as my understanding of this type goes). Random string generation (of a given length and alphabet) has also been tackled before.

Consider the remaining primitive data types (excluding Object): Decimal and (U)Int64. Their random generation has been tackled as well (Decimal, (U)Int64 [using Random.NextBytes()]), but not when constrained. Rejection sampling (i.e. looping until the generated value is the the desired range) could theoretically be used, but it is obviously not a practical solution. Normalizing NextDouble() won't work because it doesn't have enough significant digits.

In short, I am asking for the proper implementation of the following functions:

long NextLong(long min, long max)
long NextDecimal(decimal min, decimal max)

Note that, since System.DateTime is based on a ulong, the first function would allow for random constrained generation of such structs as well (similar to here, only in ticks instead of minutes).

Thanks in advance!

Answer 1

Let's assume you know how to generate N random bits. This is pretty easily done either using NextBytes or repeated calls to Random.Next with appropriate limits.

To generate a long/ulong in the right range, work out how large the range is, and how many bits it takes to represent it. You can then use rejection sampling which will at worst reject half the generated values (e.g. if you want a value in the range [0, 128], which means you'll generate [0, 255] multiple times). If you want a non-zero based range, just work out the size of the range, generate a random value in [0, size) and then add the base.

Generating a random decimal is signficantly harder, I believe - aside from anything else, you'd have to specify the distribution you wanted.

Answer 2

This should do it. For decimal I utilized Jon Skeet's initial approach to generating random decimals (no constraints). For long I provided a method to produced random non-negative longs which is then used to create the a value in the random range.

Note that for decimal the resulting distribution is not a uniform distribution on [minValue, maxValue]. It merely is uniform on all the bit representations of decimals that fall in the range [minValue, maxValue]. I do not see an easy way around this without using rejection sampling.

For long the resulting distribution is uniform on [minValue, maxValue).

static class RandomExtensions {
    static int NextInt32(this Random rg) {
        unchecked {
            int firstBits = rg.Next(0, 1 << 4) << 28;
            int lastBits = rg.Next(0, 1 << 28);
            return firstBits | lastBits;
        }
    }

    public static decimal NextDecimal(this Random rg) {
        bool sign = rg.Next(2) == 1;
        return rg.NextDecimal(sign);
    }

    static decimal NextDecimal(this Random rg, bool sign) {
        byte scale = (byte)rg.Next(29);
        return new decimal(rg.NextInt32(),
                           rg.NextInt32(),
                           rg.NextInt32(),
                           sign,
                           scale);
    }

    static decimal NextNonNegativeDecimal(this Random rg) {
        return rg.NextDecimal(false);
    }

    public static decimal NextDecimal(this Random rg, decimal maxValue) {
        return (rg.NextNonNegativeDecimal() / Decimal.MaxValue) * maxValue; ;
    }

    public static decimal NextDecimal(this Random rg, decimal minValue, decimal maxValue) {
        if (minValue >= maxValue) {
            throw new InvalidOperationException();
        }
        decimal range = maxValue - minValue;
        return rg.NextDecimal(range) + minValue;
    }

    static long NextNonNegativeLong(this Random rg) {
        byte[] bytes = new byte[sizeof(long)];
        rg.NextBytes(bytes);
        // strip out the sign bit
        bytes[7] = (byte)(bytes[7] & 0x7f);
        return BitConverter.ToInt64(bytes, 0);
    }

    public static long NextLong(this Random rg, long maxValue) {
        return (long)((rg.NextNonNegativeLong() / (double)Int64.MaxValue) * maxValue);
    }

    public static long NextLong(this Random rg, long minValue, long maxValue) {
        if (minValue >= maxValue) {
            throw new InvalidOperationException();
        }
        long range = maxValue - minValue;
        return rg.NextLong(range) + minValue;
    }
}

Answer 3

Based upon Jon Skeet's method, here's my stab at it:

    public static long NextLong(this Random rnd, long min, long max) {
        if (max <= min)
            throw new Exception("Min must be less than max.");

        long dif = max - min;

        var bytes = new byte[8];
        rnd.NextBytes(bytes);
        bytes[7] &= 0x7f; //strip sign bit

        long posNum = BitConverter.ToInt64(bytes, 0);
        while (posNum > dif)
            posNum >>= 1;

        return min + posNum;
    }

Let me know if you see any errors.

Thanks!