Pseudo-random_number_generators.cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <chrono>

// Класс линейного конгруэнтного генератора псевдослучайных чисел
class LCG {
public:
    using result_type = unsigned long long;

    // Конструктор: задаёт начальное состояние (seed) и параметры генератора A, C, M
    LCG(result_type seed,
        result_type a = 1664525ULL,
        result_type c = 1013904223ULL,
        result_type m = (1ULL << 32))
        : state(seed), A(a), C(c), M(m) {}

    // Метод next(): обновляет состояние и возвращает новое псевдослучайное число [0, M)
    result_type next() {
        state = (A * state + C) % M;
        return state;
    }

    // next_double(): получает число в диапазоне [0,1) на основе next()
    double next_double() {
        return static_cast<double>(next()) / static_cast<double>(M);
    }

    // reset(): сбрасывает состояние генератора на новый seed
    void reset(result_type seed) {
        state = seed;
    }

private:
    result_type state;         // текущее состояние (последнее сгенерированное число)
    const result_type A, C, M; // константы линейного конгруэнтного метода
};

// Хи-квадрат тест: проверка равномерности распределения в bins корзинах
void chi_square_test(LCG &gen, size_t N, size_t bins) {
    std::vector<size_t> counts(bins, 0);
    // Считаем, сколько точек попало в каждую корзину
    for (size_t i = 0; i < N; ++i) {
        size_t idx = static_cast<size_t>(gen.next_double() * bins);
        if (idx >= bins) idx = bins - 1;
        counts[idx]++;
    }

    // Вычисляем χ²-статистику
    double expected = static_cast<double>(N) / bins;
    double chi2 = 0;
    for (size_t c : counts) {
        chi2 += (c - expected) * (c - expected) / expected;
    }

    // Порог для уровня значимости α=0.05 и df=bins-1 (для bins=10 ~16.92)
    double threshold = 16.92;
    std::cout << "Chi-square = " << chi2
              << ", threshold ~ " << threshold
              << (chi2 < threshold ? ", равномерно" : ", неравномерно")
              << std::endl;
}

// Runs-тест: проверка числа серий (чередования выше/ниже медианы)
void runs_test(LCG &gen, size_t N) {
    // Начальное значение и подсчёт первой серии
    size_t runs = 1;
    size_t count_above = 0, count_below = 0;
    double first = gen.next_double();
    bool prev_above = (first > 0.5);
    prev_above ? ++count_above : ++count_below;

    // Считаем серии и общее число above/below
    for (size_t i = 1; i < N; ++i) {
        double u = gen.next_double();
        bool curr_above = (u > 0.5);
        curr_above ? ++count_above : ++count_below;
        if (curr_above != prev_above) {
            ++runs;           // новая серия при смене флага
            prev_above = curr_above;
        }
    }

    // Вычисляем ожидаемое число серий и дисперсию
    double n1 = count_above;
    double n2 = count_below;
    double expected = 1 + 2 * n1 * n2 / (n1 + n2);
    double var = (2 * n1 * n2 * (2 * n1 * n2 - n1 - n2)) /
                 ((n1 + n2) * (n1 + n2) * (n1 + n2 - 1));

    // Z-статистика
    double z = (runs - expected) / std::sqrt(var);

    std::cout << "Runs = " << runs
              << ", expected ~ " << expected
              << ", z = " << z
              << (std::abs(z) < 1.96 ? ", случайность" : ", зависимость")
              << std::endl;
}

int main() {
    // Параметры по умолчанию
    // Генерация динамического seed на основе текущего времени
    unsigned long long seed = std::chrono::high_resolution_clock::now()
                                .time_since_epoch().count();
    std::cout << "Seed = " << seed << std::endl;
    const size_t default_speed = 1000000; // длина последовательности по умолчанию
    const size_t bins = 10;               // число корзин для χ²-теста

    // Запрос у пользователя: либо указать длину, либо Enter для умолчания
    std::cout << "Введите скорость (число значений), либо нажмите Enter"
              << " для значения по умолчанию (" << default_speed << "): ";
    std::string line;
    std::getline(std::cin, line);

    // Обработка ввода: строка пуста → default_speed, иначе попытка преобразования
    size_t speed;
    if (line.empty()) {
        speed = default_speed;
    } else {
        try {
            speed = std::stoull(line);
        } catch (...) {
            std::cerr << "Неверный ввод, используется значение по умолчанию."
                      << std::endl;
            speed = default_speed;
        }
    }

    std::cout << "Используемая скорость: " << speed << std::endl;

    // Инициализируем генератор и выполняем тесты
    LCG gen(seed);
    std::cout << "Проверка качества LCG (seed=" << seed << ")" << std::endl;
    chi_square_test(gen, speed, bins);
    gen.reset(seed); // сброс к начальному состоянию для независимого теста
    runs_test(gen, speed);

    return 0;
}