该函数能否生成均匀分布整数?附O(1)无分支实现方案
关于无分支O(1)生成均匀分布随机整数的疑问
近期项目中,我需要从随机字节生成任意范围[a, b]内的均匀分布整数——这是个常见问题,通常用拒绝采样解决。但我好奇能不能在O(1)常数时间、无分支的前提下实现,于是想到了模运算的思路。
可以这样理解这个思路:想象有一个在0到n-1(n≥2的正整数)范围内循环计时的时钟,它匀速持续运转。离开房间后,经过0到m-1(m≥n)的随机时长再返回,记录时钟显示的时间;多次重复这个操作,就能得到目标范围内的随机整数列表。
我目前还不完全清楚这个方法的原理,但测试显示它生成的直方图很平坦,没有模偏置。我用10,000,000个随机字节适配到0-251范围做了两组测试:
- 直接取模(
bytes % 252)的结果 - 我这个方法的结果
以下是我的Python实现,想请教这个方案是否已有先例,以及是否具备数学理论支撑:
import os STATE = 0 def random_int(a: int, b: int): global STATE int_range = b - a + 1 bytes_needed = (int_range.bit_length() + 7) // 8 value = int.from_bytes(os.urandom(bytes_needed)) STATE = (STATE + value) % int_range return STATE + a
内容的提问来源于stack exchange,提问作者Marz
相关产品推荐
相关产品推荐

