RNGCryptoServiceProvider - 产生一系列快一些，并保留分配？ [英] RNGCryptoServiceProvider - generate number in a range faster and retain distribution?

问题描述

首先，我在手机上，所以请原谅格式可怜！

First I'm on a phone so please forgive poor formatting!

我已经做了很多，现在搜索，发现没有明确的答案。如果没有一个，很公平，但我敢肯定有人比我聪明必须有一个很好的答案！

I've done a lot of searching now and found no definitive answer to this. If there isn't one, fair enough, but I'm sure somebody smarter than I must have a good answer!

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

I'm using the RNG crypto provider to generate numbers in a range the truly naive way:

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

这是伟大的，当该范围足够宽，这样，有一个像样的机会得到一个结果，但今天早些时候我打一个场景，范围足够小（在万数字），它可以采取一个时代。

This is great when the range is wide enough such that there is a decent chance of getting a result, but earlier today I hit a scenario where the range is sufficiently small (within 10,000 numbers) that it can take an age.

所以我一直在试图想出更好的方式，将获得一个体面的分布，但会更快。但现在我陷入更深的数学和统计数据，我根本没有在学校里，或至少如果我做了我已经忘记了这一切！

So I've been trying to think of a better way that will achieve a decent distribution but will be faster. But now I'm getting into deeper maths and statistics that I simply didn't do at school, or at least if I did I have forgotten it all!

我的想法是：

• 获得的最小值和最大值，例如最高设置位的位置4这将是3和17将是5


• 选择号码从PRNG字节可能包含至少高比特，EG1在这种情况下，对于8位


• 查看是否有在允许的范围内（3-5）上的位被置


• 如果有，把它转换成一个数达和包括高比特


• 如果这个数字是最小和最大，收益之间。


• 如果任何以前的测试失败，重新开始。

• get the highest set bit positions of the min and max, e.g. for 4 it would be 3 and for 17 it would be 5
• select a number of bytes from the prng that could contain at least the high bits, e.g.1 in this case for 8 bits
• see if any of the upper bits in the allowed range (3-5) are set
• if yes, turn that into a number up to and including the high bit
• if that number is between min and max, return.
• if any of the previous tests fail, start again.

就像我说的，这可能是非常天真的，但我相信它会在一个狭窄的范围内返回匹配比目前的实现速度更快。我不是在此刻坐在电脑前等不能考，会做，明天上午英国时间。

Like I say, this could be exceedingly naive, but I am sure it will return a match in a narrow range faster than the current implementation. I'm not in front of a computer at the moment so can't test, will be doing that tomorrow morning UK time.

不过，当然速度是不是我的唯一的关注，否则，我只想用的随机的（需要一对夫妇的刻度线的有正确格式，如果有人会热情地向 - 他们不是在Android键盘上）。

But of course speed isn't my only concern, otherwise I would just use Random (needs a couple of tick marks there to format correctly if someone would be kind enough - they're not on the Android keyboard!).

我与上述方法最大的担心是，我总是扔掉了由PRNG，这似乎是坏生成的7位。我想到的方式（例如，一个简单的加法），从而将它们，但他们似乎非常不科学的黑客！

The biggest concern I have with the above approach is that I am always throwing away up to 7 bits that were generated by the prng, which seems bad. I thought of ways to factor them in (e.g. a simple addition) but they seem terribly unscientific hacks!

我知道mod把戏，在这里你只需要生成一个序列，但我也知道它的弱点。

I know about the mod trick, where you only have to generate one sequence, but I also know about its weaknesses.

这是一个死胡同？如果最终的最佳解决方案将是坚持使用当前的实现，我会的，我只是觉得必须有一个更好的办法！

Is this a dead end? Ultimately if the best solution is going to be to stick with the current implementation I will, I just feel that there must be a better way!

推荐答案

斯蒂芬Toub和Shawn Farkas的具有共同编写在MSDN上的优秀文章叫的传说从CryptoRandom 的，如果你用的 RNGCryptoServiceProviders

Stephen Toub and Shawn Farkas has co-written an excellent article on MSDN called Tales From The CryptoRandom that you should definitely read if you're experimenting with RNGCryptoServiceProviders

在这他们提供了从System.Random继承的实现（其中包含你正在寻找），但不是使用伪随机数的实现使用的 RNGCryptoServiceProvider

In it they provide an implementation that inherits from System.Random (which contains the nice range-random method that you're looking for) but instead of using pseudo random numbers their implementation uses the RNGCryptoServiceProvider.

他实施了下一步的方式（最小，最大）方法如下：

The way he has implemented the Next(min, max) method is as follows:

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));
        }
    }
}

有关的选择的理由实施以及对随机性的损失和什么步骤，他们正在生产出高品质的随机数是的他们的文章。

The reasoning for the choice of implementation as well as a detailed analysis about loss of randomness and what steps they are taking to produce high-quality random numbers is in their article.

线程安全bufferred CryptoRandom

我写了一个扩展实现斯蒂芬该类的，以最小化）呼唤GetBytes会的任何开销（利用随机缓冲区。我的实现还使用同步提供线程安全，使其能够分享你所有的线程之间的实例，以充分利用缓冲区。

I've written an extended implementation of Stephen's class which utilized a random buffer in order to minimize any overhead of calling out to GetBytes(). My implementation also uses synchronization to provide thread safety, making it possible to share the instance between all your threads to make full use of the buffer.

我写了这个一个非常特殊的情况，所以你当然应该轮廓是否有意义，你给你的应用程序的特定争和并发属性。我扔在GitHub上，如果你wan't检查出来的代码了。

I wrote this for a very specific scenario so you should of course profile whether or not is makes sense for you given the specific contention and concurrency attributes of your application. I threw the code up on github if you wan't to check it out.

根据斯蒂芬Toub和线程缓冲CryptoRandom肖恩法卡斯'执行

当我写它（几年前）我似乎已经做了一些分析为通过调用下一个（）我的机器上1 000 000次（双核3GHz的）
$ b制作精良

When I wrote it (a couple of years back) I seem to have done some profiling as well

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                              |
|---------------------|------------------------------------|

请注意，theese三围只有轮廓一个非常具体的非真实世界的场景，只应使用为指导，衡量你的正确结果的情况。

Please note that theese measurements only profile a very specific non-real-world scenario and should only be used for guidance, measure your scenario for proper results.

这篇关于RNGCryptoServiceProvider - 产生一系列快一些，并保留分配？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！