Тесты на проверку случайности последовательности - C (СИ)
Формулировка задачи:
Добрый день!
Мне нужно проверить последовательность, выдаваемую линейным конгруэнтным генератором, одним из тестов Дональда Кнута. Выбрала Критерий сериальной корреляции.
Но в той формуле, которую дает Кнут, никак не могу разобраться.
1) Если под членами U подразумеваются члены последовательности, то что есть V?
2) n - есть количество чисел, которые я генерирую?
3) Нет ли где-нибудь реализованных тестов Кнута? По коду легче будет разобраться...
Решение задачи: «Тесты на проверку случайности последовательности»
textual
Листинг программы
const int M=N; unsigned int null_num, first_num, numerator_n, numerator_2, denominator_n, denominator_2; long double C; null_num = (a*x+c)%4294967296; numerator_n=0; numerator_2 = null_num; denominator_n = null_num*null_num; for (i=0; i<M; i++) { first_num = (a*null_num+c)%4294967296; numerator_n = numerator_n + null_num*first_num; numerator_2 = numerator_2 + first_num; denominator_n = denominator_n + first_num*first_num; null_num = first_num; } numerator_n = numerator_n + null_num*((a*x+c)%4294967296); numerator_2 = numerator_2 + null_num; denominator_2 = numerator_2; denominator_n = denominator_n + null_num*null_num; C = (double)((numerator_n*M)-(numerator_2*numerator_2))/(double)((denominator_n*M)-(denominator_2*denominator_2)); printf("Coefficient: %f \n\n", C);
Объяснение кода листинга программы
- В первой строке объявляются переменные: const int M=N; unsigned int null_num, first_num, numerator_n, numerator_2, denominator_n, denominator_2; long double C;
- Вторая строка вычисляет null_num: null_num = (a*x+c)%4294967296;
- Третья и четвертая строки вычисляют numerator_n и numerator_2: numerator_n=0; numerator_2 = null_num;
- Пятая и шестая строки вычисляют denominator_n: denominator_n = null_num*null_num;
- Затем следует цикл for, который выполняется M раз: for (i=0; i<M; i++) { first_num = (anull_num+c)%4294967296; numerator_n = numerator_n + null_numfirst_num; numerator_2 = numerator_2 + first_num; denominator_n = denominator_n + first_num*first_num; null_num = first_num; }
- После цикла for вычисляются numerator_n и numerator_2: numerator_n = numerator_n + null_num((ax+c)%4294967296); numerator_2 = numerator_2 + null_num;
- Затем вычисляются denominator_2 и denominator_n: denominator_2 = numerator_2; denominator_n = denominator_n + null_num*null_num;
- В последней строке вычисляется C: C = (double)((numerator_nM)-(numerator_2numerator_2))/(double)((denominator_nM)-(denominator_2denominator_2));
- И наконец, результат выводится на экран:
printf(
Coefficient: %f \n\n
, C); - Код завершается.