生成具有一定最大值的均匀随机整数
我想生成满足0 <= result <= maxValue统一整数。
我已经有一个生成器，它在内置的无符号整数类型的整个范围内返回统一值。 让我们调用这个byte Byte()的方法byte Byte() ， ushort UInt16() ， uint UInt32()和ulong UInt64() 。 假设这些方法的结果是完全一致的。
我想要的方法的签名是uint UniformUInt(uint maxValue)和ulong UniformUInt(ulong maxValue) 。
我在找什么：
- 正确性
我更喜欢在给定的时间间隔内分配返回值。
但如果显着提高性能，则可以接受非常小的偏差。 我的意思是指一个订单的偏差，允许区分符的概率为2/3给定2 ^ 64个值。
它必须适用于任何maxValue。 - 性能
该方法应该很快。 - 效率
该方法确实消耗很少的原始随机性，因为取决于底层生成器，生成原始字节可能是昂贵的。 浪费几个比特很好，但消耗128比特来生成一个数字可能是过多的。
在某些成员变量中，还可以缓存前一次调用中的一些遗留随机性。
小心int溢出和包装行为。
我已经有了一个解决方案（我会将其作为答案发布），但这对我的口味来说有点难看。 所以我想获得更好的解决方案的想法。
关于如何使用大型maxValue进行unit testing的建议也不错，因为我无法生成具有2 ^ 64个桶和2 ^ 74个随机值的直方图。 另一个复杂因素是，对于某些错误，只有一些maxValue发行版有很多偏见，而其他发行版只有很小的偏差。
像这样的通用解决方案怎么样？ 该算法基于Java的nextInt方法使用的算法，拒绝任何会导致非均匀分布的值。 只要你的UInt32方法的输出完全一致，那么这也应该是。
uint UniformUInt(uint inclusiveMaxValue) { unchecked { uint exclusiveMaxValue = inclusiveMaxValue + 1; // if exclusiveMaxValue is a power of two then we can just use a mask // also handles the edge case where inclusiveMaxValue is uint.MaxValue if ((exclusiveMaxValue & (~exclusiveMaxValue + 1)) == exclusiveMaxValue) return UInt32() & inclusiveMaxValue; uint bits, val; do { bits = UInt32(); val = bits % exclusiveMaxValue; // if (bits - val + inclusiveMaxValue) overflows then val has been // taken from an incomplete chunk at the end of the range of bits // in that case we reject it and loop again } while (bits - val + inclusiveMaxValue < inclusiveMaxValue); return val; } }
理论上，拒绝过程可以永远循环; 在实践中表现应该是相当不错的。 在不了解（a）预期使用模式和（b）基础RNG的性能特征的情况下，很难建议任何普遍适用的优化。
例如，如果大多数呼叫者将指定最大值<= 255，则每次要求四个字节的随机性可能没有意义。 另一方面，总是检查实际需要的额外成本可能会超过请求更少字节的性能优势。 （当然，一旦你掌握了具体的信息，你就可以继续优化和测试，直到你的结果足够好。）
我不确定，他的答案是肯定的。 它绝对需要比评论更多的空间，所以我必须在这里写，但我愿意删除，如果其他人认为这是愚蠢的。
从OQ我得到，那
- 熵位非常昂贵
- 其他一切都应该被认为是昂贵的，但不如熵。
我的想法是使用二进制数字到一半，quater … maxValue空间，直到它减少到一个数字。 有点像
我使用maxValue = 333（十进制）作为例子并假设一个函数getBit() ，它随机返回0或1
offset:=0 space:=maxValue while (space>0) //Right-shift the value, keeping the rightmost bit this should be //efficient on x86 and x64, if coded in real code, not pseudocode remains:=space & 1 part:=floor(space/2) space:=part //In the 333 example, part is now 166, but 2*166=332 If we were to simply chose one //half of the space, we would be heavily biased towards the upper half, so in case //we have a remains, we consume a bit of entropy to decide which half is bigger if (remains) if(getBit()) part++; //Now we decide which half to chose, consuming a bit of entropy if (getBit()) offset+=part; //Exit condition: The remeinind number space=0 is guaranteed to be met //In the 333 example, offset will be 0, 166 or 167, remaining space will be 166 } randomResult:=offset
getBit()可以来自你的熵源，如果它是基于位的，或者在第一次调用时一次消耗n位熵（显然n是你的熵源的最佳值），并将其转换为空。
我目前的解决方案 我的口味有点难看。 每个生成的数字也有两个分区，这可能会对性能产生负面影响（我还没有对此部分进行过分析）。
uint UniformUInt(uint maxResult) { uint rand; uint count = maxResult + 1; if (maxResult < 0x100) { uint usefulCount = (0x100 / count) * count; do { rand = Byte(); } while (rand >= usefulCount); return rand % count; } else if (maxResult < 0x10000) { uint usefulCount = (0x10000 / count) * count; do { rand = UInt16(); } while (rand >= usefulCount); return rand % count; } else if (maxResult != uint.MaxValue) { uint usefulCount = (uint.MaxValue / count) * count;//reduces upper bound by 1, to avoid long division do { rand = UInt32(); } while (rand >= usefulCount); return rand % count; } else { return UInt32(); } } ulong UniformUInt(ulong maxResult) { if (maxResult < 0x100000000) return InternalUniformUInt((uint)maxResult); else if (maxResult < ulong.MaxValue) { ulong rand; ulong count = maxResult + 1; ulong usefulCount = (ulong.MaxValue / count) * count;//reduces upper bound by 1, since ulong can't represent any more do { rand = UInt64(); } while (rand >= usefulCount); return rand % count; } else return UInt64(); }