主要观点:作者之前写过关于 Daniel Lemire 几乎无除法无偏有界随机数算法,最近发现 Steve Canon 和 Kendall Willets 有真无除法随机数方法,作者编写了自己的真无除法随机数版本并与 Lemire 算法比较。
关键信息:通过将原始随机数生成器处理为定点分数来获取所需范围随机数,利用高精度分数处理避免偏差,通过左右相加处理进位,存在提前退出情况,使用位操作进行进位检查,给出了真无除法和几乎无除法随机数的代码及基准测试结果,真无除法算法理解简单但代码更长更分支,在不同硬件上性能表现不同。
重要细节:用W == 1<<32
表示字大小的 2 的幂,原始随机数生成器rng()
产生[0,W)范围数,处理为[0,1)范围分数后乘以限制得到 32.32 定点结果,高精度分数通过系列原始随机数扩展相加,加法有三种情况处理进位,存在提前退出情况避免获取下一个随机数,通过位操作测试进位,基准测试在不同硬件上比较了两种算法的随机数生成时间和rng()
调用次数,真无除法算法在硬件除法快时表现较好,几乎无除法算法在随机数生成器调用次数上有优势,若需大限制无偏数最好使用一次生成 64 位的 RNG 使算法少走慢路径。
**粗体** _斜体_ [链接](http://example.com) `代码` - 列表 > 引用
。你还可以使用@
来通知其他用户。