按年被提到
20182020 · 3 次2026
算法与数据结构›哈希、压缩与向量化·arXiv:1805.10941 · cs.DS

Fast Random Integer Generation in an Interval

区间内的快速随机整数生成
Daniel Lemire · 2018

无偏随机整数的区间映射:高概率避开整数除法,洗牌更快

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 6 人首次 2018-05-30 · 最近 2021-08-18
6不同的人
5活跃月份
5讨论串
57被引(OpenAlex)

论文回顾一种在区间 [0,s) 内生成无偏随机整数的算法:它从随机字出发,高概率避免整数除法,而标准库(如 Java)的常见做法依赖开销较大的除法。作者证明该方法在 x64 上可成倍加快无偏随机洗牌,并已被 Go 语言用于其 shuffle 实现。

HN 为什么提它

评论者追溯某些语言(如 Julia)更快随机整数实现的来源时引用它,并澄清它不是随机数生成器本身,而是把随机数输出无偏地映射到任意区间的方法。

方法难度 2 / 5约 20 分钟经得起时间
读之前最好知道
1伪随机数生成器(PRNG)
2Fisher-Yates 洗牌
3拒绝采样(rejection sampling)
4整数乘法与除法的开销

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用igg · 2020-08

“Digging deeper, at least one of the PRs [1] is based on a 2018 paper [2].”

指出其中一个 PR 基于这篇 2018 年的论文
Julia 1.5 Highlights原评论 ↗
引用MauranKilom · 2020-10

“I did skim the paper to find which of the listed algorithms is the one in question (Algorithm 5)”

略读论文,找出所讨论的算法是其中的算法 5
Dissecting Lemire's nearly divisionless random number generator原评论 ↗
引用Reelin · 2020-10

“Looking at the original paper this doesn't seem to be a RNG itself but rather a method to efficiently transform the output of a RNG onto an arbitrary interval while maintaining a uniform distribution.”

指出它不是 RNG,而是把 RNG 输出均匀映射到任意区间的方法
Dissecting Lemire's nearly divisionless random number generator原评论 ↗
引用NWDD · 2021-08

“wrote blog posts and an academic paper comparing different approaches”

提到有人写了博客和学术论文来比较不同方法
A fast alternative to the modulo reduction (2016)原评论 ↗
被提交为 story · 2 次