在没有 bignum 库的情况下生成 32 字节随机数据范围内的随机数

Question

我有 32 个字节的随机数据。

我想在 0-9 和 0-100 之间的可变范围内生成随机数。

如果我使用任意精度算术 (bignum) 库，并将 32 个字节视为一个大数字，我可以简单地这样做：

random = random_source % range;
random_source = random_source / range;

随心所欲（使用不同的范围），直到范围的乘积接近 2^256。

有没有办法只使用（固定大小的）整数运算来做到这一点？

Answer 1

/*  The 32 bytes in data are treated as a base-256 numeral following a "." (a
    radix point marking where fractional digits start).  This routine
    multiplies that numeral by range, updates data to contain the fractional
    portion of the product, and returns the integer portion.

    8-bit bytes are assumed, or "t /= 256" could be changed to
    "t >>= CHAR_BIT". But then you have to check the sizes of int
    and unsigned char to consider overflow.
*/
int r(int range, unsigned char *data)
{
    // Start with 0 carried from a lower position.
    int t = 0;

    // Iterate through each byte.
    for (int i = 32; 0 < i;)
    {
        --i;

        // Multiply next byte by our multiplier and add the carried data.
        t = data[i] * range + t;

        // Store the low bits of the result.
        data[i] = t;

        // Carry the high bits of the result to the next position.
        t /= 256;
    }

    // Return the bits that carried out of the multiplication.
    return t;
}

Answer 2

当然你可以通过 base 256 long division（或上推乘法）来做到这一点。它就像你在小学学习的长 division，但用字节而不是数字。它涉及对每个字节依次进行 divide 和余数的级联。请注意，您还需要了解您是如何使用大数字的，并且当您使用它并且它变小时，对范围内较大值的偏差会增加。例如，如果您只剩下 110，并且您要求 rnd(100)，则值 0-9 的可能性比 10-99 高 10%。

但是，您实际上并不需要 bignum 技术，您可以使用 ideas 来自算术编码压缩，您可以在其中构建单个数字，而无需实际处理整个事情。

如果您首先将 4 个字节读取到无符号 uint_32 缓冲区，则它的范围为 0..4294967295，不包括最大值 4294967296。我将此合成值称为 "carry forward"，这个唯一的最大值也很重要，需要记录。

[为简单起见，您可以从读取 3 个字节到缓冲区开始，最多生成 16M。这避免了必须处理不能保存在 32 位整数中的 4G 值。]

有 2 种使用方法，都具有准确性影响：

向下流：

做你的 modulo 范围。 modulo 是您的随机答案。 division 结果是您的新结转结果，范围更小。
假设你想要 0..99，所以你 modulo 100，你的上半部分的范围最大为 42949672 (4294967296/100)，你可以为下一个随机请求结转我们还不能再输入一个字节...
假设你现在想要 0..9，所以你 modulo 乘以 10，现在你的上半部分的范围是 0..4294967 (42949672/100)
由于 max 小于 16M，我们现在可以引入下一个字节。将它乘以当前最大值 4294967 并将其添加到结转中。最大值也乘以 256 -> 1099511552

这个方法对小值有轻微的偏向，因为1在"next max"次，可用值范围不会是全范围，因为最后一个值被截断了，但是通过选择保持最多 3-4 个好字节，偏差最小化。它只会在 1600 万次中最多出现 1 次。

该算法的计算成本是 div 乘以 carried forward 和 max 的随机范围，然后每次输入新字节时乘以。我假设编译器会优化 modulo

向上流：
假设你想要 0..99
Divide 你的最大范围，得到下一个最大值，然后 divide 由下一个最大值结转。现在，您的随机数在 division 结果中，余数构成您结转以获得下一个随机数的值。
当 nextmax 小于 16M 时，只需将 nextmax 和您的结转乘以 256 并添加下一个字节。
downside 如果这个方法是依赖于 division 用于生成 nextmax，最高值结果（即 99 或 9）严重偏向，或者有时你会生成超值(100) - 这取决于你是向上还是向下进行第一个 division。

此处的计算成本再次为 2 divides，假设编译器优化器混合了 div 和 mod 操作。乘以 256 很快。

在这两种情况下，您都可以选择说如果输入结转值在此 "high bias range" 中，那么您将执行不同的技术。您甚至可以在这两种技术之间摇摆不定——优先使用第二种，但如果它产生超值，则使用第一种技术，尽管就其本身而言，这两种技术在结转时可能会偏向于相似的输入随机流值接近最大值。可以通过使第二种方法生成 -1 作为超出范围来减少这种偏差，但是这些修复中的每一个都增加了一个额外的乘法步骤。

请注意，在算术编码中，当每个符号被提取时，这个溢出区域被有效地丢弃了。在解码期间保证不会出现这些边缘值，这会导致轻微的次优压缩。

在没有 bignum 库的情况下生成 32 字节随机数据范围内的随机数

Generating random numbers in ranges from 32 bytes of random data, without bignum library

c

bignum