c# - RNGCryptoServiceProvider - 更快地生成一个范围内的数字并保留分布？

Question

我正在使用 RNG 加密提供程序以真正天真的方式生成一定范围内的数字:

byte[] bytes = new byte[4];
int result = 0;
while(result < min || result > max)
{
   RNG.GetBytes(bytes);
   result = BitConverter.ToInt32(bytes);
}  

当范围足够宽以至于有很大机会获得结果时，这很好，但今天早些时候我遇到了一个范围足够小(在 10,000 个数字以内)的场景，它可能需要一段时间。

所以我一直在努力想出一种更好的方法，既能实现良好的分发，又能更快。但现在我正在深入学习我在学校根本没有学过的数学和统计学，或者至少如果我学过，我已经完全忘记了!

我的想法是:

• 获取最小值和最大值的最高设置位位置，例如4 人为 3，17 人为 5
• 从 prng 中选择至少包含高位的字节数，例如 1 在这种情况下为 8 位
• 查看是否设置了允许范围 (3-5) 中的任何高位
• 如果是，将其转换为一个数字，包括高位
• 如果该数字介于最小值和最大值之间，则返回。
• 如果之前的任何测试失败，请重新开始。

就像我说的，这可能非常天真，但我相信它会比当前实现更快地返回一个狭窄范围内的匹配。我现在不在电脑前，所以无法测试，将在英国时间明天早上进行测试。

当然，速度不是我唯一关心的问题，否则我只会使用Random(如果有人足够友善的话，需要几个刻度线才能正确格式化 - 他们不在Android 键盘!)。

我对上述方法最大的担忧是，我总是丢弃由 prng 生成的最多 7 位，这看起来很糟糕。我想到了将它们考虑在内的方法(例如简单的加法)，但它们看起来非常不科学!

我知道 mod 技巧，您只需生成一个序列，但我也知道它的弱点。

这是死胡同吗？最终，如果最好的解决方案是坚持当前的实现，我会这样做，我只是觉得必须有更好的方法!

Answer 1

Stephen Toub 和 Shawn Farkas 在 MSDN 上共同撰写了一篇名为 Tales From The CryptoRandom 的优秀文章如果您正在试验 RNGCryptoServiceProviders，您绝对应该阅读

在其中，他们提供了一个继承自 System.Random 的实现(其中包含您正在寻找的很好的范围随机方法)，但他们的实现使用 RNGCryptoServiceProvider 而不是使用伪随机数。 .

他实现Next(min, max)方法的方式如下:

public override Int32 Next(Int32 minValue, Int32 maxValue)
{
    if (minValue > maxValue) 
        throw new ArgumentOutOfRangeException("minValue");
    if (minValue == maxValue) return minValue;
    Int64 diff = maxValue - minValue;
    while (true)
    {
        _rng.GetBytes(_uint32Buffer);
        UInt32 rand = BitConverter.ToUInt32(_uint32Buffer, 0);

        Int64 max = (1 + (Int64)UInt32.MaxValue);
        Int64 remainder = max % diff;
        if (rand < max - remainder)
        {
            return (Int32)(minValue + (rand % diff));
        }
    }
}

实现选择的原因以及关于随机性损失的详分割析以及他们为产生高质量随机数所采取的步骤在 their article 中。 .

线程安全缓冲 CryptoRandom

我已经编写了 Stephen 类的扩展实现，它利用随机缓冲区来最小化调用 GetBytes() 的任何开销。我的实现还使用同步来提供线程安全，从而可以在所有线程之间共享实例以充分利用缓冲区。

我是为一个非常具体的场景编写的，因此您当然应该根据应用程序的特定争用和并发属性来分析它是否对您有意义。如果你不想查看，我把代码放在了 github 上。

Threadsafe buffered CryptoRandom based on Stephen Toub and Shawn Farkas' implementation

当我写它的时候(几年前)我似乎也做了一些分析

Results produced by calling Next() 1 000 000 times on my machine (dual core 3Ghz)

System.Random completed in 20.4993 ms (avg 0 ms) (first: 0.3454 ms)
CryptoRandom with pool completed in 132.2408 ms (avg 0.0001 ms) (first: 0.025 ms)
CryptoRandom without pool completed in 2 sec 587.708 ms (avg 0.0025 ms) (first: 1.4142 ms)

|---------------------|------------------------------------|
| Implementation      | Slowdown compared to System.Random |
|---------------------|------------------------------------|
| System.Random       | 0                                  |
| CryptoRand w pool   | 6,6x                               |
| CryptoRand w/o pool | 19,5x                              |
|---------------------|------------------------------------|

请注意，这些测量仅描述了非常具体的非真实场景，并且应该仅用于指导，测量您的场景以获得正确的结果。