节点:使用 crypto.randomBytes 生成 6 位随机数 [英] Node: Generate 6 digits random number using crypto.randomBytes
问题描述
由于 1000000 不是 2 的幂，随机生成从 0 到 999999 的精确值的正确方法是什么?
What is the correct way to generate exact value from 0 to 999999 randomly since 1000000 is not a power of 2?
这是我的方法:
- 使用
crypto.randomBytes生成3个字节并转换为hex - 使用前 5 个字符转换为整数(最大值为
fffff==1048575>999999) - 如果结果>
999999，再次从第1步开始
- use
crypto.randomBytesto generate 3 bytes and convert tohex - use the first 5 characters to convert to integer (max is
fffff==1048575>999999) - if the result >
999999, start from step 1 again
它会以某种方式创建一个递归函数.它在逻辑上是否正确，是否会引起性能问题?
It will somehow create a recursive function. Is it logically correct and will it cause a concern of performance?
推荐答案
有几种方法可以从随机位中提取一定范围内的随机数.NIST Special Publication 800-90A 第 1 版中描述了一些常见的: 使用确定性随机位生成器生成随机数的建议
There are several way to extract random numbers in a range from random bits. Some common ones are described in NIST Special Publication 800-90A revision 1: Recommendation for Random Number Generation Using Deterministic Random Bit Generators
虽然该标准是关于确定性随机位生成的，但有一个有用的附录，称为 A.5 将随机位转换为随机数，其中描述了三种有用的方法.
Although this standard is about deterministic random bit generations there is a helpful appendix called A.5 Converting Random Bits into a Random Number which describes three useful methods.
描述的方法是:
- A.5.1 简单丢弃方法
- A.5.2 复杂丢弃法
- A.5.3 简单的模块化方法
它们中的前两个在运行时间方面不是确定性的，但会生成一个完全没有偏差的数字.它们基于拒绝抽样.
The first two of them are not deterministic with regards to running time but generate a number with no bias at all. They are based on rejection sampling.
复杂丢弃方法讨论了一种更优化的方案，用于在一定范围内生成大量随机数.我认为它对于几乎任何正常使用来说都太复杂了.如果您需要更高的效率，我会看看下面描述的 Optimized Simple Discard 方法.
The complex discard method discusses a more optimal scheme for generating large quantities of random numbers in a range. I think it is too complex for almost any normal use; I would look at the Optimized Simple Discard method described below if you require additional efficiency instead.
简单模块化方法是时间常数和确定性的，但具有非零(但可忽略不计)偏差.但是，它需要相对大量的额外随机性才能实现可忽略的偏差；基本上，要获得 2^128 中的一个偏差，您需要在所需范围的位大小之上增加 128 位.对于较小的数字，这可能不是选择的方法.
The Simple Modular Method is time constant and deterministic but has non-zero (but negligible) bias. It requires a relatively large amount of additional randomness to achieve the negligible bias though; basically to have a bias of one out of 2^128 you need 128 bits on top of the bit size of the range required. This is probably not the method to choose for smaller numbers.
您的算法显然是简单丢弃方法的一个版本(通常称为拒绝采样")，所以没问题.
我自己想到了一种基于简单丢弃方法的非常有效的算法，称为 "Optimized简单的丢弃方法"或RNG-BC，其中BC"表示BC".代表二进制比较".它基于以下观察:比较只查看最高有效位，这意味着最低有效位仍应被视为随机的，因此可以重复使用.请注意，此方法尚未经过官方同行评审；我确实提供了与简单丢弃方法等效的非正式证明.
I've myself thought of a very efficient algorithm based on the Simple Discard Method called the "Optimized Simple Discard Method" or RNG-BC where "BC" stands for "binary compare". It is based on the observation that comparison only looks at the most significant bits, which means that the least significant bits should still be considered random and can therefore be reused. Beware that this method has not been officially peer reviewed; I do present an informal proof of equivalence with the Simple Discard Method.
当然，您应该使用 通用方法，该方法在给定任何 N 值的情况下都是有效的.在这种情况下，应该考虑复杂丢弃方法或简单模块化方法而不是简单丢弃方法.还有其他更复杂的算法效率更高，但通常使用这两种算法中的任何一种都可以.
Of course you should rather use a generic method that is efficient given any value of N. In that case the Complex Discard Method or Simple Modular Method should be considered over the Simple Discard Method. There are other, much more complex algorithms that are even more efficient, but generally you're fine when using either of these two.
请注意，在生成 [0, N) 范围内的随机数时，首先检查 N 是否为 2 的幂通常是有益的.如果 N 是 2 的幂，则无需使用任何这些可能昂贵的计算；只需使用随机位或字节生成器中所需的位即可.
Note that it is often beneficial to first check if N is a power of two when generating a random in the range [0, N). If N is a power of two then there is no need to use any of these possibly expensive computations; just use the bits you need from the random bit or byte generator.
这篇关于节点:使用 crypto.randomBytes 生成 6 位随机数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
