You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

该函数能否生成均匀分布整数?附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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.06.12 05:12:31