随机数生成算法的性能瓶颈：并非你选择的PRNG

本文通过一个故事引出随机数生成算法性能优化的关键问题：瓶颈可能并非PRNG本身，而是生成指定范围随机数的方法。作者比较了多种生成指定范围随机数的方法，包括经典的取模法、浮点乘法、整数乘法、以及几种无偏方法，例如拒绝采样法和位掩码法。实验结果表明，在不同的PRNG和数据规模下，最佳方法各不相同，但基于整数乘法的Lemire方法经过优化后表现出色，显著提升了性能。文章还比较了多种PRNG的性能，发现即使是最快的PRNG，性能提升也远不如优化范围生成方法带来的提升显著。