Джордж Марсалья

Джордж Марсалья (англ. George Marsaglia; 12 марта 1924, Бойсе, Айдахо — 15 февраля 2011, Таллахасси, Флорида) — американский математик и статистик, известный своими работами в области генерации псевдослучайных чисел и компьютерной статистики. Разработал ряд широко используемых алгоритмов, включая тест на случайность «Diehard» и генератор случайных чисел «MWC» (Multiply-with-Carry).

Биография

Джордж Марсалья родился 12 марта 1924 года в городе Бойсе, штат Айдахо. Во время Второй мировой войны служил в Военно-воздушных силах США. После войны получил степень бакалавра в Университете Айдахо, а затем магистерскую и докторскую степени в Университете штата Огайо. Докторскую диссертацию по математической статистике защитил в 1950 году.

В 1950-х годах работал в компании Boeing, где занимался статистическими методами контроля качества. В 1957 году перешёл в Университет штата Вашингтон, где начал активные исследования в области случайных чисел. В 1964 году стал профессором Университета Флориды в Таллахасси, где проработал до выхода на пенсию в 1994 году. В 1995 году ему было присвоено звание заслуженного профессора (Professor Emeritus). Умер 15 февраля 2011 года в Таллахасси.

Научные достижения

Генерация псевдослучайных чисел

Марсалья внёс фундаментальный вклад в теорию и практику генерации псевдослучайных чисел. Он разработал несколько классов генераторов, которые отличались высокой скоростью работы и хорошими статистическими свойствами.

Генератор «Multiply-with-Carry» (MWC)

В 1991 году Марсалья предложил метод «Multiply-with-Carry» (MWC). Этот генератор основан на рекуррентной формуле:

\[ x_n = (a \cdot x_{n-1} + c_{n-1}) \mod m \]

где \(c_n\) — перенос (carry), вычисляемый как \(c_n = \lfloor (a \cdot x_{n-1} + c_{n-1}) / m \rfloor\). Параметр \(a\) — множитель, \(m\) — модуль (обычно степень двойки). Генератор MWC сочетает простоту реализации с длинным периодом (до \(2^{60}\) и более) и хорошими статистическими свойствами.

Генератор «KISS» (Keep It Simple Stupid)

В 1990-х годах Марсалья разработал семейство генераторов KISS, которые комбинировали несколько простых алгоритмов (например, MWC, сдвиговый регистр и линейный конгруэнтный генератор) для получения последовательностей с очень длинным периодом (порядка \(2^{123}\)) и высокой степенью случайности. Генераторы KISS широко использовались в научных расчётах и симуляциях.

Генератор «Mother of All» (или «Mother»)

В 1993 году Марсалья представил генератор «Mother of All» (также известный как «Mother»), основанный на комбинации двух MWC-генераторов. Этот генератор имел период около \(2^{128}\) и был одним из первых, предложенных для использования в криптографических целях, хотя впоследствии были выявлены некоторые уязвимости.

Тесты на случайность

Набор тестов «Diehard»

В 1995 году Марсалья опубликовал набор статистических тестов для проверки качества генераторов псевдослучайных чисел, известный как Diehard. Набор включает 15 тестов, каждый из которых проверяет определённую гипотезу о случайности последовательности. Среди них:

• Тест на день рождения (Birthday Spacings) — проверяет распределение расстояний между днями рождения в случайной выборке.
• Тест на перекрывающиеся перестановки (Overlapping Permutations) — анализирует частоту появления различных перестановок в последовательности.
• Тест на ранги матриц (Ranks of Matrices) — проверяет, насколько матрицы, составленные из случайных чисел, соответствуют ожидаемому распределению рангов.
• Тест на монотонные последовательности (Runs Test) — проверяет длину возрастающих и убывающих подпоследовательностей.
• Тест на сжимаемость (Compressibility Test) — использует алгоритм сжатия для выявления закономерностей.

Тесты Diehard стали стандартом де-факто для проверки генераторов случайных чисел в научных и инженерных приложениях. В 2006 году Марсалья опубликовал обновлённую версию — Dieharder, которая включает дополнительные тесты и улучшенную статистическую обработку.

Другие работы

Марсалья также внёс вклад в теорию случайных процессов, статистическое моделирование и численные методы. Он разработал методы для генерации случайных чисел с заданным распределением (например, нормальным, экспоненциальным, гамма-распределением). Его работы по случайным числам и статистическим тестам остаются актуальными и цитируются в современных исследованиях.

Критика и наследие

Несмотря на широкое признание, некоторые из генераторов Марсалья, в частности «Mother of All», подвергались критике за недостаточную криптостойкость. В 2000-х годах были обнаружены уязвимости, позволяющие предсказывать последовательности, генерируемые этим алгоритмом, что ограничило его применение в криптографии. Однако для научных и инженерных целей, где не требуется устойчивость к атакам, эти генераторы остаются востребованными.

Наследие Марсалья включает не только конкретные алгоритмы, но и методологию тестирования случайности. Его тесты Diehard и Dieharder используются для валидации новых генераторов, включая современные аппаратные и программные решения. В честь Марсалья назван кратер на Луне (Marsaglia, диаметр 2,5 км), что является признанием его вклада в науку.

Интересные факты

• Марсалья был известен своим чувством юмора и нестандартным подходом к названиям алгоритмов (например, «KISS», «Mother of All»).
• Он активно выступал за использование простых и прозрачных алгоритмов, которые можно легко проверить и воспроизвести.
• В 1960-х годах он разработал метод «рандомизации» для статистических вычислений, который предвосхитил современные методы бутстрепа.

Источники

• Marsaglia, G. (1995). "Diehard: A Battery of Tests of Randomness". Florida State University.
• Marsaglia, G. (1991). "A New Class of Random Number Generators". The Annals of Applied Probability, 1(3), 462–480.
• Marsaglia, G. (1993). "The Mother of All Random Number Generators". Florida State University Technical Report.
• Marsaglia, G. (2003). "Random Number Generation". In: Encyclopedia of Statistical Sciences. Wiley.
• Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley.