生成 BigInt 值的随机样本

问：

对于用 JavaScript 实现的游戏，我需要生成一个唯一数字的随机列表，其范围可能大于 。这带来了三个重要挑战：n[0, N)NNumber.MAX_SAFE_INTEGER

• 内存成本不能是 O（N），因为我们没有足够的 RAM。这意味着我们不能使用修改后的 Fisher-Yates 随机算法从元素数组中获取随机值。（JS 数组仅限于 32 位索引，但在此之前我们早就耗尽了 RAM。nN
• 执行时间应尽可能接近 O（n） 而不是 O（N）。我预计 n 会相对较小（< 100）。
• 大多数数学运算使用双精度浮点值，不适用于这么大的数字。

我在 Kim-Hung Li 的储层采样算法 L 中找到了解决前两个挑战的解决方案。总而言之，这个算法背后的想法是，我们洗牌第一个数字以形成一个初始水库，然后我们用从范围的其余部分获取的随机数逐步覆盖其中的一些数字。我们使用几何级数来确定每次迭代要跳过多少个数字。n

假设 sampleSize 是一个数字，populationSize 是一个 BigInt，代码如下：

// Creates an array initialized with [0n, 1n, ... BigInt(count-1)].
function bigRange (count) {
    const array = Array(count);
    for (let i = 0; i < count; i += 1) {
        array[i] = BigInt(i);
    }
    return array;
}

function bigSample (sampleSize, populationSize) {
    const reservoir = shuffle(bigRange(sampleSize));
    let record = BigInt(sampleSize);
    let weight = exp(log(random()) / sampleSize);

    while (true) {
        const skipCount = floor(log(random()) / log(1 - weight));
        record += BigInt(skipCount);

        if (record >= populationSize) {
            return reservoir;
        }

        reservoir[floor(random() * sampleSize)] = record;
        record += BigInt(1);
        weight *= exp(log(random()) / sampleSize);
    }
}

但是，此代码不适用于任意大的数字，因为浮点数的精度是有限的。随着 populationSize 的增长，浮点数的非有效位最终被使用，我们不再具有均匀分布，然后我们进入不安全的整数区域，最后有可能成为 .知道了这一点，我就想知道......skipCountInfinity

• 在什么时候，此功能变得不可靠？
• 我有没有办法改进这个算法来弥补 JavaScript 的局限性？
• 有没有更好的选择？

请注意，我对概率的了解是有限的，我花了一周时间挖掘我几乎不理解的科学论文后编写了这段代码。我确实有另一种方法，但它的效率要低得多，并且需要将随机数生成与拼图生成逻辑混合在一起。