关于产生在固定范围内均匀分布的随机数问题

[MrVito]

之前一直用的是 Rand()%(range+1)，昨天发现这个有点问题，概率好像不太对，于是在网上查了发现如果 range 不能被 rand_max 整除的话，确实会出现问题，于是我想了一个解决方案，在这里提出来，想问问有没有什么 bug，思路就是 floor((Rand ()/rand_max)*range)，就是说先把产生的随机数平均分布在[0,1]里面再扩大到 range 里面，请问这种思路有什么 bug 吗？

手机发帖大家凑合看，不知道格式有没有什么问题……

[geelaw]

这个错误在于 rand()/(RAND_MAX+0.) 并不接近均匀分布的实数，而是离散分布的。

一个简单的做法是 rejection sampling，不过效率比较低。均摊效率更高的做法是批量型 rejection sampling （在把 rand 替换为真随机数后的 hybrid 是完美的分布），或者用 leftover hash lemma （但这样就不完美了）。