Линейный конгруэнтный метод excel

Обновлено: 05.07.2024

В этой статье описаны синтаксис формулы и использование функции LINEST в Microsoft Excel. Ссылки на дополнительные сведения о диаграммах и выполнении регрессионного анализа можно найти в разделе См. также.

Описание

Функция ЛИНЕЙН рассчитывает статистику для ряда с применением метода наименьших квадратов, чтобы вычислить прямую линию, которая наилучшим образом аппроксимирует имеющиеся данные и затем возвращает массив, который описывает полученную прямую. Функцию ЛИНЕЙН также можно объединять с другими функциями для вычисления других видов моделей, являющихся линейными по неизвестным параметрам, включая полиномиальные, логарифмические, экспоненциальные и степенные ряды. Поскольку возвращается массив значений, функция должна задаваться в виде формулы массива. Инструкции приведены в данной статье после примеров.

Уравнение для прямой линии имеет следующий вид:

y = m1x1 + m2x2 +. + b

если существует несколько диапазонов значений x, где зависимые значения y — функции независимых значений x. Значения m — коэффициенты, соответствующие каждому значению x, а b — постоянная. Обратите внимание, что y, x и m могут быть векторами. Функция ЛИНЕЙН возвращает массив . Функция ЛИНЕЙН может также возвращать дополнительную регрессионную статистику.

Синтаксис

ЛИНЕЙН(известные_значения_y; [известные_значения_x]; [конст]; [статистика])

Аргументы функции ЛИНЕЙН описаны ниже.

Синтаксис

Известные_значения_y. Обязательный аргумент. Множество значений y, которые уже известны для соотношения y = mx + b.

Если массив известные_значения_y имеет один столбец, то каждый столбец массива известные_значения_x интерпретируется как отдельная переменная.

Если массив известные_значения_y имеет одну строку, то каждая строка массива известные_значения_x интерпретируется как отдельная переменная.

Известные_значения_x. Необязательный аргумент. Множество значений x, которые уже известны для соотношения y = mx + b.

Массив известные_значения_x может содержать одно или несколько множеств переменных. Если используется только одна переменная, то массивы известные_значения_y и известные_значения_x могут иметь любую форму — при условии, что они имеют одинаковую размерность. Если используется более одной переменной, то известные_значения_y должны быть вектором (т. е. интервалом высотой в одну строку или шириной в один столбец).

Если массив известные_значения_x опущен, то предполагается, что это массив , имеющий такой же размер, что и массив известные_значения_y.

Конст. Необязательный аргумент. Логическое значение, которое указывает, требуется ли, чтобы константа b была равна 0.

Если аргумент конст имеет значение ИСТИНА или опущен, то константа b вычисляется обычным образом.

Если аргумент конст имеет значение ЛОЖЬ, то значение b полагается равным 0 и значения m подбираются таким образом, чтобы выполнялось соотношение y = mx.

Статистика. Необязательный аргумент. Логическое значение, которое указывает, требуется ли вернуть дополнительную регрессионную статистику.

Если статистика имеет true, то LINEST возвращает дополнительную регрессию; в результате возвращается массив .

Если аргумент статистика имеет значение ЛОЖЬ или опущен, функция ЛИНЕЙН возвращает только коэффициенты m и постоянную b.

Дополнительная регрессионная статистика.

Стандартные значения ошибок для коэффициентов m1,m2. mn.

Коэффициент определения. Сравнивает предполагаемые и фактические значения y и диапазоны значений от 0 до 1. Если значение 1, то в выборке будет отличная корреляция— разница между предполагаемым значением y и фактическим значением y не существует. С другой стороны, если коэффициент определения — 0, уравнение регрессии не помогает предсказать значение y. Сведения о том, как вычисляется 2, см. в разделе "Замечания" далее в этой теме.

Стандартная ошибка для оценки y.

F-статистика или F-наблюдаемое значение. F-статистика используется для определения того, является ли случайной наблюдаемая взаимосвязь между зависимой и независимой переменными.

Степени свободы. Степени свободы используются для нахождения F-критических значений в статистической таблице. Для определения уровня надежности модели необходимо сравнить значения в таблице с F-статистикой, возвращаемой функцией ЛИНЕЙН. Дополнительные сведения о вычислении величины df см. ниже в разделе "Замечания". Далее в примере 4 показано использование величин F и df.

Регрессионная сумма квадратов.

Остаточная сумма квадратов. Дополнительные сведения о расчете величин ssreg и ssresid см. в подразделе "Замечания" в конце данного раздела.

На приведенном ниже рисунке показано, в каком порядке возвращается дополнительная регрессионная статистика.

Замечания

Любую прямую можно описать ее наклоном и пересечением с осью y:

Наклон (m):
Чтобы найти наклон линии, обычно записанной как m, возьмите две точки на строке (x1;y1) и (x2;y2); наклон равен (y2 - y1)/(x2 - x1).

Y-перехват (b):
Y-пересечение строки, обычно записанное как b, — это значение y в точке, в которой линия пересекает ось y.

Уравнение прямой имеет вид y = mx + b. Если известны значения m и b, то можно вычислить любую точку на прямой, подставляя значения y или x в уравнение. Можно также воспользоваться функцией ТЕНДЕНЦИЯ.

Если имеется только одна независимая переменная x, можно получить наклон и y-пересечение непосредственно, воспользовавшись следующими формулами:

Наклон:
=ИНДЕКС( LINEST(known_y,known_x's);1)

Y-перехват:
=ИНДЕКС( LINEST(known_y,known_x),2)

Точность аппроксимации с помощью прямой, вычисленной функцией ЛИНЕЙН, зависит от степени разброса данных. Чем ближе данные к прямой, тем более точной является модель ЛИНЕЙН. Функция ЛИНЕЙН использует для определения наилучшей аппроксимации данных метод наименьших квадратов. Когда имеется только одна независимая переменная x, значения m и b вычисляются по следующим формулам:

где x и y — выборочные средние значения, например x = СРЗНАЧ(известные_значения_x), а y = СРЗНАЧ(известные_значения_y).

Функции ЛИННЕСТРОЙ и ЛОГЪЕСТ могут вычислять наилучшие прямые или экспоненциальное кривой, которые подходят для ваших данных. Однако необходимо решить, какой из двух результатов лучше всего подходит для ваших данных. Вы можетевычислить known_y(known_x) для прямой линии или РОСТ(known_y, known_x в) для экспоненциальной кривой. Эти функции без аргумента new_x возвращают массив значений y, спрогнозируемых вдоль этой линии или кривой в фактических точках данных. Затем можно сравнить спрогнозируемые значения с фактическими значениями. Для наглядного сравнения можно отобразить оба этих диаграммы.

Проводя регрессионный анализ, Microsoft Excel вычисляет для каждой точки квадрат разности между прогнозируемым значением y и фактическим значением y. Сумма этих квадратов разностей называется остаточной суммой квадратов (ssresid). Затем Microsoft Excel подсчитывает общую сумму квадратов (sstotal). Если конст = ИСТИНА или значение этого аргумента не указано, общая сумма квадратов будет равна сумме квадратов разностей действительных значений y и средних значений y. При конст = ЛОЖЬ общая сумма квадратов будет равна сумме квадратов действительных значений y (без вычитания среднего значения y из частного значения y). После этого регрессионную сумму квадратов можно вычислить следующим образом: ssreg = sstotal - ssresid. Чем меньше остаточная сумма квадратов по сравнению с общей суммой квадратов, тем больше значение коэффициента определения r 2 — индикатор того, насколько хорошо уравнение, выданное в результате регрессионного анализа, объясняет связь между переменными. Значение r 2 равно ssreg/sstotal.

В некоторых случаях один или несколько столбцов X (предполагается, что значения Y и X — в столбцах) могут не иметь дополнительного прогнозируемого значения при наличии других столбцов X. Другими словами, удаление одного или более столбцов X может привести к одинаковой точности предсказания значений Y. В этом случае эти избыточные столбцы X следует не использовать в модели регрессии. Этот вариант называется "коллинеарность", так как любой избыточный X-столбец может быть выражен как сумма многих не избыточных X-столбцов. Функция ЛИНЕЙН проверяет коллинеарность и удаляет все избыточные X-столбцы из модели регрессии при их идентификации. Удалены столбцы X распознаются в результатах LINEST как имеющие коэффициенты 0 в дополнение к значениям 0 se. Если один или несколько столбцов будут удалены как избыточные, это влияет на df, поскольку df зависит от числа X столбцов, фактически используемых для прогнозирования. Подробные сведения о вычислении df см. в примере 4. Если значение df изменилось из-за удаления избыточных X-столбцов, это также влияет на значения Sey и F. Коллинеарность должна быть относительно редкой на практике. Однако чаще всего возникают ситуации, когда некоторые столбцы X содержат только значения 0 и 1 в качестве индикаторов того, является ли тема в эксперименте участником определенной группы или не является ее участником. Если конст = ИСТИНА или опущен, функция LYST фактически вставляет дополнительный столбец X из всех 1 значений для моделирования перехвата. Если у вас есть столбец с значением 1 для каждой темы, если мальчик, или 0, а также столбец с 1 для каждой темы, если она является женщиной, или 0, последний столбец является избыточным, так как записи в нем могут быть получены из вычитания записи в столбце "самец" из записи в дополнительном столбце всех 1 значений, добавленных функцией LINEST.

Вычисление значения df для случаев, когда столбцы X удаляются из модели вследствие коллинеарности происходит следующим образом: если существует k столбцов известных_значений_x и значение конст = ИСТИНА или не указано, то df = n – k – 1. Если конст = ЛОЖЬ, то df = n - k. В обоих случаях удаление столбцов X вследствие коллинеарности увеличивает значение df на 1.

При вводе константы массива (например, в качестве аргумента известные_значения_x) следует использовать точку с запятой для разделения значений в одной строке и двоеточие для разделения строк. Знаки-разделители могут быть другими в зависимости от региональных параметров.

Следует отметить, что значения y, предсказанные с помощью уравнения регрессии, возможно, не будут правильными, если они располагаются вне интервала значений y, которые использовались для определения уравнения.

Основной алгоритм, используемый в функции ЛИНЕЙН, отличается от основного алгоритма функций НАКЛОН и ОТРЕЗОК. Разница между алгоритмами может привести к различным результатам при неопределенных и коллинеарных данных. Например, если точки данных аргумента известные_значения_y равны 0, а точки данных аргумента известные_значения_x равны 1, то:

Функция ЛИНЕЙН возвращает значение, равное 0. Алгоритм функции ЛИНЕЙН используется для возвращения подходящих значений для коллинеарных данных, и в данном случае может быть найден по меньшей мере один ответ.

Помимо вычисления статистики для других типов регрессии с помощью функции ЛГРФПРИБЛ, для вычисления диапазонов некоторых других типов регрессий можно использовать функцию ЛИНЕЙН, вводя функции переменных x и y как ряды переменных х и у для ЛИНЕЙН. Например, следующая формула:

работает при наличии одного столбца значений Y и одного столбца значений Х для вычисления аппроксимации куба (многочлен 3-й степени) следующей формы:

y = m1*x + m2*x^2 + m3*x^3 + b

Формула может быть изменена для расчетов других типов регрессии, но в отдельных случаях требуется корректировка выходных значений и других статистических данных.

Значение F-теста, возвращаемое функцией ЛИНЕЙН, отличается от значения, возвращаемого функцией ФТЕСТ. Функция ЛИНЕЙН возвращает F-статистику, в то время как ФТЕСТ возвращает вероятность.

Примеры

Пример 1. Наклон и Y-пересечение

Скопируйте образец данных из следующей таблицы и вставьте их в ячейку A1 нового листа Excel. Чтобы отобразить результаты формул, выделите их и нажмите клавишу F2, а затем — клавишу ВВОД. При необходимости измените ширину столбцов, чтобы видеть все данные.

На Хабре и в сети часто начали появляться статьи, посвященные уязвимостям генераторов случайных чисел. Данная тема крайне обширна и является одной из основных в криптографии. Под катом находится описание случайных чисел от A до Z. Статья является результатом свободного перевода цикла статей из одного западного блога и личных дополнений автора. Основная цель — получить feedback и поделиться знаниями.

Введение

Генераторы сессий (PHPSESSID)
Генерация текста для капчи
Шифрование
Генерация соли для хранения паролей в необратимом виде
Генератор паролей
Порядок раздачи карт в интернет казино

Как отличить случайную последовательность чисел от неслучайной?

Пусть есть последовательность чисел: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 . Является ли она случайной? Есть строгое определение для случайной величины. Случайная величина — это величина, которая принимает в результате опыта одно из множества значений, причём появление того или иного значения этой величины до её измерения нельзя точно предсказать. Но оно не помогает ответить на наш вопрос, так как нам не хватает информации для ответа. Теперь скажем, что данные числа получились набором одной из верхних строк клавиатуры. «Конечно не случайная» — воскликните Вы и тут же назовете следующие число и будете абсолютно правы. Последовательность будет случайной только если между символами, нету зависимости. Например, если бы данные символы появились в результате вытягивания бочонков в лото, то последовательность была бы случайной.

Чуть более сложный пример или число Пи

Последовательность цифры в числе Пи считается случайной. Пусть генератор основывается на выводе бит представления числа Пи, начиная с какой-то неизвестной точки. Такой генератор, возможно и пройдет «тест на следующий бит», так как ПИ, видимо, является случайной последовательностью. Однако этот подход не является критографически надежным — если криптоаналитик определит, какой бит числа Пи используется в данный момент, он сможет вычислить и все предшествующие и последующие биты.
Данный пример накладывает ещё одно ограничение на генераторы случайных чисел. Криптоаналитик не должен иметь возможности предсказать работу генератора случайных чисел.

Отличие генератора псевдослучайных чисел (ГПСЧ) от генератора случайных чисел (ГСЧ)

Источники энтропии используются для накопления энтропии с последующим получением из неё начального значения (initial value, seed), необходимого генераторам случайных чисел (ГСЧ) для формирования случайных чисел. ГПСЧ использует единственное начальное значение, откуда и следует его псевдослучайность, а ГСЧ всегда формирует случайное число, имея в начале высококачественную случайную величину, предоставленную различными источниками энтропии.
Энтропия – это мера беспорядка. Информационная энтропия — мера неопределённости или непредсказуемости информации.
Можно сказать, что ГСЧ = ГПСЧ + источник энтропии.

Уязвимости ГПСЧ

Предсказуемая зависимость между числами.
Предсказуемое начальное значение генератора.
Малая длина периода генерируемой последовательности случайных чисел, после которой генератор зацикливается.

Линейный конгруэнтный ГПСЧ (LCPRNG)

Распространённый метод для генерации псевдослучайных чисел, не обладающий криптографической стойкостью. Линейный конгруэнтный метод заключается в вычислении членов линейной рекуррентной последовательности по модулю некоторого натурального числа m, задаваемой следующей формулой:

где a (multiplier), c (addend), m (mask) — некоторые целочисленные коэффициенты. Получаемая последовательность зависит от выбора стартового числа (seed) X0 и при разных его значениях получаются различные последовательности случайных чисел.

Для выбора коэффициентов имеются свойства позволяющие максимизировать длину периода(максимальная длина равна m), то есть момент, с которого генератор зациклится [1].

Пусть генератор выдал несколько случайных чисел X0, X1, X2, X3. Получается система уравнений

Решив эту систему, можно определить коэффициенты a, c, m. Как утверждает википедия [8], эта система имеет решение, но решить самостоятельно или найти решение не получилось. Буду очень признателен за любую помощь в этом направлении.

Предсказание результатов линейно-конгруэнтного метода

Основным алгоритмом предсказания чисел для линейно-конгруэнтного метода является Plumstead’s — алгоритм, реализацию, которого можно найти здесь [4](есть онлайн запуск) и здесь [5]. Описание алгоритма можно найти в [9].
Простая реализация конгруэнтного метода на Java.

Отправив 20 чисел на сайт [4], можно с большой вероятностью получить следующие. Чем больше чисел, тем больше вероятность.

Взлом встроенного генератора случайных чисел в Java

Многие языки программирования, например C(rand), C++(rand) и Java используют LСPRNG. Рассмотрим, как можно провести взлом на примере java.utils.Random. Зайдя в исходный код (jdk1.7) данного класса можно увидеть используемые константы

Метод java.utils.Randon.nextInt() выглядит следующим образом (здесь bits == 32)

Пусть мы знаем два подряд сгенерированных числа x1 и x2. Тогда необходимо перебрать 2^16 = 65536 вариантов oldseed и применять к x1 формулу:

до тех пор, пока она не станет равной x2. Код для brute-force может выглядеть так

Несложно понять, что мы нашли не самый первый seed, а seed, используемый при генерации второго числа. Для нахождения первоначального seed необходимо провести несколько операций, которые Java использовала для преобразования seed, в обратном порядке.

И теперь в исходном коде заменим
crackingSeed.set(seed);
на
crackingSeed.set(getPreviousSeed(seed));

И всё, мы успешно взломали ГПСЧ в Java.

Взлом ГПСЧ Mersenne twister в PHP

Рассмотрим ещё один не криптостойкий алгоритм генерации псевдослучайных чисел Mersenne Twister. Основные преимущества алгоритма — это скорость генерации и огромный период 2^19937 − 1, На этот раз будем анализировать реализацию алгоритма mt_srand() и mt_rand() в исходном коде php версии 5.4.6.

Можно заметить, что php_mt_reload вызывается при инициализации и после вызова php_mt_rand 624 раза. Начнем взлом с конца, обратим трансформации в конце функции php_mt_rand(). Рассмотрим (s1 ^ (s1 >> 18)). В бинарном представление операция выглядит так:

10110111010111100111111001110010 s1
00000000000000000010110111010111100111111001110010 s1 >> 18
10110111010111100101001110100101 s1 ^ (s1 >> 18)
Видно, что первые 18 бит (выделены жирным) остались без изменений.
Напишем две функции для инвертирования битового сдвига и xor

Тогда код для инвертирования последних строк функции php_mt_rand() будет выглядеть так

Если у нас есть 624 последовательных числа сгенерированных Mersenne Twister, то применив этот алгоритм для этих последовательных чисел, мы получим полное состояние Mersenne Twister, и сможем легко определить каждое последующее значение, запустив php_mt_reload для известного набора значений.

Область для взлома

Если вы думаете, что уже нечего ломать, то Вы глубоко заблуждаетесь. Одним из интересных направлений является генератор случайных чисел Adobe Flash(Action Script 3.0). Его особенностью является закрытость исходного кода и отсутствие задания seed'а. Основной интерес к нему, это использование во многих онлайн-казино и онлайн-покере.
Есть много последовательностей чисел, начиная от курса доллара и заканчивая количеством времени проведенным в пробке каждый день. И найти закономерность в таких данных очень не простая задача.

Задание распределения для генератора псевдослучайных чисел

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

Треугольное распределение

Приведем пример генерации случайной величины с треугольным распределением [7] на языке C99.

В данном случае мы берем случайную величину rand() и задаем ей распределение, исходя из функции треугольного распределения. Для параметров a = -40, b = 100, c = 50 график 10000000 измерений будет выглядеть так

Экспоненциальное распределение

Пусть требуется получить датчик экспоненциально распределенных случайных величин. В этом случае F(x) = 1 – exp(-lambda * x). Тогда из решения уравнения y = 1 – exp(-lambda * x) получаем x = -log(1-y)/lambda.
Можно заметить, что выражение под знаком логарифма в последней формуле имеет равномерное распределение на отрезке [0,1), что позволяет получать другую, но так же распределённую последовательность по формуле: x = -log(y)/lambda, где y есть случайная величина(rand()).

Тесты ГПСЧ

Некоторые разработчики считают, что если они скроют используемый ими метод генерации или придумают свой, то этого достаточно для защиты. Это очень распространённое заблуждение. Следует помнить, что есть специальные методы и приемы для поиска зависимостей в последовательности чисел.

Одним из известных тестов является тест на следующий бит — тест, служащий для проверки генераторов псевдослучайных чисел на криптостойкость. Тест гласит, что не должно существовать полиномиального алгоритма, который, зная первые k битов случайной последовательности, сможет предсказать k+1 бит с вероятностью большей ½.

В теории криптографии отдельной проблемой является определение того, насколько последовательность чисел или бит, сгенерированных генератором, является случайной. Как правило, для этой цели используются различные статистические тесты, такие как DIEHARD или NIST. Эндрю Яо в 1982 году доказал, что генератор, прошедший «тест на следующий бит», пройдет и любые другие статистические тесты на случайность, выполнимые за полиномиальное время.
В интернете [10] можно пройти тесты DIEHARD и множество других, чтобы определить критостойкость алгоритма.

Довольно часто программисты в своей работе встречаются с необходимостью работать со случайными числами. Чаще всего случайные числа требуются в задачах моделирования, численного анализа и тестирования, но существует и множество других весьма специфических задач.
Конечно, во всех современных языках программирования есть функция random или её аналоги. Эти функции чаще всего дают действительно хорошие псевдослучайные числа, но мне всегда было интересно, как эти функции работают.
В этом топике я постараюсь объяснить, как работает линейный конгруэнтный метод (который чаще всего используется в функции random), и метод получения случайных чисел с помощью полиномиального счётчика (который часто используется для тестирования аппаратуры).

Введение

Сразу стоит сказать, что есть смысл генерировать случайные числа только с равномерным законом распределения, т.к. все остальные распределения можно получить из равномерного путём преобразований, известных из теории вероятности.
Для тех, кто забыл или пока не изучал теорию вероятности, напомню, что в равномерно распределённой последовательности нулей и единиц нули в среднем(!) будут встречаться в 50% случаев. Но это вовсе не значит, что в последовательности из 1000 цифр будет ровно 500 нулей. Более того, в последовательности из 1000 цифр может быть 999 нулей, и вероятность того, что тысячный элемент будет равен нулю по-прежнему остаётся равной 0.5. На первый взгляд это кажется парадоксальным, но важно понимать, что все последовательности равновероятны. Если же мы будем рассматривать достаточно большую совокупность таких последовательностей, то в среднем(!) в каждой из них будет 500 нулей.
Немного вспомнив теорию, мы перейдём к истории. В докомпьютерные времена случайные числа получали, вытаскивая разноцветные мячи из мешков, вытягивая карты, бросая кости. Понятно, что серьёзные исследования так проводить было нельзя, поэтому в 1927 года Типпетт опубликовал первую таблицу случайных чисел. Чуть позже люди попытались как-то автоматизировать этот процесс. Начали появляться машины, генерирующие случайные числа. Сейчас такие устройства тоже используются и называются источниками (генераторами) энтропии. Стоит заметить, что только такие устройства могут давать по-настоящему случайные числа. Но, к сожалению, генераторы энтропии довольно дороги, и не представляется возможным установить их в каждый ПК. Именно поэтому и возникла необходимость в алгоритмах получения случайных чисел.

Первая попытка получения ПСП

Некоторые люди думают, что получать случайные числа легко. По их мнению для этого достаточно делать случайные сложные математические действия над исходным числом. Если мы откроем второй том всем известного Кнута, то узнаем, что в 1959 Кнут тоже пробовал построить генератор, основанный на такой идее. Его алгоритм выглядел так:
К1. [Выбрать число итераций.] Присвоить Y наибольшую значащую цифру Х. (Мы выполним шаги К2-К13 точно Y+1 раз, т. е. применим рандомизированные преобразования случайное число раз.)
К2. [Выбрать случайный шаг] Присвоить следующую наибольшую значащую цифру X. Переходим к шагу К(3 + Z), т. е. к случайно выбранному шагу в программе.
КЗ. [Обеспечить > 5 х 109] Если X < 5000000000, присвоить X значение X + 5000000000.
К4. [Средина квадрата.] Заменить X серединой квадрата X.
К5. [Умножить.] Заменить X числом (1001001001 X) mod 1010.
К6. [Псевдодополнение.] Если X < 100000000, то присвоить X значение X + 9814055677; иначе присвоить X значение 1010- X.
К7. [Переставить половины.] Поменять местами пять младших по порядку знаков со старшими.
К8. [Умножить.] Выполнить шаг К5.
К9. [Уменьшить цифры.] Уменьшить каждую не равную нулю цифру десятичного представления числа X на единицу.
К10. [Модифицировать на 99999.] Если А' < 105, присвоить X значение — X 2 +99999; иначе присвоить X значение X — 99999.
К11. [Нормировать.] (На этом шаге А' не может быть равным нулю.) Если X <109, то умножить X на 10.
К12. [Модификация метода средин квадратов.] Заменить Х на средние 10 цифр числа Х(Х — 1).
К13. [Повторить?] Если Y > 0, уменьшить У на 1 и возвратиться к шагу К2. Если Y = 0, алгоритм завершен. Значение числа X, полученное на предыдущем шаге, и будет желаемым «случайным» значением.
Несмотря на кажущуюся сложность, этот алгоритм быстро сошёлся к числу 6065038420, которое через небольшое число шагов преобразовалось в себя же. Мораль этой истории в том, что нельзя использовать случайный алгоритм для получения случайных чисел.

Линейный конгруэнтный метод

Модуль m (m>0);
Множитель a (0<=a<m);
Приращение c (0<=c<m);
Начальное значение X₀ (0<= X₀<m)

Числа m,a,c, X₀ не должны быть случайными;
Линейный конгруэнтный метод даёт нам повторяющиеся последовательности.

Числа c и m взаимно простые;
a-1 кратно p для каждого простого p, являющегося делителем m;
Если m кратно 4, то и a-1 должно быть кратно 4.

Получение псевдослучайных чисел на основе полиномиального счетчика (сдвигового регистра)

В основе алгоритма, который мы сейчас рассмотрим, лежит операция исключающего ИЛИ (сумма по модулю два). На всякий случай, напомню, как выглядит таблица истинности для данной функции:

Схемы, представленные на рисунке ниже, являются простейшими полиномиальными счётчиками. Нулевой бит в таких схемах вычисляется на основе функции исключающего ИЛИ, а все остальные биты получаются простым сдвигом. Разряды с которых сигнал идёт на исключающее ИЛИ называются отводами.

Рассмотрим, как будут изменяться значения в этих регистрах при начальном значении 001:

Оба регистра начинают работу с одного и того же значения, но потом значения, генерируемые регистрами начинают быстро расходиться. Но через 6 шагов, оба регистра возвращаются в исходное состояние.
Легко показать, что оба этих регистра сгенерировали максимально длинную последовательность, которая содержит все комбинации, кроме нулевой. Т.е. при разрядности регистра m, можно получить последовательность длинной 2 m -1.
Полиномиальный счётчик любой разрядности имеет ряд комбинаций отводов, которые обеспечат последовательность максимальной длины, использование неверных комбинаций приведёт к генерации коротких последовательностей. Отдельная и довольно сложная задача – поиск этих комбинаций отводов.
Стоит заметить, что эти комбинации не всегда уникальны. К примеру, для 10-битного счётчика их существует две: [6;9] и [2;9], для шестиразрядного счётчика таких комбинаций двадцать восемь.
Для того, чтобы найти эти комбинации, необходимо представить счётчик в виде полинома. Счётчики из примера будут иметь следующий вид: x 2 XOR 1 и x 2 XOR x XOR 1.

В этой статье я покажу, как генерировать случайные числа с помощью четырех разных алгоритмов: алгоритма Лемера (Lehmer), линейного конгруэнтного алгоритма ( linear congruential algorithm), алгоритма Вичмана-Хилла (Wichmann-Hill) и алгоритма Фибоначчи с запаздываниями (lagged Fibonacci algorithm).

Хороший способ получить представление о том, куда я клоню в этой статье, — взглянуть на демонстрационную программу на рис. 1. Демонстрационная программа начинает с создания очень простого RNGЮ используя алгоритм Лемера. Затем с помощью RNG генерируется 1000 случайных целых чисел между 0 и 9 включительно. За кулисами записываются счетчики для каждого из сгенерированных целых чисел, которые потом отображаются на экране. Этот процесс повторяется для линейного конгруэнтного алгоритма, алгоритма Вичмана-Хилла и алгоритм Фибоначчи с запаздываниями.

Рис. 1. Демонстрация упрощенной генерации случайных чисел

Алгоритм Лемера

Самый простой приемлемый метод генерации случайных чисел — алгоритм Лемера. (Для простоты я использую термин «генерация случайных чисел» вместо более точного термина «генерация псевдослучайных чисел».) Выраженный в символьном виде, алгоритм Лемера представляет собой следующее:

На словах это звучит так: «новое случайное число является старым случайным числом, умножаемым на константу a, после чего над результатом выполняется операция по модулю константы m». Например, предположим, что в некий момент текущее случайное число равно 104, a = 3 и m = 100. Тогда новое случайное число будет равно 3 * 104 mod 100 = 312 mod 100 = 12. Вроде бы просто, но в реализации этого алгоритма много хитроумных деталей.

После загрузки кода шаблона в окно редактора я переименовал в окне Solution Explorer файл Program.cs в более описательный RandomNumbersProgram.cs, и Visual Studio автоматически переименовала класс Program за меня. В начале кода я удалил все лишние выражения using, оставив только ссылки на пространства имен верхнего уровня System и Collections.Generic.

Затем я добавил класс с именем LehmerRng для реализации RNG-алгоритма Лемера. Код показан на рис. 2. Версия алгоритма Лемера за 1988 год использует a = 16807 и m = 2147483647 (которое является int.MaxValue). Позднее, в 1993 году Лемер предложил другую версию, где a = 48271 как чуть более качественную альтернативу. Эти значения берутся из математической теории. Демонстрационный код основан на знаменитой статье С. К. Парка (S. K. Park) и К. У. Миллера (K. W. Miller) «Random Number Generators: Good Ones Are Hard to Find».

Рис. 2. Реализация алгоритма Лемера

Проблема реализации в том, чтобы предотвращать арифметическое переполнение. Алгоритм Лемера использует ловкий алгебраический трюк. Значение q является результатом m / a (целочисленное деление), а значение r равно m % a (m по модулю a).

При инициализации RNG Лемера начальным (зародышевым) значением можно использовать любое целое число в диапазоне [1, int.MaxValue – 1]. Многие RNG имеют конструктор без параметров, который получает системные дату и время, преобразует их в целое число и использует в качестве начального значения.

RNG Лемера вызывается в методе Main демонстрационной программы:

Каждый вызов метода Next возвращает значение в диапазоне [0.0, 1.0) — больше или равно 0.0 и строго меньше 1.0. Шаблон (int)(hi – lo) * Next + lo) будет возвращать целое число в диапазоне [lo, hi–1].

Алгоритм Лемера весьма эффективен, и в простых сценариях я обычно выбираю именно его. Но заметьте, что ни один алгоритм из представленных в этой статье не обладает надежностью криптографического уровня и что их следует применять только в ситуациях, где не требуется статической строгости (statistical rigor).

Алгоритм Вичмана-Хилла

Этот алгоритм датируется 1982 годом. Идея Вичмана-Хилла заключается в генерации трех предварительных результатов и последующего их объединения в один финальный результат. Код, реализующий алгоритм Вичмана-Хилла, представлен на рис. 3. Демонстрационный код основан на статье Б. А. Вичмана (B. A. Wichmann) и А. Д. Хилла (I. D. Hill) «Algorithm AS 183: An Efficient and Portable Pseudo-Random Number Generator».

Рис. 3. Реализация алгоритма Вичмана-Хилла

Поскольку алгоритм Вичмана-Хилла использует три разных генерирующих уравнения, он требует трех начальных значений. В этом алгоритме три m-значения равны 30269, 30307 и 30323, поэтому вам понадобятся три начальных значения в диапазоне [1, 30000]. Вы могли бы написать конструктор, принимающий эти три значения, но тогда вы получили бы несколько раздражающий программный интерфейс. В демонстрации применяется параметр с одним начальным значением, генерирующим три рабочих зародыша.

Вызов RNG Вичмана-Хилла осуществляется по тому же шаблону, что и других демонстрационных RNG:

Алгоритм Вичмана-Хилла лишь немного труднее в реализации, чем алгоритм Лемера. Преимущество первого над вторым в том, что алгоритм Вичмана-Хилла генерирует более длинную последовательность (более 6 000 000 000 000 значений) до того, как начнет повторяться.

Линейный конгруэнтный алгоритм

Оказывается, и алгоритм Лемера, и алгоритм Вичмана-Хилла можно считать особыми случаями так называемого линейного конгруэнтного алгоритма (linear congruential, LC). Выраженный в виде уравнения, LC выглядит так:

Это точно соответствует алгоритму Лемера с добавлением дополнительной константы c. Включение c придает универсальному LC-алгоритму несколько лучшие статистические свойства по сравнению с алгоритмом Лемера. Демонстрационная реализация LC-алгоритма показана на рис. 4. Код основан на стандарте POSIX (Portable Operating System Interface).

Рис. 4. Реализация линейного конгруэнтного алгоритма

LC-алгоритм использует несколько битовых операций. Здесь идея в том, чтобы в базовых математических типах работать не с целым типом (32 бита), а с длинным целым (64 бита). По окончании 32 из этих битов (с 16-го по 47-й включительно) извлекаются и преобразуются в целое число. Этот подход дает более качественные результаты, чем при использовании просто 32 младших или старших битов, но за счет некоторого усложнения кодирования.

В демонстрации генератор случайных чисел LC вызывается так:

Заметьте, что в отличие от генераторов Лемера и Вичмана-Хилла генератор LC может принимать начальное значение 0. Конструктор в демонстрации LC копирует значение входного параметра seed непосредственно в член класса — поле seed. Многие распространенные реализации LC выполняют предварительные манипуляции над входным начальным значением, чтобы избежать генерации хорошо известных серий начальных значений.

Алгоритм Фибоначчи с запаздываниями

Этот алгоритм, выраженный уравнением, выглядит так:

Если на словах, то новое случайное число является тем, которое было сгенерировано 7 раз назад, плюс случайное число, сгенерированное 10 раз назад, и деленное по модулю на большое значение m. Значения (7, 10) можно изменять, как я вскоре поясню.

Допустим, что в некий момент времени последовательность сгенерированных чисел следующая:

где 561 — самое последнее из сгенерированных значений. Если m = 100, то следующим случайным числом будет:

Заметьте, что в любой момент вам всегда нужны 10 самых последних сгенерированных значений. Поэтому ключевая задача в алгоритме Фибоначчи с запаздываниями состоит в генерации начальных значений, необходимых для запуска процесса. Демонстрационная реализация алгоритма Фибоначчи с запаздываниями приведена на рис. 5.

Рис. 5. Реализация алгоритма Фибоначчи с запаздываниями

Демонстрационный код использует предыдущие случайные числа X(i–7) и X(i–10) для генерации следующего случайного числа. В научно-исследовательской литературе по этой тематике значения (7, 10) обычно обозначаются (j, k). Существуют другие пары (j, k), которые можно применять для алгоритма Фибоначчи с запаздываниями. Несколько значений, рекомендованных в хорошо известной книге «Art of Computer Programming» (Addison-Wesley, 1968), — (24,55), (38,89), (37,100), (30,127), (83,258), (107,378).

Чтобы инициализировать (j, k) в RNG Фибоначчи с запаздываниями, вы должны предварительно заполнить список значениями k. Это можно сделать несколькими способами. Однако наименьшее из начальных значений k обязательно должно быть нечетным. В демонстрации применяется грубый метод копирования значения параметра seed для всех начальных значений k с последующим удалением первой 1000 сгенерированных значений. Если значение параметра seed четное, тогда первое из значений k выставляется равным 11 (произвольному нечетному числу).

Чтобы предотвратить арифметическое переполнение, метод Next использует тип long для вычислений и математическое свойство: (a + b) mod n = [(a mod n) + (b mod n)] mod n.

Заключение

Позвольте мне подчеркнуть, что все четыре RNG, представленные в этой статье, предназначены только для некритичных случаев применения. С учетом этого я прогнал все RNG через набор хорошо известных базовых тестов на степень случайности, и они прошли эти тесты. Но даже при этом коварство RNG всем хорошо известно, и время от времени даже в стандартных RNG обнаруживаются дефекты, иногда лишь спустя годы их использования. Например, в 1960-х годах IBM распространяла реализацию линейного конгруэнтного алгоритма под названием RANDU, которая, как оказалось, обладала невероятно плохими качествами. А в Microsoft Excel 2008 была выявлена ужасно проблемная реализация алгоритма Вичмана-Хилла.

Нынешний фаворит в генерации случайных чисел — алгоритм Фортуна (Fortuna) (названный в честь римской богини удачи). Алгоритм Фортуна был опубликован в 2003 году и основан на математической энтропии плюс сложных шифровальных методах, таких как AES (Advanced Encryption System).

Выражаю благодарность за рецензирование статьи экспертам Microsoft Крису Ли (Chris Lee) и Кирку Олинику (Kirk Olynyk).

Читайте также: