Как я могу заставить OSD rand() пропустить спектральный тест?

Для класса программирования я пытаюсь проиллюстрировать слабые места генераторов случайных чисел, которые обычно поставляются со стандартной библиотекой C, в частности "плохой случайный генератор" rand(), который поставляется с OSX (quoth manpage).

Я написал простую программу для проверки моего понимания спектрального теста:

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

int main() {
  int i;
  int prev = rand();
  int new;

  for (i=0; i<100000; i++) {
    new = rand();
    printf("%d %d\n", prev, new);
    prev = new;
  }
  return 0;
}

Но когда я рисую полученную диаграмму рассеяния, вот что я получаю:

Я бы ожидал, что что-то покажет больше структуры, как то, что можно найти в Википедии. Я здесь что-то не так? Должен ли я рисовать в больших размерах?

UPDATE

Следуя предложению pjs, я увеличил часть участка, где числа меньше 1e7, и вот что я нашел:

Я нахожу точно такие же строки, показанные pjs. Они кажутся вертикальными, но это невозможно, поскольку это подразумевает, что некоторые значения были "пропущены" на rand(). Когда я sort -n данные, это (образец), что я вижу:

571 9596797
572 9613604
575 9664025
578 9714446
580 9748060
581 9764867
584 9815288
586 9848902
587 9865709
590 9916130
592 9949744
127774 13971
127775 30778
127780 114813
127781 131620
127782 148427
127783 165234
127785 198848
127787 232462
127788 249269

Другими словами, точки лежат в прямых, но не совсем вертикальных.

Ответ 1

Линейные конгруэнтные генераторы страдают от проблемы, идентифицированной Джорджем Марсалья. "Теорема Марсалья" говорит, что k-кортежи (векторы длины k) будут падать на ограниченное число гиперплоскостей. Оценка m**(1/k), где k - размер кортежа, а m - число, используемое для модуля генератора. Таким образом, если модуль равен (2**31 - 1), и вы смотрите на множества из 3, трехмерный график покажет, что точки падают не более, чем корень куба (2**31 - 1) или около 1290 плоскостей, если смотреть с правая ориентация.

Все LCG подчиняются теореме Марсалья. "Хороший", выполняемый на верхней границе или близкий к ней, плохой, хорошо отстает от верхней границы. То, что спектральный тест эффективно измеряет, и то, что вы видели в своей ссылке в Википедии - RANDU, LCG из ада, производит триплеты, которые попадают в 15 самолетов.

Генератор библиотеки углерода Apple использует 16807 в качестве своего множителя и (2**31 - 1) в качестве своего модуля. Поскольку LCG идет, это не совсем так плохо. Следовательно, ваш сюжет не показал те же крайности, что и у RANDU. Однако, если вы хотите, чтобы качественные случайные числа не использовали LCG,

Добавление

Я пошел вперед и свернул миллиард чисел из функции Apple rand(), но напечатал только те, где оба значения пары были менее 2 миллионов, т.е. нижний левый угол вашего сюжета. Разумеется, они падают на линии. Вам просто нужно увеличить масштаб, чтобы увидеть его из-за плотности линий.

Старый Джордж был умным человеком!

Ответ 2

Предполагая, что bad rand является линейным конгруэнтным генератором, то есть его вида:

next = a * prev + b (mod RAND_MAX+1)

вы можете просто взять несколько терминов и решить уравнения для a и b. После этого вы должны иметь возможность генерировать функцию вывода, чтобы структура стала очевидной.