生成均匀随机偏差在给定范围内

本文介绍了生成均匀随机偏差在给定范围内的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我想在给定范围内生成均匀分布的随机整数.我使用的解释型语言具有内置的快速随机数生成器，该生成器返回介于0(含)到1(含)之间的浮点数.不幸的是，这意味着我不能使用在另一种SO中看到的标准解决方案问题(当RNG返回0(包括)到1(不包括)之间的数字时)以生成给定范围内的均匀分布的随机整数:

I'd like to generate uniformly distributed random integers over a given range. The interpreted language I'm using has a builtin fast random number generator that returns a floating point number in the range 0 (inclusive) to 1 (inclusive). Unfortunately this means that I can't use the standard solution seen in another SO question (when the RNG returns numbers between 0 (inclusive) to 1 (exclusive) ) for generating uniformly distributed random integers in a given range:

result=Int((highest - lowest + 1) * RNG() + lowest)

我目前只能看到一个理智的方法，在极少数情况下，随机数生成器返回1只是要求一个新数字.

The only sane method I can see at the moment is in the rare case that the random number generator returns 1 to just ask for a new number.

但是，如果有人知道更好的方法，我将很高兴听到它.

But if anyone knows a better method I'd be glad to hear it.

Rob

注意:将现有的随机数生成器转换为这种语言会导致速度过慢，因此恐怕这不是可行的解决方案.

NB: Converting an existing random number generator to this language would result in something infeasibly slow so I'm afraid that's not a viable solution.

链接到实际的SO答案.

To link to the actual SO answer.

推荐答案

想必您对速度非常感兴趣，否则您将在每次RNG调用时都吸纳条件测试.无论如何，其他任何选择都可能会比分支慢...

Presumably you are desperately interested in speed, or else you would just suck up the conditional test with every RNG call. Any other alternative is probably going to be slower than the branch anyway...

...除非您确切知道RNG的内部结构是什么.特别是，它的返回值是多少?如果它们不是IEEE-754浮点数或双精度点，则您有同感.如果是的话，那么其中有多少个真正的随机性位?浮点数为24，双精度数为53(尾数位).如果这些是天真的生成的，则您可以使用移位和掩码将其中的普通旧随机整数生成器合并在一起，然后在函数中使用它(取决于范围的大小，您可以使用如果有这样的生成器，则需要更多的移位和遮罩以避免任何分支).如果您有一个高质量的生成器，可以生成完整质量的24或53位随机数，则可以通过一次乘法将它们从[0,1]转换为[0,1):只需乘以最大的可生成浮点数即可小于1的点数，您的范围问题就消失了.如果尾数未完全填充随机位，此技巧仍然有效，但是您需要做更多的工作才能找到合适的乘数.

...unless you know exactly what the internal structure of the RNG is. Particularly, what are its return values? If they're not IEEE-754 floats or doubles, you have my sympathies. If they are, how many real bits of randomness are in them? You would expect 24 for floats and 53 for doubles (the number of mantissa bits). If those are naively generated, you may be able to use shifts and masks to hack together a plain old random integer generator out of them, and then use that in your function (depending on the size of your range, you may be able to use more shifts and masks to avoid any branching if you have such a generator). If you have a high-quality generator that produces full quality 24- or 53-bit random numbers, then with a single multiply you can convert them from [0,1] to [0,1): just multiply by the largest generatable floating-point number that is less than 1, and your range problem is gone. This trick will still work if the mantissas aren't fully populated with random bits, but you'll need to do a bit more work to find the right multiplier.

您可能需要查看向梅森·扭曲者(Mersenne Twister)的C来源，以了解他们对类似问题的处理.

You may want to look at the C source to the Mersenne Twister to see their treatment of similar problems.