如何在0和bigint之间选择一个随机值？

Question

我有一个组合学问题,我希望能够在0和一个大整数之间随机选择一个整数.

---

我目前做法的不足之处

现在对于常规整数,我通常会写一些类似的东西int rand 500;并完成它.

但对于大整数来说,它看起来rand并不适合这个.

使用以下代码,我运行了200万次调用的模拟rand $bigint:

$ perl -Mbigint -E 'say int rand 1230138339199329632554990773929330319360000000 for 1 .. 2e6' > rand.txt

结果集的分布远非理想:

• 0(56计数)
• 幅度1e + 040(112计数)
• 幅度1e + 041(1411计数)
• 幅度1e + 042(14496计数)
• 幅度1e + 043(146324计数)
• 幅度1e + 044(1463824计数)
• 幅度1e + 045(计算373777)

因此,该过程永远无法选择一个类似的数字999,或者5e+020,这使得这种方法不适合我想要做的事情.

看起来这与任意精度有关rand,在测试过程中它永远不会超过15位数:

$ perl -E 'printf "%.66g", rand'
0.307037353515625

---

我怎样才能克服这个限制？

我最初的想法是,可能有一种方法可以影响精度rand,但感觉就像是一个更大问题的创可贴(即无法rand处理大整数).

无论如何,我希望有人之前走过这条路,并知道如何纠正这种情况.

Answer 1

(转自我的评论)

更理论化的方法是使用多次调用PRNG来为您的数字创建足够的随机位进行采样.如果某个PRNG产生的比特数不等于下面所述的比特数,则必须小心!

伪代码

• 计算代表您的号码所需的位数: n_needed_bits
• 检查PRNG返回的位大小: n_bits_prng
• 计算所需的样品数量: needed_prng_samples = ceil(n_needed_bits / n_bits_prng)
• 虽然如此:
  • 采样needed_prng_samples(调用PRNG)次并连接所有获得的位
  • 检查结果数字是否在您的范围内
  • 是吗？:退货号码(已完成)
  • 不？:什么都不做(循环继续;将再次重新采样所有组件!)

备注

• 这是一种接受采样/拒绝采样的形式
• 该方法是Las-vegas类型的算法:运行时在理论上不受限制
  • 所需的循环数平均为: n_possible-sample-numbers-of-full-concatenation / n_possible-sample-numbers-within-range
• 根据拒绝方法进行的完整重采样(如果结果不在范围内)可以获得对非偏置/均匀性的更正式分析,这是这种方法的一个非常重要的方面
• 当然,需要有关PRNG输出的经典假设才能实现这一目标.
  • 例如,如果PRNG在低位/高位(如常提到的话)方面有一些不均匀性,这将对上面的输出产生影响