18万亿掷硬币，在哪里我会错呢？ [英] 18 trillion coin tosses, where did I go wrong?

问题描述

为什么下面的C code给我我的台式机和服务器，在Linux上运行两个版本相似的不同的结果？

它发现在18万亿掷硬币连续序列最长的同一侧。 [见伊恩M.银行科幻小说的考虑Phlebas 的。]

在服务器上，之后157000亿掷硬币（它仍在运行），在连续序列最长的同一侧，到目前为止只有29.自 2 ^ 44 = 17,592,186,044,416 ，我期望最长的同一侧顺序是40年年中的某处低，大概44毕竟18万亿已经完成。

在后只有4.7十亿掷硬币的最长序列已经是31，因为 2 ^ 31 = 2,147,483,648 ，并且敲响了桌面上是正确的。

所以，为什么我得到的只有29服务器上的序列之后157000亿掷硬币，但31只有4.7十亿我的桌面上后的顺序？

模偏置是我的第一个念头。 RAND_MAX 是台式机和服务器上的相同，2,147,483,647（32位带符号长）。因此，兰特（）功能会给我一个号码 0℃= RAND（）＆LT; = 2,147,483,647 。 0是偶数和2,147,483,647为奇数，所以，除非我非常错误的还有我的 INT rand_num =（RAND（）％2）推出无模偏置; $的行C $角

我知道C标准库的伪随机数生成不被认为是足够的加密。当然产生时，承认确实比较长，零和的序列是不可能是一个因素。莫非？

下面是源：

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

的#include＆LT;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;
＃包括LT＆;＆time.h中GT;INT主（INT ARGC，CHAR *的argv []）
{
    函数srand（时间（NULL））;    INT current_seq = 0;
    INT longest_seq = 0;
    INT prev_rand_num = -1;    长长的I = 0;
    长长的总= 180000亿;    //要作为一个基本的进度指示器。
    长billion_counter = 0;
    长十亿= 10亿;    而（I＆LT;全）
    {
        INT rand_num =（RAND（）％2）;        如果（rand_num == prev_rand_num）
        {
            current_seq ++;            如果（current_seq＆GT; = longest_seq）
            {
                longest_seq = current_seq;
                的printf（最长序列至今：％D（上迭代％LLI）\\ n，l​​ongest_seq，I）;
            }
        }
        其他
            current_seq = 1;        如果（billion_counter ==十亿）
        {
            billion_counter = 0;
            的printf（进展报告，当前迭代：％LLI \\ n，I）;
        }        prev_rand_num = rand_num;        我++;
        billion_counter ++;
    }    的printf（\\ n总计硬币扔给：％LLI \\ n，I）;
    的printf（最长序列数：％d \\ n，l​​ongest_seq）;
}


解决方案

您随机数发生器后2 ^ 32 = 4294967296电话可能重复，所以你没有真正模拟18万亿试验。你需要一个更好的RNG，一个信守内部状态的超过32位。在许多系统上，你可以通过简单地调用随机（）而不是的RAND（）访问一个更好的RNG 。 （在我的系统，人随机说随机 - 更好的随机数生成器和此随机数​​生成的周期是非常大的，大约16 *（（2 * * 31）-1）。虽然这是唯一的34359738352，这仍然是短期的18万亿的。）

此外，作为一个侧面来看，兰特（）％2 是有风险的，虽然大多数的RNG这些天没有问题，将燃烧你那里（如果你确实有这个问题，你知道的，因为除其他外你会在一排得0不管是什么）。

---

附录：您可以在问题13.15在C常见问题列表，以一些其他的，更好的随机数发生器引用： HTTP ：//c-faq.com/lib/rand.html

Why does the following C code gives me different results on my desktop and server, both running similar versions of Linux?

It finds the longest same side in a row sequence in 18 trillion coin tosses. [See Iain M. Banks' science fiction novel Consider Phlebas.]

On the server, after 15.7 trillion coin tosses (it's still running), the longest same side in a row sequence so far is only 29. Since 2^44 = 17,592,186,044,416, I'd expect the longest same side sequence to be somewhere in the low to mid 40's, and probably 44 after all 18 trillion have been completed.

On the desktop after only 4.7 billion coin tosses the longest sequence was already 31, since 2^31 = 2,147,483,648, and that sounded about right.

So why have I got a sequence of only 29 on the server after 15.7 trillion coin tosses but a sequence of 31 after only 4.7 billion on my desktop?

Modulo bias was my first thought. RAND_MAX is the same on both desktop and server, 2,147,483,647 (a 32 bit signed long). So the rand() function will give me a number 0 <= rand() <= 2,147,483,647. 0 is even and 2,147,483,647 is odd, so unless I'm very much mistaken there's no modulo bias introduced by my int rand_num = (rand() % 2); line of code.

I know that the C standard library's pseudo-random number generator is not considered adequate for cryptography. Surely that could not be a factor when generating, admittedly really rather long, sequences of zeros and ones. Could it?

Here's the source:

Compiled on both machines using: 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);
}

解决方案

Your random number generator is probably repeating after 2^32 = 4294967296 calls, so you're not really simulating 18 trillion trials. You need a better RNG, one that keeps more than 32 bits of internal state. On many systems, you can access a better RNG by simply calling random() instead of rand(). (On my system, man random says "random -- better random number generator" and "The period of this random number generator is very large, approximately 16*((2**31)-1)". Although that's "only" 34,359,738,352, which is still short of your 18 trillion.)

Also, as a side point, rand() % 2 is risky, although most RNGs these days don't have the problem that will burn you there (and if you did have that problem, you'd know it, because among other things you'd get 0 in a row no matter what).

---

Addendum: You can find references to some other, better random-number generators at question 13.15 in the C FAQ list: http://c-faq.com/lib/rand.html .

这篇关于18万亿掷硬币，在哪里我会错呢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！