18 трлн монетных монет, где я ошибся?

Question

Почему следующий код C дает мне разные результаты на моем рабочем столе и сервере, оба работают с аналогичными версиями Linux?

Он находит самую длинную ту же сторону в последовательности строк в 18 трлн монетных бросков. [См Iain M. банков научной фантастики роман Рассмотрим Флебе.]

На сервере, после того, как 15,7 триллионов бросков монеты (он все еще работает), самую длинную сторону в той же последовательности строк до сих пор только 29. Так как 2^44 = 17,592,186,044,416, я ожидал бы, что самая длинная такая же последовательность будет находиться где-то в середине до середины 40-х годов, и, вероятно, 44 после завершения всего 18 триллионов.

На рабочем столе после того, как только 4,7 миллиарда монет бросает самую длинную последовательность, было уже 31, с 2^31 = 2,147,483,648, и это звучало о праве.

Итак, почему я получил последовательность из 29 на сервере после 15,7 трлн монет, но последовательность из 31 после всего лишь 4,7 млрд. На моем рабочем столе?

Modulo bias была моей первой мыслью. 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); 
} 

Answer 1

Ваш код, кажется, хорошо. Проблема может заключаться в том, что вы используете RNG.

Я не думаю, что rand()% 2 является единообразным. Посмотрите здесь: Uniformity of random numbers taken modulo N

Почему не C++ 11 Генераторы случайных чисел? http://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution

И последнее, но не менее важное: smogло -O3 испортить что-то?

-O3 Оптимизируйте еще больше. -O3 включает все оптимизации, заданные -O2, а также включает -finline-functions, -funswitch-loops, -fpredictive-commoning, -fgcse-after-reload, -ftree-loop-vectorize, -ftree-loop-distribute -патроны, -fsplit-paths -ftree-slp-vectorize, -fvect-cost-model, -free-partial-pre и -fipa-cp-clone.

Answer 2

Несмотря на то, что ваш «случайный» бит 0 имеет одинаковые нули и единицы, последовательность псевдослучайных генераторов rand() повторяется относительно часто. В моем тесте он повторяется после 2147483648 (2 ** 31) итераций цикла. Таким образом, нет смысла собираться до 18 триллионов. Я провел тест несколько раз, всегда тот же результат.

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

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); 
} 

Answer 3

Ваш генератор случайных чисел, вероятно, повторяя через 2^32 = 4294967296 звонков, так что вы на самом деле не имитируя 18 триллионов испытаний. Вам нужен лучший RNG, который хранит более 32 бит внутреннего состояния. На многих системах вы можете получить доступ к лучшему RNG, просто позвонив random() вместо rand(). (В моей системе man random говорит «случайный - лучший генератор случайных чисел» и «Период этого генератора случайных чисел очень большой, приблизительно 16 * ((2 ** 31) -1)». Хотя это «только» 34 359 738 352 , который по-прежнему не соответствует вашим 18 триллионам.)

Кроме того, в качестве побочного пункта rand() % 2 является рискованным, хотя в настоящее время большинство ГСЧ не имеют проблемы, которые сжигают вас там (и если у вас есть эта проблема , вы это знаете, потому что среди прочего вы получите 0 в строке, независимо от того, что).

---

Добавления: Вы можете найти ссылки на некоторые другие, лучше генераторы случайных чисел на вопросе 13.15 в списке Справки C: http://c-faq.com/lib/rand.html.

Answer 4

Как указывали другие, rand не является надежным источником случайности. Это прямо в the man page:

NAME 
    rand, rand_r, srand, sranddev -- bad random number generator 

... 

DESCRIPTION 
    These interfaces are obsoleted by arc4random(3). 

Для хорошей хаотичности вам придется выйти за пределы стандартных библиотек C.

• arc4random, предлагаемая замена.
• drand48
• OpenSSL's RAND_bytes является криптографически безопасным, но может быть трудно использовать. Here is a good example of how to use it.
• PCG, замена для Mersenne Twist

Обратите внимание, что если вы на Mac он будет жаловаться, что RAND_bytes() осуждается. Не волнуйтесь, OpenSSL никуда не денется и подходит. The deprecation has to do with binary compatibility issues when upgrading Apple products.