СПОСОБ ГЕНЕРАЦИИ РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ И НЕЗАВИСИМЫХ СЛУЧАЙНЫХ ЧИСЕЛ Российский патент 2016 года по МПК G06F7/58 

Область техники

[0001] Кронекер сказал: Бог создал натуральные числа; все остальное является делом рук человека. Как предполагают изобретатели, он имел в виду то, что вся математика основана на изобретенных Богом натуральных числах или рекуррентной формуле x_k+1=x_k+1 при x₁=1; после чего труды, вдохновенные идеи и мысли известных людей позволили нам иметь рациональные числа, вещественные числа, комплексные числа, матрицы, геометрию, анализ и алгебру. В настоящее время изобретатели находятся на далеком расстоянии от уровня знания глубины и красоты математики того времени. Тем не менее, такая концепция, что вся математическая система построена на простейших рекуррентных формулах, обнадеживает нас. В настоящем документе мы представляем исследования по генерации случайных чисел на компьютере. В частности, мы показываем, что произвольная последовательность равномерно распределенных и независимых случайных чисел на компьютере может рассматриваться, как последовательность, генерируемая посредством мультипликативного конгруэнтного метода, и кладем этот факт в основу технологического способа генерации случайных чисел. Надеемся, что мы не будем бросать вызов Богам, но Боги благословят нас на блестящую перспективу, осуществимую руками человека.

[0002] Использование дистиллированной воды без примесей является необходимым для обеспечения устойчивых и правильных химических преобразований. Случайные числа с различной статистикой получают на компьютере при помощи высокоточных аналитических преобразований равномерно распределенных и независимых случайных чисел. Таким образом, генерация случайных чисел с высокоточной равномерностью и независимостью имеет важное значение для любого компьютерного моделирования, использующего различные типы случайных чисел. Наша задача состоит в представлении изобретений для способов генерации последовательностей случайных чисел на компьютере с радикально улучшенной точностью при своей статистике. Следует отметить, что теория вероятности или теория стохастических процессов неизменно основаны на предположении, что последовательности состоят из бесконечного количества элементов, и что обработанные числа имеют бесконечную степень точности вещественных чисел. Эти предположения вводят много упрощений, а также унификацию в форме предельных теорем или эргодических теорем. Напротив, компьютеры могут обрабатывать только последовательности конечной длины Т, какой бы большой не могла бы быть эта длина Т. А вещественные числа могут быть заданы только дискретно с наименьшей единицей точности. Конечность последовательностей и дискретность чисел обычно вызывает сложности. Несмотря на это, наше сознательное утверждение конечности и дискретности освобождает нас от различных метафизических проблем, таких как вопрос самой возможности генерации случайных чисел на компьютерах. Таким образом, мы здесь исходим из явного условия конечности обработанных чисел и последовательностей. Как будет вскоре объяснено, это позволяет нам сконцентрироваться на мультипликативной и конгруэнтной генерации равномерно распределенных и независимых случайных чисел, которая

содержит положительное целое число d, называемое модулем,

содержит положительное целое число z, взаимно простое с d и называемое множителем,

содержит положительное целое число n, взаимно простое с d и называемое начальным значением или начальным числом,

порождает последовательность {r_k≡n z^k| 0<r_k<d, k=0,1,2,···} целых чисел рекуррентно при помощи отношений конгруэнтности

и дает последовательность {v₁,v₂,v₃,…} случайных чисел в интервале (0,1) как

Отметим ступенчатое задание v_k и r_k-1, адаптированное здесь для дальнейшего удобства. Мультипликативный конгруэнтный генератор равномерно распределенных и независимых случайных чисел с модулем d, множителем z и начальным значением n будет символически обозначен, как (d, z, n). Если начальное число n не имеет отношения к аргументам, то это символическое обозначение будет сокращено до (d, z). Информация о случайных числах не сокращена до трех чисел (d, z, n); она получена как объект указаний, заданных посредством (d, z, n) и как огромное количество вычислительной работы для получения указанной последовательности. Для предотвращения путаницы и удобства обозначения образование степеней, таких как p_i в степени j_k, будет обозначено, как (p_i)^j_k.

Уровень техники

[0003] Начнем с общего технологического и математического описания проблемы. Требуется, чтобы генераторы случайных чисел на компьютере были воспроизводимыми, т.е. они должны давать одинаковую последовательность случайных чисел по запросу пользователя, например, когда пользователям надо отлаживать свои программы моделирования. Генераторы также должны быть переносимыми, т.е. они должны воспроизводить одинаковую последовательность случайных чисел на любых компьютерах и в любых вычислительных языках. А также моделирование обычно требует хранения в памяти компьютера слишком большого количества случайных чисел. Таким образом, случайные числа на компьютере могут быть сгенерированы только последовательно при помощи целочисленной арифметики, которая свободна от ошибок усечения и округления и дает одинаковые результаты на любых компьютерах или в любых вычислительных языках. Говоря более ясным языком, компьютеры должны производить последовательность {x₁, x₂,···, x_T} целых чисел, ограниченную как 0≤x_k<z для всех k при достаточно большом целом числе z, и выводить ассоциированную последовательность u_k:=x_k/z последовательно для k=1,2,… как равномерно распределенные и независимые случайные числа при помощи арифметики вещественных или рациональных чисел. Количество различных состояний на любом компьютере, доступных для определения следующего целочисленного результата, конечно. Следовательно, его начальное состояние постоянно повторяется, а длина последовательности случайных чисел, обозначенная Т, ограничена. Пусть последовательность {x₁, x₂,···, x_T} будет произвольной конечной последовательностью целых чисел в пределах интервала 0≤x_k<z. За исключением двух случаев, когда все {x₁, x₂,···,x_T} равны нулю и все равны d-1, мы получаем простое условие, что эта последовательность соответствует периоду

периодической последовательности, возникающей в процессе деления несократимой дроби n/d на основание z при x=n/d, удовлетворяющему условию <x<1,

Поскольку делитель d является множителем z^T-1, то d и z будут взаимно простыми. Процесс деления n на d никогда не заканчивается и выражается следующими уравнениями:

Основная особенность, которую следует отметить, состоит в том, что изменение одного числа в последовательности {x₁, x₂,···, x_T}, скажем x_j на х_j′, изменит вид несократимой дроби n/d, а наглядная близость целочисленных последовательностей может обычно приводить к очень различным формам неделимых дробей, хотя процессы деления будут почти параллельны. Другая особенность состоит в том, что второе уравнение, деленное на dz, дает ключевую оценку,

Эта оценка показывает очевидный факт: если при делении n на d остаток мал, то следующее частное будет также мало. Однако этот результат совсем не является очевидным. На практике целое число z больше, чем 2³⁰, a 1/z в качестве границы интервала пренебрежимо мало. Неравенство служит доказательством, что каждый член в любой последовательности {u_k:=x_k/z| k=1, 2,···,T}, которая должна давать равномерно распределенные случайные числа на компьютере, аппроксимируется, как v_k-1/z<u_k<v_k в малых и равномерно распределенных границах погрешности 1/z≈2^-30 соответствующей последовательности

которая является именно мультипликативной конгруэнтной последовательностью случайных чисел, сгенерированной при помощи генератора (d, z, n). Следовательно, в качестве математического принципа нам нужно только сосредоточиться на обнаружении мультипликативного конгруэнтного генератора (d, z, n) случайных чисел с достаточно длинным периодом Т с хорошей равномерностью и независимостью. Этот ясный и твердый взгляд на проблему дополнительно подкреплен спектральными тестами, которые неотделимо связаны с мультипликативной конгруэнтной генерацией случайных чисел.

[0004] В известном уровне техники существовали два различных типа для пары чисел (d, z) для мультипликативного конгруэнтного генератора. Один тип образован при помощи большого нечетного простого модуля d=p с множителем z его первообразного корня и реализует период Т=φ(р)=р-1, где φ является фи-функцией Эйлера. Другой тип состоит из модуля d=2ⁱ при i≥4 и любого множителя z=5 mod(8) для периода Т=2^i-2. Оба эти генератора реализуют большой период среди всех возможных выборов множителей для соответствующих модулей и, вероятно, принимают соответствующие спектральные тесты согласно очевидным математическим правилам, опуская получающуюся в результате большую вычислительную нагрузку. Настоящее изобретение является прямым потомком первого из них, пары нечетного простого модуля и его первообразного корня. Фишман и Мур (1986) предоставили монументальные спектральные тесты на простой модуль Мерсенна d=p=2³¹-1 и показали общий и убедительный факт, что хороший генератор (d, z) может быть найден только при помощи тщательного тестирования всех первообразных корней без каких-либо пристрастий. Однако такой вывод выявил значительную сложность; количество вычислений в полных спектральных тестах увеличилось пропорционально d^θ при показателе степени θ не большем, чем 3/2. Сам по себе тест должен быть выполнен на самом быстром современном компьютере. Требуется, чтобы компьютер был оборудован генератором случайных чисел для обеспечения наибольшего количества Т случайных чисел, которые могут быть использованы или вычислены в моделировании, скажем, месяца. Это число Т должно быть нижним пределом периода, который должен иметь генератор (d, z) случайных чисел, но выражение T≤d/2 является структурным ограничением мультипликативного конгруэнтного способа. Таким образом, компьютеры имеют предел вычислимости, пропорциональный d, но исчерпывающие спектральные тесты требуют общее количество вычислений, пропорциональное d^θ, при θ≥3/2. В этом и состоит проблема невычислимости. Накадзава и Накадзава (2012а, b) совершили важный прорыв в отношении этих трудностей путем использования модулей, образованных при помощи произведения двух степеней нечетных простых чисел. Такие способы уменьшают время вычисления исчерпывающих спектральных тестов до O(d^θ) при θ<1, в то же время сохраняя отношение периода Т к модулю d настолько большим, как в случае пары простого модуля и его первообразного корня.

Фишман и Мур (1986): Дж.С. Фишман и Л.Р. Мур, Полный анализ мультипликативных конгруэнтных генераторов случайных чисел с модулем 231-1. Журнал SIAM (Society for Industrial and Applied Mathematics, Общество промышленной и прикладной математики) научных и статистических вычислений, том 7, стр. 24-45.

Накадзава и Накадзава (2012а): Н. Накадзава и Н. Накадзава, Вычислительные процессы в спектральных тестах мультипликативных конгруэнтных генераторов для равномерно распределенных и независимых случайных чисел, реализованных посредством модулей, образованных двумя нечетными простыми числами. Название файла computable.pdf, загружаемого с http://www10.plala.or.jp/h-nkzw/ (26 октября 2012 г.).

Накадзава и Накадзава (2012b): Н. Накадзава и Н. Накадзава, Мультипликативные конгруэнтные генераторы с модулями, образованными посредством двух нечетных простых множителей, для равномерно распределенных и независимых случайных чисел I. Вычислительный анализ структур. Название файла revpopesql.pdf, загружаемого с http://www10.plala.or.jp/h-nkzw/ (15-17 сентября 2012 г., исправлен 31 октября 2012 г.).

Кратное раскрытие сущности изобретения

[0005] Следующие пункты (i1)-(i3) кратко излагают изобретения, которые будут представлены. Хотя они относятся к новым разработкам для соответствующей отдельной грани генерации равномерно распределенных и независимых случайных чисел, их объединение будет работать явно усиливая друг друга.

(i1) Новая расширенная разработка спектральных тестов в качестве усиленного фильтра для извлечения лучшей пары (d, z) нечетного модуля d и множителя z, являющегося взаимно простым с d, как мультипликативного конгруэнтного генератора для равномерно распределенных и независимых случайных чисел с достоверной статистической характеристикой.

(i2) Новая система разработок для мультипликативного конгруэнтного генератора (d, z), содержащего модуль d и множитель z, характеризующегося следующими условиями 2a)-2e);

2а) модуль d=d₁d₂ является произведением парных взаимно простых множителей d₁ и d₂, образованных при помощи двух различных нечетных простых чисел p₁ и p₂ как d_k=p_k^i_k для k=1,2 при i₁≥1 и i₂≥1,

2b) нечетное простое число p₁ имеет вид p₁=2q+1, а нечетное простое число p₂ имеет вид p₂=4r+1, при этом q и r - другие нечетные простые числа.

2c) множитель z удовлетворяет либо отношению конгруэнтности z≡z₁ mod(d₁), либо отношению конгруэнтности z≡-z₁ mod(d₁) для первообразного корня z₂ для d₂,

2d) множитель z удовлетворяет отношению конгруэнтности z≡z₂ mod(d₂) для первообразного корня z₂ для d₂,

2e) все упомянутые нечетные простые числа p₁, p₂, q, r являются различными.

(i3) Другая новая система разработок для мультипликативного конгруэнтного генератора (d, z), содержащего модуль d и множитель z, характеризующегося следующими условиями 3а)-3е);

3а) модуль d=d₁d₂ является произведением парных взаимно простых множителей d₁ и d₂, образованных при помощи двух различных нечетных простых чисел p₁ и p₂ как d_k=p_k^i_k для k=1,2 при i₁>1 и i₂≥1,

3b) нечетное простое число p₁ имеет вид p₁=2q₁+1, а нечетное простое число p₂ имеет вид p₂=2q₂+1, при этом q₁ и q₂ - другие нечетные простые числа,

3c) множитель z удовлетворяет либо отношению конгруэнтности z≡z₁ mod(d₁), либо отношению конгруэнтности z≡-z₁ mod(d₁) для первообразного корня z₁ для d₁,

3d) множитель z удовлетворяет либо отношению конгруэнтности z≡z₂ mod(d₂), либо отношению конгруэнтности z≡-z₂ mod(d2) для первообразного корня z₂ для d₂,

3е) все упомянутые нечетные простые числа p₁, р₂, q₁, q₂ являются различными.

[0006] Использование упомянутого изобретения (i2) следует начинать с принятия достаточно больших множителей первообразных корней z₁ для d₁ и z₂ для d₂ в указанных пунктах 2c) и 2d). Рекомендуется отфильтровывать их в процессе подготовки при помощи расширенного спектрального теста по п.(i1). Затем, принимая выбранные ±z₁ и z₂ один за другим, нам следует использовать построение Сунь Цзы для множителя z при помощи системы отношений конгруэнтности в пунктах 2c) и 2d), чтобы позволить (d, z) подвергнуться (i1) как спектральному тесту второго уровня, и получить целевой превосходный генератор для использования на компьютерах. Аналогично, использование упомянутого изобретения (i3) следует начинать с принятия достаточно больших множителей первообразных корней z₁ для d₁ и z₂ для d₂ в указанных пунктах 3с) и 3d). Принимая выбранных кандидатов ±z₁ и ±z₂ один за другим, мы снова используем построение Сунь Цзы для множителя z при помощи системы отношений конгруэнтности в пунктах 3c) и 3d), чтобы позволить (d, z) подвергнуться (i1), как спектральному тесту второго уровня, и получить целевой превосходный генератор для использования на компьютерах.

Подробное описание изобретений

Подробное описание первого изобретения

[0007] Для того, чтобы исключить из настоящего описания двусмысленность толкования, последовательность {n, nz, nz²,···} от мультипликативного конгруэнтного генератора (d, z, n) сначала будет принята в качестве бесконечной последовательности без отношений эквивалентности по модулю d. Соответствующие случайные числа воспроизводятся как

Начнем со спектрального теста второй степени, взяв последовательные наборы из двух чисел из сгенерированной последовательности. Зададим вектор Q_k:=(nz^k-1,nz^k)=nz^k-1(1,z). Пусть Q_k′ обозначает любой целочисленный вектор с координатами, равными координатам вектора Q_k по модулю d. Очевидно, что вектор Q_k′ получен из вектора Q_k посредством некоторых целочисленных кратных d смещений по координатным осям. Указанное d смещение по второй координатной оси осуществляется посредством сложения вектора e₂:=(0, d), d смещение по первой координатной оси осуществляется посредством сложения e₁′:=d(1,z)-z(0,d)=d(1,z)-ze₂. Следовательно, каждый вектор Qk′ с координатами, равными Q_k по модулю d является интегральной линейной комбинацией базисных векторов

которые являются линейно независимыми в том смысле, что они дают отличный от нуля детерминант. Все векторы или точки с координатами, равными координатам вектора Q_k, таким образом, находятся в решетке, образованной базисными векторами (или базисом) {е₁,е₂}. Мы говорим - узлы в решетке, поскольку они не могут занимать все узлы решетки. Обычно Q_k′ не может быть любой из точек, чьи одна или обе координаты равны О по модулю d. Пусть C_d обозначает квадрат в евклидовой плоскости Е₂, исходящий из начала координат с отрезком [0,d) в качестве сторон вдоль осей. В качестве удобного доказательства мы можем отметить, что вектора {е₁,е₂} образуют площадь d их детерминанта, тогда как квадрат C_d имеет площадь d². Более убедительно, вектор решетки je₁+ke₂=j(1,z)+k(0,d)=(j,jz+kd) с целыми числами j,k имеет первый компонент j, который может принимать только d различных значений {0,1,···,d-1} в C_d; как только определено j, целое число к будет единственным таким образом, чтобы для второго компонента выражение jz+kd находилось в интервале [0,d). Таким образом, квадрат C_d имеет ровно d узлов решетки. Генератор (d, z, n) дает точки {Q_k} в квадрате C_d, чей эквивалент по модулю d посажен на эти d узлов решетки. Степень заполнения этих опорных узлов решетки может быть максимально только (d-1)/d.

[0008] Аргументы могут быть распространены на последовательные наборы из L целых чисел при L=2,3,···, чтобы дать

Рассмотренный в качестве вектора или точки в L-мерном евклидовом пространстве E_L, этот вектор и все его d смещения по координатным осям очевидно находятся в L-мерной решетке, образованной базисными векторами

Примечательный факт состоит в том, что эта решетка снова имеет d узлов решетки в L-мерном гиперкубе C_d, исходящем из начала координат со сторонами длиной d вдоль осей. Это будет очевидно при помощи двух доказательств для случая количества измерений L=2, данного выше.

[0009] Указанное обстоятельство, что только d узлов решетки существуют в C_d независимо от количества измерений L, являются главной частью проблемы, возникающей при спектральных тестах. Ее понимание требует сначала представления об используемом периоде мультипликативных конгруэнтных последовательностей. Для простоты возьмем нечетный простой модуль d=p. Если множитель z является первообразным корнем для р, тогда генератор (p, z) дает циклическую последовательность {1,z,z²,···,z^p-1≡1} по модулю р; последний член добавлен здесь для напоминания о небольшой теореме Ферма. Каждое из целых чисел {1,2,···,р-1≡-1} используется этой циклической последовательностью раз в период Т=φ(р)=р-1. В результате чего z^T/2=z^(p-1)/2≡-1 mod(p) удерживается в средней точке. Остаток последовательности равен {-1,-z,-z²,···} и фактически является повторением первой части, Для независимых случайных чисел используется только длина Т-Т/2 последовательности. Так как вычислительная нагрузка генерации случайных чисел с помощью генератора (d, z) является пропорциональной d, мы задаем вычислительную эффективность, или просто эффективность этого генератора (d, z) как τ:=T′/d≈1/2. Такой результат для пары из нечетного простого числа и множителя его первообразного корня обычно и справедливо предполагает, что τ≈1/2 является верхней границей для всех мультипликативных конгруэнтных генераторов. Подробные исследования показывают, что существует два типа (а) и (b) модулей, упомянутых ниже, которые реализуют эту самую большую эффективность τ≈1/2 посредством надлежащего выбора множителя z

(a) d=pⁱ при нечетном простом числе р и показателе степени i≥1,

(b) d={(p₁)^i₁}×{(p₂)^i₂} при различных нечетных простых числах р₁ и р₂ и показателях i₁,i₂≥1,

где одно из простых чисел, скажем, p₁, дает нечетное q₁:=(p₁-1)/2, а другое дает q₂:=(p₂-1)/2.

Подробное доказательство со спецификацией множителей можно увидеть в заявке на патент Китая, опубликованной в Журнале патентов на изобретения с номером публикации CN 1031356961 А; предмет заявки позже был отмечен в документе (2012b) Накадзава и Накадзава.

[0010] Предположим, что моделирование требует период Т≈2⁵⁷. Тогда генератору (d, z) нужен модуль d≈2⁵⁸ или больше. Различные наборы из двух чисел (z_k,z_k+1) из используемой мультипликативной конгруэнтной последовательности существуют не более чем d/2 и заполняют только до 1/2 узлов решетки в квадрате C_d со сторонами [0,d) в евклидовой плоскости E₂. Таким образом, последовательные наборы из двух нормализованных независимых случайных чисел по большей мере могут быть 2⁵⁷ в единичном квадрате С₁ в E₂. Если стороны C₁ разделены с шириной d^-1/2≈2^-29, маленькие квадраты или ячейки с площадью d^-1 могут быть заняты с вероятностью ½ различными последовательными парами случайных чисел, появляющимися в одном используемом периоде. Спектральный тест второй степени нацелен на оценку геометрической конфигурации этих занятых ячеек посредством геометрии узлов решетки, в которых размещены упомянутые пары. Способ оценки будет упомянут кратко. Если геометрическая конфигурация решетки лучше, у нас будет меньше причин для отрицания статистического вывода, что случайные числа распределены независимо и равномерно. Таким образом, спектральные тесты с высокой точностью подходят к структурам мультипликативных конгруэнтных генераторов случайных чисел. Однако в это же время наука показывает, что этот успех незначителен. Возьмем случай последовательных наборов из L чисел Q_k:=(z^k-1,z^k,···,z^k+L-1) для L=2,3,···, образующих точки гиперкуба C_d со сторонами [0,d) в L-мерном евклидовом пространстве E_L. Снова существует по большей части только d/2 различных точек, образованных в используемом периоде. Следовательно, наборы из L последовательных случайных чисел должны быть многозначительно наблюдаемы посредством деления единичного отрезка на ширину δ=d^-1/L, которую оценивают как 1/512>δ>1/1024 в случае d=2⁵⁸ и L=6. Эта ширина небольшая, но грубая с точки зрения нормальной точности фиксированных вещественных чисел на компьютерах. Тем не менее, статистическое предположение, что последовательные наборы из L чисел из мультипликативной конгруэнтной последовательности выглядят равномерными и независимыми, будет менее сомнительным, если точки в этом грубом делении единичного гиперкуба в E_L заняты более равномерно. Мы должны подчеркнуть, что производительность спектральных тестов снижается с увеличением степени L теста, заданной текущим числом L случайных чисел, взятых для теста, но, напротив, также что спектральные тесты более низкой степени должны рассматриваться как ключевые для статистической точности в проблемах случайных чисел.

[0011] На основе качественных данных спектральных тестов, обратимся теперь к их количественным аспектам. Начинаем снова с очевидного случая L=2. Двумерная решетка нашей задачи определена посредством (d, z) и образована базисными векторами е₁, е₂. Эта решетка имеет много линий решетки {гиперплоскости решетки L-1 измерения, для общего количества измерений L≥2), которые проходят через произвольные L=2 узлы решетки; на протяжении этих линий решетки находятся фактически бесконечно много узлов решетки. Среди большого количества расстояний между смежными параллельными линиями решетки пусть самое большое расстояние будет обозначено как λd^(L)(z) при L=2. Если область, образованная базисными векторами e₁ e₂, прикреплена к d, тут вводят геометрические ограничения, которые обуславливают, что λ_d ⁽²⁾(z) должна иметь нижнюю границу $$\overline{}$$ , λ_d ⁽²⁾ определенную посредством d. Эта нижняя граница представляет собой значение указанного самого большого расстояния для геометрически идеальной формы решетки в E₂; при количестве измерений L-2 эта идеальная форма является треугольной решеткой. При общем количестве измерений L существует аналогичная нижняя граница: если объем, образованный базисными векторами решетки, заданный их детерминантом, прикреплен к d^L-1, как легко видно из базисных векторов {e₁, е₂,···,e_L}, геометрические ограничения обуславливают, что λ_d ^(L)(z) должна иметь нижнюю границу $$\overline{}$$ , λ_d ^(L), значение которой задано посредством геометрически идеальной формы решетки. Определим отношение ρ_d ^(L)(z):=λ_d ^(L)(z)/ $$\overline{}$$ ,λ_d ^(L). Поскольку геометрически идеальная решетка требует иррациональных координат для своего описания, то λ_d ^(L)(z) может никогда не достигать своего идеального значения $$\overline{}$$ , λ_d ^(L), а неравенство ρ_d ^(L)(z):=λ_d ^(L)(z)/ $$\overline{}$$ ,λ_d ^(L)>1 будет выполняться. Если ρ_d ^(L)(z) приближено к 1, то решетка в Е₂, сгенерированная при помощи наборов из двух чисел, порожденных генератором (d, z), приближена к идеальной треугольной форме, а ее узлы распределены более равномерно по всем направлениям. Спектральные тесты до сих пор использовались для оценки ρ_d ^(L)(z) для L=2, 3,···, 6, для того, чтобы выбирать множитель z, который реализует ρ_d ^(L)(z) наиболее близко к 1 сверху для 2≤L≤6. Соотношение между значениями ρ_d ^(L)(z) и формами решетки будет наглядно понятно из фиг.1A и 1B, которые изображают последовательные наборы из 2 узлов, показывающих, как они распределены для некоторых типичных значений ρ=ρ_d ^(L)(z). Нижние границы ^―,λ_d ^(L) для 2≤L≤6 заданы на фиг.5, как Список 4. Эпохальная работа Фишмана и Мура (1986) показала, что этот критерий, для ρ_d ^(L)(z)<1,25 для удержания со всеми L в диапазоне 2≤L≤6, универсален в присвоении не так много, но и не так мало проходных множителей z первообразных корней для простого модуля Мерсенна d=2³¹-1. С тех пор было доказано, что их критерии должны быть общепринятым и мощным инструментом для выбора хороших генераторов с различными формами модулей и множителей. Мы также будем интуитивно убеждены посредством фиг.1A и 1B, что этот критерий Фишмана и Мура непременно будет подходящим. Мы подчеркиваем, что вид мультипликативного конгруэнтного генератора (d, z) может быть довольно общим для того, чтобы настоящие аргументы относительно геометрической формы решетки оставались верными: модуль d может быть любым нечетным целым числом, а множитель z только должен быть взаимно простым с d. Значит, структуры решеток с упомянутыми базисными векторами являются четко определенными, а спектральные тесты будут работать в качестве оценки геометрической формы решетки, хотя значимость оценки спектрального теста будет снижена, если уровень покрытия узлов решетки, занятых точками наборов из L чисел, является небольшим.

[0012] Углубимся дальше в смысл спектральных тестов. Пусть мы начнем снова с тестов второй степени. Как обсуждалось выше, тесты изучают, может ли отношение z^k и z^k+1 быть названо независимым. Мы также надеемся придти к выводу, что z^k и z^k+2 будут независимыми. Верно это, или нет, можно легко проанализировать, взяв генератор (d, z²) и протестировав его спектрально. Аналогично, мы хотим, чтобы генератор (d, z³), (d, z⁴),),··· имел хорошую оценку, как генератор независимых случайных величин. На фиг.2 мы разместили Списки 1A-1E, которые отображают пять превосходных генераторов первообразных корней, обнаруженных Фишманом и Муром (1986) для простого модуля Мерсенна d=p=2³¹-1. Развитие компьютерных центральных процессоров, произошедшее за долгое время с тех пор, сделало спектральные тесты по этому модулю очень простыми. Строки, обозначенные а) в Списках 1A-1E показывают значения, найденные Фишманом и Муром. Следующая строка 1/а) изображает обратное значение этого значения, которое совпадает с соответствующим значением ρ_d ^(L)(z) в наших обозначениях. Строка b) изображает перерасчет ρ_d ^(L)(z) для 2≤L≤6, чтобы увидеть совпадение с 1/а). Оставшаяся строка, обозначенная с), изображает исполнение второй степени ρ_d ⁽²⁾(z^k) для 2≤k≤6 множителей z², z³,···,z⁶. Обратившись к фиг.1A и 1B, мы признаем, что эти множители не являются хорошими с точки зрения независимости случайных чисел, сгенерированных посредством их степеней.

[0013] Указанное открытие почти тривиально следует из вычислений, но выводы являются тяжелыми и угнетающими: любой существующий мультипликативный конгруэнтный генератор (d, z) должен быть повторно исследован с своими оценками по (d, z²), (d, z³),···; а если характеристики не являются удовлетворительными, то они должны быть заменены на генераторы с более надежной статистикой. Мы разместили эту разработку спектральных тестов в качестве пункта 1 формулы изобретения для обеспечения его непосредственного и широкого применения. Подробное описание второго и третьего изобретений

[0014] С более общей точки зрения факты, перечисленные на фиг.2, раскрывают, что простой модуль Мерсенна d=p=2³¹-1 может не иметь множителя первообразного корня с удовлетворительными характеристиками. Мы должны исследовать больше нечетных простых чисел, степеней нечетных простых чисел или произведений двух таких степеней нечетных простых чисел посредством спектральных тестов и найти хорошие мультипликативные конгруэнтные генераторы. Прежде всего, модуль d=p=2³¹-1 слишком мал для современных компьютеров, и мы должны перейти, скажем, к d≈2⁴⁸ или большему. Таким образом, мы сталкиваемся с трудностями вычислимости, и единственным выходом является выбор модулей, образованных двумя нечетными простыми числами или степенями нечетных простых чисел. Мы дополнительно обнаружили, что более необходимо решать новые проблемы, возникающие с соответственными генераторами (d, z²), (d, z³),···. Мы должны сначала исследовать их периоды, запрашивая также, существует или нет -1 в генерируемых ими последовательностях. Затем, должны быть исполнены тесты по меньшей мере второй ступени для (d, z²), (d, z³),··· для того, чтобы найти требуемый диапазон (d, z) и, в конечном итоге, перейти к спектральным тестам от третьей до шестой степени для (d, z). Вычислительная нагрузка должна быть уменьшена любыми средствами. По милости натуральных чисел существует две новые разработки, которые особенно подходят для снижения некоторых частей этой нагрузки. Сконцентрируемся на их описании, воздерживаясь от общих или исчерпывающих изысканий.

[0015] Начнем с двух математических следствий. Пусть нечетное простое число р выражено как p=2q+1, а также предположим, что целое число q также является нечетным простым числом. Примеры р=7 при q=3 и р=23 при q=11 доказывают существование таких простых пар. В действительности, компьютерные эксперименты предполагают их многочисленное бесконечное наличие. Это поддерживает верность следующего.

(Следствие 1) Если нечетное простое число р≥7 имеет вид p=2q+1, при этом q является другим нечетным простым числом, тогда z=2 является первообразным корнем из р порядка φ(p)=p-1=2q или имеет порядок q, как первообразный корень из р, взятый с противоположным знаком.

(Доказательство) Возьмем группу целых чисел Z_p≡{1,2,···,p-1=2q}, состоящую из 2q элементов, заданных посредством умножения по модулю р. Теорема Лагранжа доказывает, что порядок z=2 является делителем 2q. Предположение р≥7 подразумевает, что этот порядок не может быть равен 2. Следовательно, он является q или 2q, поскольку q - нечетное простое число. Если порядок z равен 2q, тогда z=2 является первообразным корнем из р. Если порядок z=2 равен q, тогда (-z)^q=-z^q=-1 mod(p), a -z является первообразным корнем из р. ■

[0016] Теперь рассмотрим нечетное простое число р по формуле р=4r+1, где r является другим нечетным простым числом. Примеры р=13 или 29, а компьютерные эксперименты легко убеждают нас, что такие нечетные простые числа существуют без ограничения.

(Следствие 2) Если нечетное простое число р>13 имеет вид р=4r+1, где r является другим нечетным простым числом, тогда z=2 является первообразным корнем из р.

(Доказательство) Прямые вычисления степени 2 для р=13 показывают, что 2 является первообразным корнем по модулю 13. Поэтому мы предполагаем, что р>29, г>7. Группа целых чисел, взаимно простых для р, состоит из ф(р)=4 r классов эквивалентности, а теорема Лагранжа доказывает, что порядок z=2 является множителем 4 r, который исчерпывается {1, 2, 4, r, 2 r, 4 r}. Предположение р>29 доказывает, что порядок z=2 не равен 1, 2, 4. Мы доказываем, что z2r=-l mod(p); это доказывает, что zr не эквивалентно 1 по модулю р, так что порядок z=2 будет 4 r и полным. Произведение

имеет другое выражение по модулю р:

Отметим, что R является нечетным. Таким образом, мы имеем 2^2r(2r)!≡-(2r)! mod(p) или 2^2r=-1 mod(p), поскольку (2r)! является взаимно простым для нечетного простого числа р=4r+1. ■

Это доказательство было передано Хироши Накадзава при посредничестве Наойа Накадзава 17 апреля 2013 г.

[0017] Вычисления с учетом упомянутых следствий сразу предполагают следующее:

(Предположение 3) Если нечетное простое число р≥7 выражено как p=2q+1, где q является другим нечетным простым числом, тогда для любой интегральной экспоненты i≥1 множитель z=2 будет либо первообразным корнем из d=pⁱ порядка φ(pⁱ)=2qp^i-1=2qd/p, либо взятым с противоположным знаком первообразным корнем из рⁱ с полуполным порядком qp^i-1=qd/p.(Конец предположения 3).

(Предположение 4) Если нечетное простое число p≥13 выражено как р=4r+1, где r является другим нечетным простым числом, тогда для любой интегральной экспоненты i≥1 множитель z=2 будет первообразным корнем из рⁱ с полным порядком φ(рⁱ)=4rp^i-1=4rd/p.(Конец предположения 4).

Эти предположения являются верными в том случае, если только они могут быть показаны для случая i=2, но мы не можем придти к доказательству. Однако компьютеры доказывают, что они являются верными вплоть до to р<10⁷=2^23,25; их легко можно предположить верными и, если нам нужны несколько модулей в виде рⁱ, мы сначала легко можем позволить компьютеру подтвердить это предположение при z=2. Указанные следствия и предположения предполагают для разработки мультипликативных конгруэнтных генераторов только с нечетными простыми числами указанных типов. Они дают φ(рⁱ) при небольших количествах простых множителей и значительно облегчают разработку генераторов (d, z). Помимо концептуальных и практических средств мы должны взять только степени 2 для множителей в сканировании первообразных корней или первообразных корней, взятых с противоположным знаком, они позволяют нам найти полезные и реализуемые структуры периодов, объясняемых ниже.

[0018] За счет второго и третьего изобретений будет целесообразно обобщить необходимые понятия. Все необходимые вычисления выполнены на стадии модулей, образованных посредством двух степеней простых чисел, и содержат двух основных игроков, пары первообразных корней для соответствующих степеней простых чисел, которые создают множители посредством системы отношений конгруэнтности. Наша задача состоит в том, чтобы вычислять периоды, реализуемые посредством упомянутых схем, а также отвечать на вопрос, возникает ли -1 или нет в сгенерированных последовательностях. Аргументы в значительной степени помогут нам посредством следующих следствий.

(Следствие 5) Пусть d₁, d₂ являются взаимно простыми целыми числами, а z_k является множителем, взаимно простым с d_k при k=1,2. Предположим, что генератор (d_k, z_k) имеет порядок или период Т_к, а они синтезированы в генератор (d, z), заданный посредством

Циклическая последовательность, сгенерированная (d,z) и заданная теперь как G(z;d):≡{1, z, z²,···} mod(d), имеет порядок или период Т, как наименьшее общее кратное T:=LCM(T₁,T₂).

(Доказательство) По этому случаю мы ссылаемся на построение Сунь Цзы, относящееся к его теореме, которое дает решение z для указанной системы отношений конгруэнтности по модулю d. Поскольку d₁ и d₂ являются взаимно простыми при GCD(d₁, d₂)=1, алгоритм Евклида обеспечивает существование целых чисел А, В, удовлетворяющих условию Ad₁+Bd₂=1. Целые числа U₁:=Bd₂=1-Ad₁ и U₂:=Ad₁=1-Bd₂ определены посредством исключительно лишь d₁ и d₂ без какого-либо отношения к z₁ и z₂, и удовлетворяют условию U_j mod(d_k)=δ_jk. Таким образом, решение z для указанной системы отношений конгруэнтности будет

Любое другое решение z′ дает z-z′=0 mod(d_k) при k=1,2,, так что z-z′ является кратным взаимно простым d₁ и d₂. Значит, z′=z mod(d) остается верным вследствие единственности модуля d. Прямые вычисления z^j и соблюдение z^j≡(z_k)^j mod(d_k) для k=1,2 сразу доказывает

Увеличивая j до Т, мы имеем

для которого (z_k)^T≡1 mod(d_k) должно оставаться верным при k=1,2. Таким образом, порядок или период G(z;d) является наименьшим общим кратным Т₁ и Т₂. ■

Утверждение ниже будет очевидным.

(Следствие 6) Предположим, что генератор (d, z) или его циклическая последовательность G(z;d) имеет период или порядок Т. Генератор (d, z^j) или циклическая последовательность G(z^j;d) реализуют период T^(j):=T/{GCD(j,T)} при любом показателе степени j=1,2,···. (Конец следствия 6)

Мы можем отметить несколько выводов, которые помогут нам в обсуждении того, появляется ли -1 или нет в циклической последовательности G(z^j;d), заданной генератором (d, z^j), в частности, когда z задано посредством z≡z_k mod(d_k) при k=1,2 и взаимно простых d₁ и d₂.

(Следствие 7) (А1) Если циклическая последовательность G(z;d) не содержит -1 mod(d), тогда циклические последовательности G(z^j;d) при любых индексах j=1,2,··· свободны от -1 по модулю d.

(A2) Продолжим обозначение T(j) для порядка или периода циклической последовательности G(z^j;d) при любых j=1, 2,···. Для того, чтобы G(z^j;d) содержала -1 mod(d), T^(j) обязательно является четным. Контрапозиция будет: Если является нечетным, то циклическая последовательность G(z^j;d) не содержит -1 по модулю d.

(В) Если модуль d=d₁d₂ является произведением двух взаимно простых множителей d₁ и d₂, a z задано посредством z≡z_k mod(d_k) для k=1,2, тогда следующие утверждения (B1) и (B2) останутся верными относительно того, появится или нет -1 в циклической последовательности G(z^j;d).

(B1) Если по меньшей мере одна из компонентных циклических последовательностей G(z_k;d_k) для k=1 или 2 свободна от -1 по модулю d_k, тогда циклическая последовательность G(z^j;d) для любого индекса j=1,2,··· свободна от -1 по модулю d.

(B2) В случае составного модуля d=d₁d₂ четный период T^(j) при любых j=1, 2,··· для циклической последовательности G(z^j;d) не всегда является достаточным для появления -1 по модулю d в последовательности G(z^j;d). Необходимым и достаточным условием для появления -1 по модулю d в последовательности G(z^j;d) является то, что T^(j) является четным и циклические последовательности {G(z′;d_k)|z′:≡(z_k)^j mod(d_k), k=1,2} имеют -1 по модулю d_k согласно Т^(j)/2, т.е. для k=1 и 2 остается верным выражение (z_k)^(T(j)/2)≡-1 mod(d_k).

(Доказательство) (A1) Утверждение очевидно, поскольку циклическая последовательность или циклическая группа G(z^j;d) при любых j=2,3,··· является подмножеством или подгруппой, содержащейся в большей уменьшенной группе класса вычетов G(z;d) целых чисел по модулю d.

(A2) Если циклическая последовательность G(z^j;d) содержит -1≡d-1 mod(d) при 0<Т′<Т^(j), тогда мы имеем

Таким образом, 0<2T′<2T^(j) является кратным T^(j), выражение 2T′=T^(j) остается верным, а Т^(j) обязательно является четным при T′=T^(j)/2.

(B1) Если циклическая последовательность G(z;d) содержит -1≡d-1 mod(d),, тогда G(z_k;d_k)=G(z;d) mod(d_k) содержит -1 mod(d_k) для обоих k=1,2. Контрапозиция доказывает указанное утверждение.

(B2) Мы скоро увидим пример последовательности G(z^j;d) с четным T^(j), при этом в циклической последовательности не содержится -1. Докажем необходимую и достаточную часть. Необходимость четного T^(j) установлено в (A2), а доказательство этого показывает, что (z^j)^(T^(j)/2)≡-1 mod(d). Следовательно, мы имеем уравнения

которые доказывают необходимую часть (А2). Напротив, предположим, что T^(j) является четным, и что отношения конгруэнтности {(z₁)^j}^(Т^(j)/2)≡-1 mod(d₁) и {(z₂)^j}^(T^(j)/2)≡-1 mod(d₂) остаются верными. Построение Сунь Цзы доказывает (z^j)^(T^(j)/2)≡{(z_k)^j}^(Т^(j)/2) mod(d_k) для k=1,2, так что (z^j)^(Т^(j)/2) является по модулю d уникальным решением этой системы отношений конгруэнтности

Заведомо (z^j)^(T^(j))/2)=-1 mod(d) является решением, и доказательство закончено. ■

[0019] Обратимся к описанию двух изобретений, которые участвуют в разработке мультипликативного конгруэнтного генератора (d, z). Первое будет позже размещено в качестве пункта 2 формулы изобретения и пояснено здесь. Пусть (d, z) будет мультипликативным конгруэнтным генератором, удовлетворяющим семи условиям (2a)-(2g), перечисленным ниже:

(2a) Модуль d является произведением двух взаимно простых множителей d=d₁d₂,, где d₁ и d₂ будут называться подмодулями,

(2b) подмодуль d₁=(p₁)^i₁ является нечетным простым числом p₁ в степени i₁, причем целый показатель степени i₁≥1, а нечетное простое число p₁ выражено в виде p₁=2q+1, где q является другим нечетным целым числом,

(2c) подмодуль d2=(p₂)^i₂ является нечетным простым числом p₂ в степени i₂, причем целый показатель степени i₂≥1, а нечетное простое число p₂ выражено в виде p₂=4r+1, где r является другим нечетным целым числом,

(2d) все нечетные простые числа p₁, p₂, q, r являются различными,

(2e) множитель z задан посредством системы конгруэнтных уравнений

где z₁ и z₂ будут называться подмножителями,

(2f) подмножитель z₁ является либо первообразным корнем, либо первообразным корнем, взятым с противоположным знаком, для подмодуля d₁,

(2g) подмножитель z₂ является первообразным корнем подмодуля d₂.

[0020] Характеристики этих разработок представлены в табличной форме на фиг.3 в виде Списка 2A и Списка 2B. Возьмем сначала разработку, которая использует в (2f) первообразный корень z₁ подмодуля d₁=(p₁)^i₁ для подмножителя по модулю d₁. Мы начинаем работать с генератором (d₁, z₁), который будет называться подгенератором. По предположению z₁ имеет наибольший порядок по модулю d₁,

Аналогично, подгенератор (d₂, z₂) имеет z₂ с наибольшим порядком по модулю d₂,

Генератор (d=d₁d₂,z) задан посредством системы отношений конгруэнтности, описанной в (1e), и в соответствии со (Следствием 5) синтезированный генератор (d, z) имеет порядок или период Т (d, z) наименьшего общего кратного

Порядок (d, z^j) теперь может быть вычислен при помощи (Следствия 6) для любых j=1, 2, 3,···:

Эта формула дает три существенных факта благодаря вышеуказанным предположениям (2a)-(2d):

(2A1) Если j<min(q, r) является нечетным, тогда порядок Т^(j)=Т.

(2A2) Если j<min(q, r) является четным, но не кратным 4, тогда Т^(j)=Т/2.

(2A3) Если j<min(q, r) кратно 4, тогда Т^(j)=Т/4.

Теперь мы должны обратиться к изучению вопроса, возникает ли -1 или нет в циклической последовательности G(z^j;d), и найти пригодный период, который обозначим Т_u ^(j), последовательности G(z^j;d) для независимых случайных чисел. Мы должны пройти сквозь такую ситуацию, где подмножители z₁, z₂ являются первообразными корнями, и необходимо отследить соответствующую -1 в их циклических последовательностях. Таким образом мы прибегаем к (B2) и (A1) (Следствия 7) и показываем рассогласование вследствие G(z₁;d₁). Из T=4qrd/(p₁p₂) и T/2=T₁×(целое число) мы имеем

Таким образом, в последовательности G(z;d)-1 не возникает, а (A1) (Следствия 7) обеспечивает отсутствие -1 в последовательностях G(z^j;d) для любого показателя степени j<min(q, r). Все порядки или периоды циклических последовательностей в Таблице 2A являются пригодными: Тu^(j)=T^(j). Мы делаем вывод относительно эффективности τ:=(длина используемого периода)/d,

(2A1) для строк с нечетным] j: τ=T/d≈1/2,

(2A2) для строк с четным j, но не кратным 4: τ=(T/2)/d≈1/4,

(2A3) для строк с j, кратным 4: τ=(T/4)/d≈1/8.

Доказательство Списка 2A на фиг.3 закончено.

[0021] За счет Списка 2B на фиг.3, который изображает характеристики изобретения, образующего вторую половину пункта 2 формулы изобретения, мы сначала должны дать описание подмножителя, который является взятым с противоположным знаком первообразным корнем по модулю d₁, как предложено разработкой (2f). Подмножитель по модулю d₁ будет обозначен -z₁, подразумевая, что z₁ является первообразным корнем для d₁. Первообразный корень z₁ генерирует циклическую последовательность, состоящую их целых чисел, различных, по модулю d₁.

В частности, целые числа {z₁, (z₁)²,···,(z₁)^(T₁/2-1)} не эквивалентны ±1 по модулю d₁. Следовательно, предположение, что нечетность T₁/2=qd₁/p₁ доказывает, что (-z₁)^(T₁/2)≡1 mod(d₁) впервые возникает в последовательности {-z₁, (-z₁)²,···}. Таким образом, порядок или период циклической последовательности G(-z₁;d₁) равен T₁/2 и будет четным. Подмножитель -z₁ не является первообразным корнем для d₁. Однако, (Следствие 6) обеспечивает, что порядок или период последовательности G(z;d) равен

(порядок z по модулю d)=LCM(T₁/2,T₂)=LCM(qd₁/p₁,4rd₂/p₂)=4qrd/(p₁p₂).

Это заметно является идентичным со случаем подмножителя z₁ первообразного корня, и все результирующие порядки z^j для j<min(q, r) аналогично являются неизменными. И нечетный порядок для -z₁ обуславливает, что циклическая последовательность G(-z₁;d₁) не содержит -1, а (A2) (Следствия 7) доказывает, что вся Таблица 2B относится к случаю T_u ^(j)=T^(j). Здесь нет никаких изменений по сравнению со Списком 2A, и все элементы Списка 2 В соответствуют.

[0022] Отметив важность тестирования z^j при j=2, 3,···, как множителей, мы обнаружили результаты, обобщенные в Списках 2A и 2B на фиг.3. Эффективность τ была обнаружена изменяющейся в диапазоне от 1/2 до 1/8, что может быть справедливо названо правильной флуктуацией, в частности, по сравнению со случаем модуля d=2ⁱ, который будет пояснен позже. Фактически, мы получим небольшую возможность использовать эти случайные числа вплоть до d/8. Однако, указанные изменения используемых периодов для z, z²,··· могут восприниматься едва заметными, хотя технологически это может стать естественной идеей для искусственного сокращения пригодных периодов до d/8 для предотвращения взаимозависимостей, опровергающих независимость. После всего, нам нужны трудные вычисления спектральных тестов для того, чтобы получить генератор (d, z) с надежной статистикой, и неизвестно, будут ли естественно плоские и красивые используемые периоды для z, z²,··· способствовать большим множителям для получения лучших характеристик. Хотя наша интуиция искушает нас, шепотом скажем, что более плоские или четные используемые периоды могли бы быть лучше. Следующее изобретение по пункту 3 формулы изобретения фактически обеспечивает плоскостность за счет уменьшения наибольшего значения используемых периодов. Предложенная разработка согласно этому изобретению определяется семью условиями (3a)-(3g), перечисленными ниже.

(3a) Модуль d является произведением двух взаимно простых множителей d=d₁d₂,, где d₁ и d₂ будут также называться подмодулями,

(3b) подмодуль d₁=(p₁)^i₁ является нечетным простым числом p₁ в степени i₁ причем целый показатель степени i₂≥1, а нечетное простое число p₂ выражено в виде p₂=2q₂+1, где q₂ является другим нечетным целым числом,

(3c) подмодуль d₂=(p₂)^i₂ является нечетным простым числом p₂ в степени i₂, причем целый показатель степени i₂≥1, а нечетное простое число p₂ выражено в виде p₂=2q₂+1, где q₂ является другим нечетным целым числом,

(3d) все нечетные простые числа p₁, p₂, q₁, q₂ являются различными,

(3e) множитель z задан посредством системы конгруэнтных уравнений,

where z₁ and z₂ will be called submultipliers, где z₁ и z₂ будут называться подмножителями,

(3f) подмножитель z₁ является либо первообразным корнем, либо первообразным корнем, взятым с противоположным знаком, для подмодуля d₁,

(3g) подмножитель z₂ является либо первообразным корнем, либо первообразным корнем, взятым с противоположным знаком, для подмодуля d₂.

Результирующие характеристики генератора (d, z) обобщены на фиг.4 в виде Списков 3A-3C. Мы доказываем эти списки, показывая преимущество указанных разработок.

[0023] Возьмем сначала разработку, которая использует подмножители z₁ и z₂ первообразных корней. Подгенераторы (d_k, z_k) при k=1, 2 имеют четные порядки

и реализуют (z_k)^(T_k/2)≡-1 mod(d_k) в середине. Также, (Следствие 5) доказывает порядок Т для G(z;d), как

Порядок T^(j) циклической последовательности G(zⁱ;d) теперь разделен на две группы при помощи (Следствия 6):

(3A - нечетное) нечетное j<min(q₁,q₂):Т^(j)=T=T₁(T₂/2)=(T₁/2)T₂=(четное),

(3A - четное) четное j<min(q₁,q₂):T^(j)=T/2=q₁q₂d/(p₁p₂)=(нечетное).

Возьмем сначала четное j с нечетным Т^(j). Посредством (A2) (Следствия 7) -1 отсутствует в G(z^j;d), а равенство T_u ^(j)=T^(j) является верным. Мы имеем

(эффективность т для каждого четного j)=T^(j)/d≈1/4,

и четные j строки Списка 3A доказаны. Напротив, нечетное j требует вычислений {(z_k)^j}^(T^(j)/2) mod(d_k) при k=1,2. Поскольку в этом случае T^(j)/2=T/2=(T₁/2)(T₂/2) является произведением нечетных целых чисел, мы имеем

{(z_k)^j}^(T/2)={[(z_k)^j]^(T_k/2)}^(нечетное целое число)

={(z_k)^(T_k/2)}^{j×(нечетное целое число)}

≡(-1)^(нечетное целое число)≡-1 mod(d_k).

Циклические последовательности G((z_k)^j;d_k) c любыми нечетными j для k=1 и 2 таким образом являются созвучными. А (B2) (Следствия 7) доказывает (z^j)^(Т/2)≡-1 mod(d). Используемый период последовательности G(z^j;d) равен T_u ^(j)=T^(j)/2=T/2. Эффективность τ=(T/2)/d≈l/4. Эти полные доказательства нечетных j строк и всего Списка 3A.

[0024] Рассмотрим теперь случай, когда один из подмножителей является первообразным корнем, взятым с противоположным знаком, результаты которого показаны в Списке 3B на фиг.4. Мы принимаем без потерь общее утверждение, что первый подмножитель является первообразным корнем, взятым с противоположным знаком, и обозначен как -z₁, при этом z₁ является первообразным корнем для d₁, a z₂ является первообразным корнем для d₂. Циклическая последовательность G(-z₁;d₁) имеет порядок T₁′:=T₁/2=q₁d₁/p₁, который является нечетным. Таким образом, (A2) (Следствия 7) утверждает, что свободно от -1 для любых j=1, 2,···. Все порядки G(z^j;d) являются используемыми. Порядок последовательности G(z;d) будет

(порядок для z)=LCM(T₁′, T₂)=LCM(q₁d₁/р₁,2q₂d₂/p₂)=2q₁q₂d/(p₁p₂)=T.

Это совпадает с порядком Т предыдущего случая, где оба подмножителя являются первообразными корнями. Значит, все циклические последовательности G(z^j;d) для целых показателей степеней j<min(q₁,q₂) имеют одинаковые порядки, как и раньше. Логические рассуждения доказывают, что порядки T^(j) будут следующими:

(3B - нечетное) нечетное j<min(q₁,q₂):Т(j)=Т=Т₁(Т₂/2)=(T₁/2)Т₂,

(3B - четное) четное j<min(q₁,q₂):Т^(j)=Т/2=(Т₁/2)(T₂/2).

Разница по сравнению с предыдущим случаем состоит в том, что независимо от того, является j четным или нечетным, все эти порядки являются используемыми в связи с отсутствием -1.

(нечетное j): τ=T/d≈1/2, (четное j): τ=(T/2)/d≈1/4,

которые все должны быть доказаны для Таблицы 3B.

[0025] Возьмем оставшийся случай, когда оба подмножителя являются превообразными корнями, взятыми с противоположными знаками, которые будут обозначены -z₁ и -z₂. Подгенераторы (d₁, -z₁) и (d₂, -z₂) имеют соответствующие порядки Т₁′ и Т₂′:

Период Т′ синтезированной последовательности G(z;d) задан посредством

который является нечетным. Циклическая последовательность G(z^j;d) при j<min(q₁, q₂) имеет один и тот же нечетный порядок T′/GCD(j,T′)=T′. Исходя из этого, или при помощи любого из (A1), (A2) или (B1) (Следствия 7) для всех рассматриваемых генераторах отсутствует -1 в их циклических последовательностях, а эффективность τ унифицирована до

Это доказывает все из Списка 3C. ■

[0026] В последних нескольких параграфах мы должны более подробно описать вычислительные процедуры спектральных тестов. Позже мы также должны дать заключение по поводу случая модуля d=2ⁱ при i≥4, но до этого мультипликативный конгруэнтный генератор (d, z) предполагается содержащим произвольное нечетное целое d в качестве модуля и любое целое число, взаимно простое с d, в качестве множителя. Пусть L≥2 будет целым числом. Последовательный набор из L чисел из генератора (d, z) задан здесь в виде Q_k:=(z^k,z^k+1,···,z^k+L-1)=z_k(1,z,···,z^L-1) при k=0, 1,··· без эквивалентности по модулю d, и рассматривается в виде вектора в L-мерном евклидовом пространстве E_L. Мы увидели, что его d смещения по координатным осям реализованы при помощи интегральных линейных комбинаций векторов

которые являются очевидно линейно независимыми относительно детерминанта d^L-1. Интегральные линейные комбинации этих векторов задают решетку в пространстве E_L при помощи базисных векторов {e₁,e₂,···,eL}. Задачей спектральных тестов степени 1 является вычисление наибольшего расстояния λd^(L)(z) между смежными параллельными гиперплоскостями решетки размерности L-1, которая проходит сквозь 1 линейно независимых векторов решетки, и вычисления отношения ρ_d ^(L)(z):=λ_d ^(L)(z)/^―,λd^(L)>1 в качестве оценки спектрального теста степени L, где ^―,λ_d ^(L) for L=2, 3,···, 6 является наименьшими возможными значениями λ_d ^(L)(z), реализованных при помощи геометрически идеальных форм решеток. Выражения, ^―, λ_d ^(L) в табличной форме представлены, как Список 4 на фиг.5.

[0027] Наиболее абстрактная часть вычислений спектральных тестов обобщена в следующем утверждении:

(Теорема 8) Зададим векторы {f₁, f₂,···, f_L}обратной или дуальной решетки, соответствующие базисным векторам {е₁, е₂,···, e_L, как показано ниже:

Векторы, образованные интегральными линейными комбинациями векторов {f₁, f₂,···,f_L}, составляют дуальную решетку для генератора (d, z). Пусть a_min ^(L)(z) означает наименьшую ненулевую длину вектора в L-мерной (d, z) обратной решетке. Тогда наибольшее расстояние λ_d ^(L)(z) между смежными параллельными гиперплоскостями исходной решетки выражается формулой λ_d ^(L)(z)=d/a_min ^(L)(z). (Конец Теоремы 8)

Полное доказательство Теоремы 8 дано Накадзава и Накадзава (2012 с). Для того чтобы дать в этом документе доказательство в полном объеме, нужно слишком большое количество бумаги. Поэтому мы опускаем это описание, отсылая читателей к первоисточнику, и описываем здесь процедуры простейшего второго теста, необходимого для подачи пункта 1 формулы изобретения. Обратные базисные вектора со степенью 2 для генератора (d, z) будут

Общая перспектива, полезная также и для более высоких измерений L=3, 4,···, получена посредством рассматривания вектора с декартовыми целочисленными координатами f=(j₁, j₂) которые находятся в обратной решетке. Мы имеем следующее:

(Следствие 9) Необходимое и достаточное условие для того, чтобы целочисленный вектор f=G 1J2) находился в 2-мерной обратной решетке генератора (d,z), задано следующим:

(Доказательство) Для того, чтобы вектор f=(j₁, j₂) находился в указанной обратной решетке, обязательно должны существовать целые числа m₁, m₂ и давать f=m₁f₁+m₂f₂ или

Следовательно, условие j₁+zj₂=dm₁≡0 mod(d) является необходимым. Напротив, если это условие удовлетворяется, существует целое число k, которое дает j₁+zj₂=kd, или

и f является вектором дуальной решетки. Таким образом, это условие является достаточным. ■

Одним из достоинств представления в системе декартовых координат f=(j₁, j₂) является то, что длина вектора f задана при помощи простой евклидовой нормы $$\Vert f\Vert :={\left\{{\left(j_1\right)}^2+{\left(j_2\right)}^2\right\}}^{1/2}$$ . Кроме того, ограничения, указанные в Списке 4 на фиг.5,

которые остаются верными по геометрическим причинам для любой пары (d, z) из нечетного модуля d и множителя z, взаимно простого с d, или для любой пары взаимно простых целых чисел d и z, говорит нам о существовании очень полезных границ,

для длины $$a_{\min }{}^{(2)}(z):=\Vert f_{\min }\Vert$$ наименьшего ненулевого вектора f_min в обратной решетке. Таким образом, поиск наименьшего дуального вектора f_min=(j₁, j₂) с целочисленными декартовыми координатами для (d, z) может быть ограничен узким диапазоном $$\left|j_1\right|,\left|j_2\right|<O\left(d^{1/2}\right)$$ . Аналогичные полезные границы также могут существовать в более высоких изменениях L≥2 с соответствующими изменениями в формуле, указывая вычислительно простой признак спектральных тестов. Спектральный тест второй степени обычно оценивает генератор (d, z) и дает, что ρ_d(2)(z):=λ_d ⁽²⁾(z)/^―,λ_d ⁽²⁾ удовлетворяет условию ρ_d ⁽²⁾(z)<1,25, и будет удовлетворительным, как было предложено Фишманом и Муром (1986).

Накадзава и Накадзава (2012 с): Н. Накадзава и Н. Накадзава, Мультипликативные конгруэнтные генераторы с модулями, образованными посредством двух нечетных простых множителей для равномерно распределенных и независимых случайных чисел II. Структуры, относящиеся к спектральным тестам. Название файла popesq2.pdf, загружаемого с http://www10.plala.or.jp/h-nkzw/ (15 октября, 2012).

[0028] Мультипликативные конгруэнтные генераторы для равномерно распределенных и независимых случайных чисел имеют другую существенную разработку, которая принимает степень простого числа 2 в качестве модуля d=2ⁱ Простое условие z≡5 mod(8) обеспечивает, что множитель z должен дать наибольший возможный период T=2^i-2=d/4. В другой эпохальной работе Фишмана (1990) выполнены спектральные тесты для модуля d=2³², исчерпавшие все возможные множители z≡5 (8), а также исследована часть множителей для d=2⁴⁸; в последнем случае вычислительные сложности помешали ему выполнить исчерпывающие тесты. Накадзава и Накадзава (2008) показали, что эта проблема не может быть решена посредством использования составных модулей. Если степень числа 2 вводит модуль d в качестве множителя в произведение с нечетными простыми числами или степенями нечетных простых чисел, это неизбежно приносит взаимозависимость среди степеней подмножителей, а результирующие случайные числа не могут быть приняты независимыми; это является ужасным недостатком в том смысле, что он не может быть обнаружен посредством спектральных тестов. Иными словами, для мультипликативного конгруэнтного генератора модуль d=2ⁱ должен использоваться в единственном числе, а сильные затруднения в вычислениях для исчерпывающих спектральных тестов не дают возможность облегчить статусное положение, бывшее у Фишмана (1990). Отметим здесь другую проблему. Предположим, у нас есть генератор (d, z), где d=2ⁱ и z=5 mod(8). Мы увидели, что (d, z^j) для j=2, 3,··· также должны быть хорошими генераторами случайных чисел, а трудности возникают с их порядками. Поскольку генератор (d=2ⁱ, z) имеет порядок Т=2^i-2, генератор (d, z^j) имеет

в качестве своего порядка. Если экспонента j указанного множителя достигает j=2^m для m<i-2, возникает внезапное изменение Т′=Т/2^m. Эта особенность будет непригодна для генераторов (d=2ⁱ, z^j) с различными показателями степени j для реализации хорошей независимости случайных чисел. Конечно, это только мысленная догадка, сопоставленная с очень трудными вычислениями спектральных тестов, и, однако, действительные характеристики генераторов должны распознаваться при помощи числовых экспериментов.

Фишман (1990): Дж.С. Фишман, Мультипликативные конгруэнтные генераторы случайных чисел с модулями 2^β: Исчерпывающий анализ для β=32 и частичный анализ для β=48. Математика вычислений, Том 54 (1990), стр. 331-344 Накадзава и Накадзава (2008): Н. Накадзава и Н. Накадзава, Разработки равномерно распределенных и независимых случайных чисел с большим периодом и высокой точностью - управление последовательной геометрией посредством произведения групповых структур и конфигураций решеток. Название файла 3978erv.pdf, загружаемого с http://www10.plala.or.jp/h-nkzw/ (9 марта - 8 июля, 2008).

Краткое описание чертежей

[0029] (Фиг.1A, 1B). Типичные распределения точек, образованные посредством последовательных наборов из двух случайных чисел, порожденных мультипликативным конгруэнтным генератором (d, z); показанные распределения соответствуют оценке ρ:=ρ_d ⁽²⁾(z) приблизительно 1,05, 1,10,···; изображенные квадраты взяты немного большими, чем единичные квадраты, а генератор (d, z) может быть прочитан в подписи под изображениями.

[0030] (Фиг.2) Списки 1A-1E, изображающие характеристики пяти лучших множителей из работы Фишмана и Мура (1986); в строке а) находится значение, показанное в их работе, строка 1/а) изображает обратное значение для а) и совпадает с представленным ρ_d ^(L)(z),, в строке b) находится расчет ρ_d ^(L)(z) согласно настоящему изобретению, а оставшиеся строки показывают ρ_d ⁽²⁾(z^j) для j=2, 3,···, 6.

[0031] (Фиг.3) Списки 2A и 2B для генераторов (d, z^j) для j=1, 2,···, показывающие порядок для z^j, существование или отсутствие -1 в циклической последовательности из генератора (d, z^j) и эффективность τ, где генератор (d, z) разработан в соответствии с положениями, указанными в пункте 2 формулы изобретения.

[0032] (Фиг.4) Списки 3A-3C для генераторов (d, z^j) для j=1, 2,···, показывающие порядок для z^j, существование или отсутствие -1 в циклической последовательности и эффективность τ, где генератор (d, z) разработан в соответствии с положениями, указанными в пункте 3 формулы изобретения.

[0033] (Фиг.5). Список 4, показывающий наименьшее значение ^―,λ_d ^(L) для максимального расстояния λ_d ^(L)(z) смежных параллельных гиперплоскостей решетки в размерности L-1, реализованных при помощи геометрически идеальных форм решетки в L-мерном евклидовом пространстве, где объем единичной ячейки решетки един для d^L-1.

Изобретение относится к области вычислительной техники и может быть использовано для генерации случайных чисел. Техническим результатом является повышение точности. Способ генерации равномерно распределенных и независимых случайных чисел с нечетным модулем d и множителем z, взаимно простым с d, начинает с произвольно заданного целого числа n, взаимно простого с d, и рекуррентно порождает последовательность целых чисел {r₀, r₁, r₂, …} при помощи отношений конгруэнтности r₀≡n mod(d), 0<r₀<d, r_k≡zr_k-1 mod(d), 0<r_k<d, k=1, 2, 3, …, и дает на выходе случайные числа {v_k:=r_k-1/d| k=1, 2, …}, при этом множитель z выбран таким образом, что удовлетворяет условию, что генератор (d,z′) при z′≡z^j mod(d) для целого j по меньшей мере в диапазоне 1≤j≤6 проходит спектральный тест второй степени в пределах оценки 1,25, а именно, для любого целого j в диапазоне 1≤j≤6 генератор (d, z′) при z′≡z^j mod(d) удовлетворяет условию, что вектор f дуальной решетки, заданный для (d, z′) посредством линейной комбинации f:=m₁f₁+m₂f₂ базисных векторов {f₁, f₂} дуальной решетки, f₁:=(d,0), f₂:=(-z′,1), с целочисленными коэффициентами {m₁,m₂} и длиной ||f||:={(dm₁-z′m₂)²+(m₂)²}^1/2>0, имеет наименьший ненулевой вектор f_min с длиной a_min ⁽²⁾(z′):=||f_min||>0, удовлетворяя условию ρ_d ⁽²⁾(z′):=2^1/2d^1/2/{3^1/4a_min ⁽²⁾(z′)}<l,25. 6 ил.

Способ использования мультипликативного конгруэнтного генератора (d, z) равномерно распределенных и независимых случайных чисел с нечетным модулем d и множителем z, взаимно простым с d, который начинает с произвольно заданного целого числа n, взаимно простого с d, и рекуррентно порождает последовательность целых чисел {r₀, r₁, r₂, …} при помощи отношений конгруэнтности
r₀≡n mod(d), 0<r₀<d,
r_k≡zr_k-1 mod(d), 0<r_k<d, k=1, 2, 3, …,
и дает на выходе случайные числа {v_k:=r_k-1/d| k=1, 2, …}, при этом множитель z выбран таким образом, что удовлетворяет условию, что генератор (d,z′) при z′≡z^j mod(d) для целого j по меньшей мере в диапазоне 1≤j≤6 проходит спектральный тест второй степени в пределах оценки 1,25, а именно, для любого целого j в диапазоне 1≤j≤6 генератор (d, z′) при z′≡z^j mod(d) удовлетворяет условию, что вектор f дуальной решетки, заданный для (d, z′) посредством линейной комбинации f:=m₁f₁+m₂f₂ базисных векторов {f₁, f₂} дуальной решетки,
f₁:=(d,0), f₂:=(-z′,1),
с целочисленными коэффициентами {m₁,m₂} и длиной
||f||:={(dm₁-z′m₂)²+(m₂)²}^1/2>0,
имеет наименьший ненулевой вектор f_min с длиной a_min ⁽²⁾(z′):=||f_min||>0, удовлетворяя условию
ρ_d ⁽²⁾(z′):=2^1/2d^1/2/{3^1/4a_min ⁽²⁾(z′)}<l,25.