Тест на случайность Кнута (критерий сериальной корреляции)

#c #тестирование

Добрый день! Мне нужно реализовать один из тестов Кнута. Выбрала критерий сериальной
корреляции. Во втором томе Кнута дается формула 



Я пытаюсь по ней вычислить этот коэффициент корреляции и он у меня получается при
N=50 равный 1,04. Но он не может быть, по модулю, больше единицы!... Помогите, пожалуйста,
разобраться...



Кусочек кода:

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

Ответы
Ответ 1

Ваш тест неверно реализован.
Делайте что-то такое:
double sumUV = 0, sumU = 0, sumV = 0, sumU2 = 0, sum V2 = 0;
for (int i = 0; i < n; i++)
{
    double u = GetNextU(i);
    double v = GetNextV(i);

    sumU += u; sumV += v;
    sumU2 += u*u; sumV2 += v*v;
    sumUV += u*v;
}
double coeff = (n * sumUV - sumU * sumV) /
          sqrt((n * sumU2 - sumU * sumU) * (n * sumV2 - sumV * sumV));

Это, к сожалению, достаточно наивный код: из-за неточности при округлении результат
может оказаться катастрофически неточен. О подробностях читайте в Кнуте, 4.2.2. Пример
после формулы (15) показывает, что при вычислении корня в знаменателе вы можете столкнуться
с отрицательным числом, несмотря на то, что это математически невозможно.

Апдейт. С новой формулой у вас V_i = U_{i+1}, вы считаете корреляцию последовательности
на себя. Код можно упростить.
double sumU = 0, sumU2 = 0, sumUShifted = 0;
double firstU = GetNextU(0);
double prevU = firstU;
for (int i = 0; i < n; i++)
{
    double nextU = i == (n - 1) ? firstU : GetNextU(i + 1);

    sumU += prevU;
    sumU2 += prevU*prevU;
    sumUShifted += prevU*nextU;

    prevU = nextU;
}
double coeff = (n * sumUShifted - sumU * sumU) / (n * sumU2 - sumU * sumU);