18万亿次硬币抛掷，我哪里错了？ [关闭]

为什么以下 C 代码在运行相似版本 Linux 的桌面和服务器上给出不同的结果？

它在 18 万亿次抛硬币中找到连续序列中最长的同边。 [参见 Iain M. Banks 的科幻小说考虑弗莱巴斯.]

在服务器上，经过 15.7 万亿次硬币抛掷（仍在运行），到目前为止，行序列中最长的同边只有 29。2^44 = 17,592,186,044,416，我预计最长的同侧序列将在 40 左右，在 18 万亿已经完成之后可能是 44。

在桌面上，仅抛了 47 亿次硬币后，最长的序列就已经是 31，因为2^31 = 2,147,483,648，这听起来不错。

那么，为什么在 15.7 万亿次硬币抛掷后，我在服务器上得到的序列只有 29，而在我的桌面上只有 47 亿次硬币抛掷后，得到的序列却只有 31？

模偏差是我的第一个想法。RAND_MAX在桌面和服务器上都是相同的，2,147,483,647（32 位有符号长）。所以rand()函数会给我一个数字0 <= rand() <= 2,147,483,647。 0 是偶数，2,147,483,647 是奇数，所以除非我犯了很大的错误，否则我的方法不会引入模偏差int rand_num = (rand() % 2);行代码。

我知道 C 标准库的伪随机数生成器不被认为足以用于密码学。当然，在生成确实相当长的零和一序列时，这不可能成为一个因素。可以吗？

这是来源：

在两台机器上编译使用：gcc -O3 -o 18TCT 18TrillionCoinTosses.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(int argc, char* argv[])
{
    srand(time(NULL));

    int current_seq = 0;
    int longest_seq = 0;
    int prev_rand_num = -1;

    long long i = 0;
    long long total = 18000000000000;

    // To serve as a rudimentary progress indicator.
    long billion_counter = 0;
    long billion = 1000000000;

    while (i < total)
    {
        int rand_num = (rand() % 2);

        if (rand_num == prev_rand_num)
        {
            current_seq++;

            if (current_seq >= longest_seq)
            {
                longest_seq = current_seq;
                printf("Longest sequence so far: %d (on iteration %lli)\n", longest_seq, i);
            }
        }
        else
            current_seq = 1;

        if (billion_counter == billion)
        {
            billion_counter = 0;
            printf("Progress report, current iteration: %lli\n", i);
        }

        prev_rand_num = rand_num;

        i++;
        billion_counter++;
    }

    printf("\nTotal coins tossed: %lli\n", i);
    printf("Longest sequence: %d\n", longest_seq);
}

您的随机数生成器可能在 2^32 = 4294967296 次调用后重复，因此您并没有真正模拟 18 万亿次试验。您需要一个更好的 RNG，它可以保留超过 32 位的内部状态。在许多系统上，您只需调用即可访问更好的 RNGrandom()代替rand()。 （在我的系统上，man random说“随机——更好的随机数生成器”和“这个随机数生成器的周期非常大，大约为 16*((2**31)-1)”。虽然这“仅仅”是 34,359,738,352，但距离你的 18 万亿还差。）

另外，作为一个侧面，rand() % 2是有风险的，尽管现在大多数 RNG 都不存在会烧伤你的问题（如果你确实遇到了这个问题，你就会知道，因为除其他外，无论如何你都会连续得到 0） 。

附录：您可以在 C FAQ 列表中的问题 13.15 中找到一些其他更好的随机数生成器的参考：http://c-faq.com/lib/rand.html .