---

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication3
{
    class Program
    {
        // Функция LFSR: возвращает [выходной_бит, новое_состояние]
        static uint[] LFSR(uint reg, int[] shift)
        {
            uint xor = reg & 1;
            uint o = xor;
            for (int i = shift.Length - 2; i >= 0; i--)
            {
                xor ^= (reg >> shift[i]) & 1;
            }
            reg = (reg >> 1) | (xor << shift[0]);
            return new uint[] { o, reg };
        }

        // Функция большинства для генератора Геффа
        static bool Geffe(uint b1, uint b2, uint b3)
        {
            bool x1 = (b1 & 1) == 1;
            bool x2 = (b2 & 1) == 1;
            bool x3 = (b3 & 1) == 1;
            return (x1 & x2) ^ (x1 & x3) ^ (x2 & x3);
        }

        static void Main(string[] args)
        {
            Console.OutputEncoding = Encoding.UTF8;

            // Инициализация регистров (вариант 1)
            uint reg1 = 43949;          // 16-битный
            uint reg2 = 181;            // 8-битный
            uint reg3 = 3613104981;     // 32-битный

            // Отводные последовательности
            int[] shifts1 = new int[5] { 15, 5, 3, 2, 0 };   // (16,5,3,2,0)
            int[] shifts2 = new int[4] { 7, 4, 3, 2, 0 };    // (8,4,3,2,0)
            int[] shifts3 = new int[5] { 31, 7, 6, 2, 0 };   // (32,7,6,2,0)

            // Периоды LFSR
            long period1 = (1L << 16) - 1;  // 65535
            long period2 = (1L << 8) - 1;   // 255
            long period3 = (1L << 32) - 1;  // 4294967295
            
            // Период генератора Геффа = НОК(period1, period2, period3)
            long totalPeriod = Lcm(Lcm(period1, period2), period3);
            Console.WriteLine("Теоретический период: " + totalPeriod + " бит");

            // Генерируем 1 000 000 бит (или меньше, если период меньше)
            int n = (int)Math.Min(totalPeriod, 1000000);
            Console.WriteLine("Генерируем " + n + " бит...");

            bool[] seq = new bool[n];
            for (int i = 0; i < n; i++)
            {
                // Получаем выходные биты
                uint[] rez1 = LFSR(reg1, shifts1);
                uint[] rez2 = LFSR(reg2, shifts2);
                uint[] rez3 = LFSR(reg3, shifts3);
                
                reg1 = rez1[1];
                reg2 = rez2[1];
                reg3 = rez3[1];

                // Выход генератора Геффа
                seq[i] = Geffe(rez1[0], rez2[0], rez3[0]);
            }

            Console.WriteLine("Генерация завершена. Запуск тестов...\n");

            // ============ СТАТИСТИЧЕСКИЕ ТЕСТЫ ============

            Console.WriteLine("=== СТАТИСТИЧЕСКИЕ ТЕСТЫ (α=0.05) ===\n");

            // 1. Частотный тест
            int n0 = seq.Count(x => !x);
            int n1 = n - n0;
            double X1 = (double)((n0 - n1) * (n0 - n1)) / n;
            double chi1 = 3.8415;
            Console.WriteLine("1. Частотный тест:");
            Console.WriteLine("   X1 = " + X1.ToString("F4") + ", порог = " + chi1);
            Console.WriteLine("   Результат: " + (X1 <= chi1 ? "ПРОЙДЕН ✓" : "НЕ ПРОЙДЕН ✗") + "\n");

            // 2. Тест на серии (двухразрядный)
            int n00 = 0, n01 = 0, n10 = 0, n11 = 0;
            for (int i = 0; i < n - 1; i++)
            {
                if (!seq[i] && !seq[i + 1]) n00++;
                else if (!seq[i] && seq[i + 1]) n01++;
                else if (seq[i] && !seq[i + 1]) n10++;
                else if (seq[i] && seq[i + 1]) n11++;
            }
            double X2 = 4.0 / (n - 1) * (n00 * n00 + n01 * n01 + n10 * n10 + n11 * n11) 
                        - 2.0 / n * (n0 * n0 + n1 * n1) + 1;
            double chi2 = 5.9915;
            Console.WriteLine("2. Тест на серии:");
            Console.WriteLine("   X2 = " + X2.ToString("F4") + ", порог = " + chi2);
            Console.WriteLine("   Результат: " + (X2 <= chi2 ? "ПРОЙДЕН ✓" : "НЕ ПРОЙДЕН ✗") + "\n");

            // 3. Обобщенный тест (m=3)
            int m = 3;
            int k = n / m;
            if (k < 5 * (1 << m))
            {
                Console.WriteLine("3. Обобщенный тест: недостаточно данных\n");
            }
            else
            {
                int patterns = 1 << m;
                int[] counts = new int[patterns];
                for (int i = 0; i < k; i++)
                {
                    int idx = 0;
                    for (int j = 0; j < m; j++)
                    {
                        idx = (idx << 1) | (seq[i * m + j] ? 1 : 0);
                    }
                    counts[idx]++;
                }
                double sum = 0;
                for (int i = 0; i < patterns; i++) sum += counts[i] * counts[i];
                double X3 = (double)patterns / k * sum - k;
                double chi3 = 14.0671;
                Console.WriteLine("3. Обобщенный тест (m=3):");
                Console.WriteLine("   X3 = " + X3.ToString("F4") + ", порог = " + chi3);
                Console.WriteLine("   Результат: " + (X3 <= chi3 ? "ПРОЙДЕН ✓" : "НЕ ПРОЙДЕН ✗") + "\n");
            }

            // 4. Тест на последовательности
            int K = 0;
            for (int i = 1; ; i++)
            {
                double e = (n - i + 3) / Math.Pow(2, i + 2);
                if (e < 5) break;
                K = i;
            }
            K = Math.Min(K, 10);
            
            double X4 = 0;
            for (int i = 1; i <= K; i++)
            {
                double e = (n - i + 3) / Math.Pow(2, i + 2);
                
                // Блоки (единицы)
                int blocks = 0, runLen = 0;
                for (int j = 0; j < n; j++)
                {
                    if (seq[j]) runLen++;
                    else { if (runLen == i) blocks++; runLen = 0; }
                }
                if (runLen == i) blocks++;
                
                // Промежутки (нули)
                int gaps = 0;
                runLen = 0;
                for (int j = 0; j < n; j++)
                {
                    if (!seq[j]) runLen++;
                    else { if (runLen == i) gaps++; runLen = 0; }
                }
                if (runLen == i) gaps++;
                
                X4 += (blocks - e) * (blocks - e) / e;
                X4 += (gaps - e) * (gaps - e) / e;
            }
            double chi4 = 9.4877;
            Console.WriteLine("4. Тест на последовательности:");
            Console.WriteLine("   X4 = " + X4.ToString("F4") + ", порог = " + chi4);
            Console.WriteLine("   Результат: " + (X4 <= chi4 ? "ПРОЙДЕН ✓" : "НЕ ПРОЙДЕН ✗") + "\n");

            // 5. Автокорреляционный тест
            int d = n / 4;
            if (d < 1) d = 1;
            if (n - d >= 10)
            {
                int A = 0;
                for (int i = 0; i < n - d; i++)
                {
                    if (seq[i] != seq[i + d]) A++;
                }
                double X5 = 2 * (A - (double)(n - d) / 2) / Math.Sqrt(n - d);
                double threshold = 1.96;
                Console.WriteLine("5. Автокорреляционный тест (d=" + d + "):");
                Console.WriteLine("   X5 = " + X5.ToString("F4") + ", порог = " + threshold);
                Console.WriteLine("   Результат: " + (Math.Abs(X5) <= threshold ? "ПРОЙДЕН ✓" : "НЕ ПРОЙДЕН ✗") + "\n");
            }
            else
            {
                Console.WriteLine("5. Автокорреляционный тест: n-d < 10, не применим\n");
            }

            Console.WriteLine("Нажмите любую клавишу для выхода...");
            Console.ReadKey();
        }

        // НОД
        static long Gcd(long a, long b)
        {
            while (b != 0)
            {
                long temp = b;
                b = a % b;
                a = temp;
            }
            return a;
        }

        // НОК
        static long Lcm(long a, long b)
        {
            return a / Gcd(a, b) * b;
        }
    }
}