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

Question

我有一个组合问题，我希望能够在运行dom 处选择一个介于 0 和一个大整数之间的整数。

我当前方法的不足

现在对于常规整数，我通常会写类似 int rand 500; 的东西，然后完成它。

但是对于大整数，rand 似乎并不适用于此。

使用下面的代码，我运行模拟了对rand $bigint的200万次调用：

$ 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 return编辑的位的大小：n_bits_prng
计算需要的样本数：needed_prng_samples = ceil(n_needed_bits / n_bits_prng)
虽然正确：
- 采样 needed_prng_samples（调用 PRNG）次并连接获得的所有位
- 检查结果数字是否在您的范围内
- 是吗?: return 号（完成）
- 否？：什么也不做（循环继续；将再次对所有组件重新采样！）

备注

这是acceptance-sampling / rejection-sampling
方法是Las-vegas type of algorithm：理论上运行时间不受限制
- 平均需要循环次数：n_possible-sample-numbers-of-full-concatenation / n_possible-sample-numbers-within-range
根据拒绝方法的完整重采样（如果结果不在范围内）提供了对无偏差/均匀性的更正式分析的访问权，并且是该方法的一个非常重要的方面
当然，需要关于 PRNG 输出的经典假设才能完成这项工作。
- 例如，如果 PRNG 在低位/高位方面存在一些不均匀性（如经常提到的那样），这将对上述输出产生影响

Answer 2

一种方法是将数字的字符串表示形式切割成块，初始化的布尔值（$low）为假，而第一次随机抽取等于上限。

编辑：在评论后添加了一些解释

# first argument (in) upper bound
# second argument (in/out) is lower (false while random returns upper bound, after it remains true)
sub randhlp {
    my($upp)=@_;
    my $l=length $upp;
    # random number less than
    # - upper bound if islower is false
    # - 9..99 otherwise
    my $x=int rand ($_[1] ? 10**$l : $upp+1);
    if ($x<$upp) {
        $_[1]=1;
    }
    # left padding with 0
    return sprintf("%0*d",$l,$x);
}

# returns a random number less than argument (numeric string)
sub randistr {
    my($n)=@_;
    $n=~/^\d+$/ or die "invalid input not numeric";
    $n ne "0" or die "invalid input 0";
    my($low,$x);
    do {
        undef $x;
        # split string by chunks of 6 characters
        # except last chunk which has 1 to 6 characters
        while ($n=~/.{1,6}/g) {
            # concatenate random results
            $x.=randhlp($&,$low)
        }
    } while ($x eq $n);
    $x=~s/^0+//;
    return $x;
}

测试

for ($i=0;$i<2e6;++$i) {
    $H{length(randistr("1230138339199329632554990773929330319360000000"))}+=1;
}

print "$_ $H{$_}\n" for sort keys %H;

Returns

Answer 3

我看问题的角度不对

垃圾箱大小不一。每个箱子的大小是前一个箱子的 10 倍。从正确的角度来看，对于每个大小为 1e+40.

的整数，在大小为 1e+44 时有 10,000 个可能的整数

1e+45 处的 bigint 找到任何大小为 1e+20 的数字的概率小于 0.00000 00000 00000 00000 001 %.

忘掉大海捞针，这更像是在类星体中寻找针头！

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

How can I pick a random value between 0 and a bigint?

random

perl

bigint

我当前方法的不足

如何克服这个限制？

伪代码

备注

我看问题的角度不对