18万亿投掷硬币，我哪里出错了？
为什么以下C代码在我的桌面和服务器上给出了不同的结果，两者都运行类似的Linux版本？
它在18万亿投币中发现行序列中最长的同一侧。 [见Iain M. Banks的科幻小说考虑Phlebas 。]
在服务器上，经过15.7万亿投币（它仍然在运行）之后，到目前为止，行序列中最长的同一侧只有29个。由于2^44 = 17,592,186,044,416 ，我希望最长的相同边序列在某个地方。 40到40年代中期，在完成所有18万亿之后可能达到44。
在仅仅47亿次投掷硬币之后的桌面上，最长的序列已经是31，因为2^31 = 2,147,483,648 ，这听起来是正确的。
那么为什么我在15.7万亿投币后只在服务器上获得了29个序列，但是在我的桌面上只有47亿的31个序列？
Modulo偏见是我的第一个想法。 桌面和服务器上的RAND_MAX是相同的，2,147,483,647（32位签名长）。 所以rand()函数会给我一个数字0 <= rand() <= 2,147,483,647 。 0是偶数，2,147,483,647是奇数，所以除非我非常误以为我的int rand_num = (rand() % 2);引入了模数偏差int rand_num = (rand() % 2); 代码行。
我知道C标准库的伪随机数生成器不适合加密。 当然，这不是一个因素，当然，实际上相当长，零和一系列的序列。 可以吗？
这是来源：
使用以下两种机器编译： gcc -O3 -o 18TCT 18TrillionCoinTosses.c
#include #include #include 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 = 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位内部状态的RNG。 在许多系统上，只需调用random()而不是rand()即可访问更好的RNG。 （在我的系统上， 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 。
即使你的“随机”位0具有相等的零和1，伪随机生成器函数rand()序列也会相对频繁地重复。 在我的测试中，它在循环的2147483648（2 ** 31）次迭代后重复。 所以没有必要达到18万亿。 我跑了几次测试，结果总是一样。
#include #include #include int main(void) { unsigned long long n = 0; int a, b, c, d; int e, f, g, h; srand((unsigned)time(NULL)); e = a = rand(); f = b = rand(); g = c = rand(); h = d = rand(); do { n++; e = f; f = g; g = h; h = rand(); } while (e != a || f != b || g != c || h != d); printf("%llu\n", n); }
你的代码似乎没问题。 问题可能是您正在使用的RNG。
我不认为rand（）％2是统一的。 看看这里：以N为模的随机数的均匀性
为什么不使用C ++ 11随机数生成器？ http://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution
最后但并非最不重要的是，-O3可能会搞砸什么？
-O3优化更多。 -O3打开-O2指定的所有优化，并打开-finline-functions，-funswitch-loops，-fpredictive-commoning，-fgcse-after-reload，-ftree-loop-vectorize，-ftree-loop-distribute -patterns，-fsplit-paths -ftree-slp-vectorize，-fvect-cost-model，-ftree-partial-pre和-fipa-cp-clone选项。
正如其他人所指出的那样， rand不是随机性的可靠来源。 它就在手册页中 ：
NAME rand, rand_r, srand, sranddev -- bad random number generator ... DESCRIPTION These interfaces are obsoleted by arc4random(3).
为了获得良好的随机性，您必须超出标准C库。
- arc4random ，建议替换。
- drand48
- OpenSSL的RAND_bytes是加密安全的，但可能很难使用。 这是一个如何使用它的一个很好的例子 。
- PCG ， Mersenne Twist的替代品
请注意，如果您使用的是Mac，则会抱怨RAND_bytes()已弃用。 别担心，OpenSSL不会去任何地方，并且可以使用。 在升级Apple产品时，弃用与二进制兼容性问题有关 。