4
\$\begingroup\$

I've corrected the bug in the first version and fixed up the error messages.

As for using floating arithmetic, since i'm not using more than 10 digits of the generated double, which, to my understanding, has at least 14 significant digits I can't see how the rounding will effect the outcome.

As for the randomness of the results, I can't seem to find any bias in the results of this algorithm. Perhaps someone has a better test and hard numbers, instead of blind theory.

        public static class CryptoRandom
        {
            const double MAX_RANGE = (double)UInt64.MaxValue + 1;

            /// <summary>
            /// Internal algorithm to generate the range based integers.           
            /// </summary>
            static int Next(UInt64 min, UInt64 max)
            {
                if (max < min)
                {
                    throw new ArgumentException($"max is less than min.  The values are, min = {min}, max = {max}");
                }
                if(min < 0)
                {
                    throw new ArgumentException($"min is negative.  The value is min = {min}");
                }
                if (min == max)
                {
                    throw new ArgumentException($"min equals max.  The values are, min = {min}, max = {max}");
                }

                using (RNGCryptoServiceProvider rng = new RNGCryptoServiceProvider())
                {
                    byte[] randomNumber = new byte[8];

                    rng.GetBytes(randomNumber);
                    double baseNum = BitConverter.ToUInt64(randomNumber, 0) / MAX_RANGE;

                    UInt64 range = max - min;

                    return (int)((baseNum * range) + min);
                }

            }
            /// <summary>
            /// Get a cryptographic random 32-bit integer in the range from
            /// min(inclusive) to max(exclusive)
            /// </summary>
            public static int Next(int min, int max)
            {
                return (int)Next((UInt64)min, (UInt64)max);
            }
            /// <summary>
            /// Get a cryptographic random 32-bit integer in the range from
            /// 0 to max(exclusive)
            /// </summary>
            public static int Next(int max)
            {
                return (int)Next(0, (UInt64)max);
            }

            /// <summary>
            /// Get a cryptographic random 32-bit integer
            /// </summary>
            public static int Next()
            {
                return (int)Next(0, (UInt64)Int32.MaxValue+1);
            }


        }
\$\endgroup\$
  • \$\begingroup\$ I can't comment on the statistics of it because i haven't checked the distribution of 100000s of the random numbers generated, but i can make some comments about the naming of the methods/class - which you may find useful: gist.github.com/BKSpurgeon/9eb15c6cb42471f4a50f9d03029dd98b \$\endgroup\$ – BKSpurgeon Jan 12 '18 at 14:01
3
\$\begingroup\$

First of all somehing trivial:

  • When max < min or max == min you correctly throw ArgumentException but then for min < 0you should throw ArgumentOufOfRangeException however...ulong cannot be less than zero then this check is meaningless.

  • There is a needless cast in the other overloads of Next(): return value is already an int.

  • If you cast int to ulong (signed to unsigned) you may want to do it in a checked environment to, at least, have a run-time error instead of wrong but undetected values (I assume that you do not want to penalize distribution simply discarding ms bits).

  • You may replace new byte[8] with new byte[sizeof(ulong)].

Now more serious things...

Using double for such big range you effectively break the distribution of your random numbers (because above a threshold even integer numbers cannot be represented correctly in floating point). I understand that you're doing that to keep an apparent upper limit equal to UInt64.MaxValue but you're sacrificing randomness. It may be an issue or not, in your case, but be aware of it.

As you already know RNGCryptoServiceProvider generates random bytes and Convert.ToUInt64() is not enough to have a true randomly generated number (because each byte, not their composition, is supposed to be randomly distributed). There is a technique you're somehow applying to compensate this issue and it's described by Stephen Toub and Shawn Farkas in Tales from the CryptoRandom. I suggest to pick their code and to use it as-is until you completely understand their implementation (and the implication of any change). Not that this will introduce any big bias in your calculations but unless you statistically validate your algorithm I think you should stick to well-known and reviewed implementations.

As Adam already noted in his answer you should not have a static class and RNGCryptoServiceProvider should be a class member. Let the caller decide how your random number generator should be used to have a better distribution. Don't forget to implement IDisposable also for your class. Also consider to accept ctor parameter of type RandomNumberGenerator (which can be mocked in your tests), you may want to test your code with a well-known set of inputs, not with random ones:

public sealed class CryptoRandom : IDisposable
{
    public CryptoRandom(RandomNumberGenerator generator)
    {
        _generator = generator ?? throw new ArgumentNullException(nameof(generator));
    }

    public CryptoRandom()
        : this(new RNGCryptoServiceProvider())
    {
    }

    // ...

    private readonly RandomNumberGenerator _generator;
}

There is, finally, an even more serious problem. If you initialize RNGCryptoServiceProvider without a seed then it will use Environment.TickCount and its resolution is limited to the system timer resolution (typically 10 ms), this alone will practically vanish most of your effort.

\$\endgroup\$
  • \$\begingroup\$ I'm not at all sure you're right about the range of the double being an issue. A double has 53 bits of precision, which means that choosing a 32-bit integer this way will result in less than 1/2^-21 bias for any given integer. You couldn't even write a program that could even detect such a small bias, even running 24/7/365 on a supercomputer. \$\endgroup\$ – Adam Brown Jan 12 '18 at 20:04
  • \$\begingroup\$ Also, I think your assertion about the distribution of bits in RNGCryptoServiceProvider is wrong. It would be a very dangerous thing if there was any correlation between the bits produced by it, in fact the whole point of a crypto service provider is to make absolutely, 100%, sure that there isn't a correlation between any of the successive bits, of any sort. Unlike floating point numbers, where if you choose random bits you don't get a uniform distribution, @tinstaafl is converting to a UInt64, which is fine. \$\endgroup\$ – Adam Brown Jan 12 '18 at 20:16
  • \$\begingroup\$ @Adam Range of double is an issue. You do not need to run 24/7 to find that number. Just declare a double variable x and set it to 9007199254740991, now compare the result of x + 1 and x + 2 and you'll (surprising?) see that they're the same. Note that this number is well below ulong.MaxValue. That's the maximum integer number you can represent with a double precision floating number without losing any precision. \$\endgroup\$ – Adriano Repetti Jan 12 '18 at 21:18
  • \$\begingroup\$ About second assertion: that's EXACTLY the problem. RNGCryptoServiceProvider is a cryptographic number generator then it's good. Generated values have a good distribution. However combining 8 bytes to form a value with a bigger range is not the same as generating a value with that range. It's not formally correct (no need to explain why) but think about this intuitive example: three ulong values 1, 2 and 3 have a good distribution. However to generate those values from 24 byte (3 * 8) you need these values: 1, 2, 3 and...21 times 0. Thats's a bad distribution. \$\endgroup\$ – Adriano Repetti Jan 12 '18 at 21:25
  • \$\begingroup\$ wrong on both points, I think. Firstly, 2^53 is the largest integer that double can represent exactly, yes. But he is mashing them back down into the integer range with a floating point divide. So each possible integer value in the output is going to map to 2^21 random double values. Not a problem if for some integers that is 2^21 + 1 and for others just 2^21. \$\endgroup\$ – Adam Brown Jan 12 '18 at 21:32
1
\$\begingroup\$

The only thing I'm a little worried about is the recreation of the RNGCryptoServiceProvider for every call to Next - creating 8 bytes. I think you'll get much better performance if you create more bytes, and only go back when the buffer is used up. So you could pre-create 2048 bytes, and then only go back to get new bytes every 256 calls, for instance.

I don't know about your specific use case, but most PRNG interfaces have a NextDouble() or something similar.

Overall, the distribution doesn't look like it's going to have any issues - as you said, the precision of a double is enough to exactly cover all integers.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.