Maximize
Bookmark

VX Heaven

Library Collection Sources Engines Constructors Simulators Utilities Links Forum

Генерация случайных чисел

Sl0n
2005

[Вернуться к списку] [Комментарии]
"Кто говорит, тот не знает
А кто знает, тот не говорит"

Древне китайская мудрость


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

ГПСЧ (PRNG) это генераторы псевдо-случайных чисел. Никакой детерминированный алгоритм не может генерировать полностью случайные числа, а только лишь аппроксимировать некоторые свойства случайных чисел. Еще Джон фон Нейман говорил, что только лишь арифметическими методами случайное число получить не возможно. Любой ГПСЧ с ограниченными ресурсами рано или поздно зацикливается.

Большинство простых арифметических генераторов хотя и обладают большой скоростью, но страдают от многих серьезных недостатков:

В компиляторах широкое распространение получил линейный конгруэнтный метод. Применяется в простых случаях и не обладает криптографической стойкостью. Этот алгоритм заключается в итеративном применении следующей формулы:

X[k+1]=(a*X[k]+c) mod m

Этот алгоритм используется в ANSI-C. Рассмотрим его:

#define RAND_MAX 32767

unsigned long next=1;

int rand(void) {
 next=next*1103515245+12345;
 return((unsigned int)(next/65536)%32768);
}

void srand(unsigned int seed) {
 next=seed;
}
 

Где a > 0, c > 0, m > 0 - некоторые целочисленные константы. Получаемая последовательность зависит от выбора стартового числа X0 и при разных его значениях получаются различные последовательности случайных чисел. В то же время, многие свойства последовательности Xk определяются выбором коэффициентов в формуле и не зависят от выбора стартового числа. Ясно, что последовательность чисел, генерируемая таким алгоритмом, периодична с периодом, не превышающим m. При этом длина периода равна m тогда и только тогда, когда:

  1. НОД(c,m) = 1 (т.е. c и m взаимно просты);
  2. a - 1 кратно p для всех простых p - делителей m;
  3. a - 1 кратно 4, если m кратно 4.

При реализации выгодно выбирать m = 2e, где e - число бит в машинном слове, поскольку это позволяет избавиться от относительно медленной операции приведения по модулю. Младшие двоичные разряды сгенерированных таким образом случайных чисел демонстрируют поведение, далекое от случайного, поэтому рекомендуется использовать только старшие разряды.

Для генерации числа в диапазоне *0 - 2^32 -1* достаточно простого умножения на мультипликатор и сложения с инкрементом. Деление по модулю будет произведено автоматически при переполнении. Значения мультипликатора и инкремента для этого случая получены в исследованиях D. Knuth и H.W. Lewis.

Они рекомендуют использовать следующие коэффициенты: a = 1664525, c = 1013904223, m = 2^32

Вот этой формулой рекомендуют пользоваться для генерации 32 битного числа.

next=1664525*next+1013904223;

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

;%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%;
; ГЕНЕРАТОР СЛУЧАЙНОГО ЧИСЛА V. 0.3 (x) 2004 СЛОН                              ;
; Линейный конгруэнтный генератор он не прошел тест DIEHARD и не               ;
; является криптостойким                                                       ;
;%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%;
; Интервал:             [0..eax-1]                                             ;
;------------------------------------------------------------------------------;
; Использование:        call       r_init                                         ;
;                       mov     eax,ГРАНИЦА ИНТЕРВАЛА                          ;
;                       call    brandom32                                      ;
;------------------------------------------------------------------------------;
; Результат:           число в интервале [0..ГРАНИЦА ИНТЕРВАЛА]               ;
;%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%;

;----[Подпрограмма инициализации генератора случайных чисел]-------------------;

r_init:
                push    ebp eax edx             ; Сохраняем в стэке ebp,
                                                ; eax, edx

                call    __delta1_               ;
__delta1_:      pop     ebp                     ; Получение дельта смещения
                sub     ebp,offset __delta1_    ;

                db      0fh,031h                ; Получаем случайное зерно
                mov     rand_seed,eax           ;

                pop     edx eax ebp             ; Восстанавливаем edx,
                                                ; eax, ebp

                ret                             ; Возврат из подпрограммы

;----[Подпрограмма генерации случаного чмсла в диапазоне]----------------------;

brandom32:                                      ; Эта подпрограмма
                                                ; возвращает случайное число
                                                ; в диапазоне 0..eax-1

                push    edx ecx ebp             ; Сохраняем в стэке edx,
                                                ; ecx, ebp

                call    __delta2_               ;
__delta2_:      pop     ebp                     ; Получение дельта смещения
                sub     ebp,offset __delta2_    ;

                imul    eax,eax,100             ; Умножаем eax на 100
                push    eax                     ; и сохраняем eax в стэке

                call    random32                ; Вызываем подпрограмму
                                                ; генерации случайного числа
                xor     edx,edx                 ; Обнуляем edx
                pop     ecx                     ; Восстанавливаем значение
                                                ; из стэка в ecx
                div     ecx                     ; Делим eax на ecx
                xchg    eax,edx                 ; Помещаем остаток в eax
                xor     edx,edx                 ; Обнуляем edx
                push    100                     ; Помещаем в ecx - 100
                pop     ecx                     ;
                div     ecx                     ; Делим eax на ecx
                pop     ebp ecx edx             ; Восстанавливаем ebp, ecx,
                                                ; edx
                ret                             ; Возврат из подпрограммы

;----[Подпрограмма генерации случайного числа]---------------------------------;

random32:
                push    ebp

                call   
__delta3_               ;
__delta3_:      pop     ebp                     ; Получение дельта смещения
                sub     ebp,offset __delta3_    ;

                mov     eax,12345678h           ;
                rand_seed= dword ptr $-4        ;
                imul    eax,00019660Dh          ;
                add     eax,03C6EF35Fh          ; Математические операции
                mov     [ebp+rand_seed],eax     ; для получения случайного
                shr     eax,16                  ; числа
                imul    eax,[esp+4]             ;

                pop     ebp

                retn                            ; Возврат из подпрограммы
 

Метод Фибоначчи с запаздываниями (Lagged Fibonacci generator) - один из методов, который используется для генерации псевдослучайных чисел.

Особенности распределения случайных чисел, выдаваемых линейным конгруэнтным алгоритмом, делает невозможным их использование в статистических алгоритмах, требующих высокого разрешения. Это происходит из-за малого периода и их предсказуемости. Поэтому линейный крнгруэнтный метод практически не используется ни в статистике, ни в криптографии. Обычно вместо него используют либо фибоначиевые алгоритмы (в английской литературе "Subtract-with-borrow Generators" (SWBG)), либо "Linear feedback shift registers".

Так же широкое распространение получил "Mersenne twister", разработанный в 1997 году Мацумото и Нишимурой. Выигрывает у других ГПСЧ громадным периодом (2^19937-1) и быстрой генерацией случайных чисел. Недостатком данного алгоритма является то, что существует возможность охарактеризовать выдаваемую последовательность, как не случайную. Именно по этой причине данный алгоритм не применим в криптографии. Агнер Фог разработал библиотеку реализующую Mersenne twister на ассемблере. Его домашняя страница находится по адресу: http://www.agner.org

До недавнего времени, оптимальным вариантом генерации псевдо случайных чисел был алгоритм Джорджа Марсаглии, который использует метод умножения с переносом. Называется алгоритм - "Marsaglia-Multicarry". Данный алгоритм достаточно быстрый и имеет различные периоды начиная с 2^60 Для его использования данного алгортима на языке программирования "С", достаточно вставить эту функцию в начале программы:

unsigned long mwc()
{
static unsigned long x=123456789,
y=362436069,
z=77465321,
c=13579;
unsigned long long t;
t=916905990LL*x+c;
x=y;
y=z;
c=(t>>32);
return z=(t&0xffffffff);
}
 

После этого используйте MWC() для генерации целого 32 битного числа. Данная функция имеет период где-то 2^125. Она с легкостью прошла тесты DIEHARD и единственным ее недостатком является использование умножения, которое значительно влияет на скорость работы данного ГПСЧ.

Вот ее реализация на ассемблере:

                                                                             ;
;%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%;
; ГЕНЕРАТОР СЛУЧАЙНОГО ЧИСЛА V. 0.41 (x) 2005 СЛОН                             ;
;%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%;
; Интервал:             [0..eax-1]                                             ;
;------------------------------------------------------------------------------;
; Используется алгоритм ГПСЧ Джорджа Марсаглии - "Multiply-With-Carry(MWC)"    ;
; Данный алгоритм прошел тест DIEHARD его период 2^125                         ;
;------------------------------------------------------------------------------;
; Использование:        call       r_init                                         ;
;                       mov     eax,ГРАНИЦА ИНТЕРВАЛА                          ;
;                       call    brandom32                                      ;
;------------------------------------------------------------------------------;
; Результат:           число в интервале [0..ГРАНИЦА ИНТЕРВАЛА]               ;
;%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%;

;----[Подпрограмма инициализации генератора случайных чисел]-------------------;

r_init:
                push    ebp eax edx             ; Сохраняем в стэке ebp,eax,edx

                call    __delta1_               ;
__delta1_:      pop     ebp                     ; Получение дельта смещения
                sub     ebp,offset __delta1_    ;

                db      0fh,031h                ; Получаем случайное зерно
                mov     [ebp+x],eax             ;

                pop     edx eax ebp             ; Восстанавливаем edx,eax,ebp

                ret                             ; Возврат из подпрограммы

;----[Подпрограмма генерации случаного чмсла в диапазоне]----------------------;

brandom32:                                      ; Эта подпрограмма
                                                ; возвращает случайное число
                                                ; в диапазоне 0..eax-1

                push    edx ecx ebp             ; Сохраняем в стэке edx,ecx,ebp

                call    __delta2_               ;
__delta2_:      pop     ebp                     ; Получение дельта смещения
                sub     ebp,offset __delta2_    ;

                imul    eax,eax,100             ; Умножаем eax на 100
                push    eax                     ; и сохраняем eax в стэке

                call    random32                ; Вызываем подпрограмму
                                                ; генерации случайного числа
                xor     edx,edx                 ; Обнуляем edx
                pop     ecx                     ; Восстанавливаем значение
                                                ; из стэка в ecx
                div     ecx                     ; Делим eax на ecx
                xchg    eax,edx                 ; Помещаем остаток в eax
                xor     edx,edx                 ; Обнуляем edx
                push    100                     ; Помещаем в ecx - 100
                pop     ecx                     ;
                div     ecx                     ; Делим eax на ecx
                pop     ebp ecx edx             ; Восстанавливаем ebp,ecx,edx,
                ret                             ; Возврат из подпрограммы

;----[Подпрограмма генерации случайного числа]---------------------------------;

random32:
                push    edx ecx                 ;
                push    ebp                     ; Сохраняем регистры в стэке

                call    __delta3_               ;
__delta3_:      pop     ebp                     ; Получение дельта смещения
                sub     ebp,offset __delta3_    ;

                mov     eax,123456789           ; Генерируем СЧ по алгоритму
                x = dword ptr $-4               ; "Multipy-With-Carry(MWC)"
                mov     edx,916905900           ; алгоритму данная часть
                t = dword ptr $-4               ; выглядела бы на С так:
                mul     edx                     ; unsigned long x=123456789,
                xor     ecx,ecx                 ; y=362436069,
                xchg    ecx,edx                 ; z=77465321,
                add     eax,13579               ; c=13579;
                c = dword ptr $-4               ; unsigned long long t;
                adc     edx,ecx                 ; t=916905990LL*x+c;
                mov     ecx,362436069           ; x=y;
                y = dword ptr $-4               ; y=z;
                mov     [ebp+x],ecx             ; c=(t>>32);
                mov     ecx,77465321            ; return z=(t&0xffffffff);
                z = dword ptr $-4               ;
                mov     [ebp+y],ecx             ;
                mov     [ebp+c],edx             ;
                mov     [ebp+z],eax             ;

                pop     ebp                     ;
                pop     ecx edx                 ; Вынимаем регистры из стэка

                retn                            ; Возврат из подпрограммы
 

Джорджем Марсаглией, позднее, был написан еще более мощный алгоритм генерации случайных чисел и он был назван им "Mother-of-All random number". Этот алгоритм базируется на умножении с переносом и имеет период 2^250. Реализация и этого алгоритма на ассемблере была сделана Агнером Фогом и увидеть ее вы можете на его домашней странице.

Но предидущие алгоритмы не подходят в тех случаях, когда необходима скорость. Поэтому, все тем же Джорджем Марсаглией был разработан очень быстрый PRNG. Назвал он его "Xorshift"[3]. Преимуществом данного алгоритма является его скорость,данный PRNG в 5 раз быстрее, чем "Marsaglia-Multicarry". Он как и предидущие алгоритмы данного автора прошел тесты DIEHARD. Данные тесты определяют пригодность генератора псевдо случайных чисел к применению в статистике.

Далее рассмотрим реализацию данного алгоритма на С:

unsigned long xor128()
{
static unsigned long x=123456789,
y=362436069,
z=521288629,
w=88675123;
unsigned long t;
t=(x^(x<<11));x=y;y=z;z=w;
return(w=(w^(w>>19))^(t^(t>>8)));
}
 

В данном алгоритме не используется умножение, а используется только битовые сдвиги и сложение по модулю 2(XOR). Рассмотрим листинг с реализацией данного алгоритма на ассемблере.

;%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%;
; ГЕНЕРАТОР СЛУЧАЙНОГО ЧИСЛА V. 0.42 (x) 2005 СЛОН                             ;
;%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%;
; Интервал:             [0..eax-1]                                             ;
;------------------------------------------------------------------------------;
; Используется алгоритм ГПСЧ Джорджа Марсаглии - "Xorshift - 128"              ;
; Данный алгоритм прошел тест DIEHARD его период 2^128-1                       ;
;------------------------------------------------------------------------------;
; Использование:        call       r_init                                         ;
;                       mov     eax,ГРАНИЦА ИНТЕРВАЛА                          ;
;                       call    brandom32                                      ;
;------------------------------------------------------------------------------;
; Результат:           число в интервале [0..ГРАНИЦА ИНТЕРВАЛА]               ;
;%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%;

;----[Подпрограмма инициализации генератора случайных чисел]-------------------;

r_init:
                push    ebp eax edx             ; Сохраняем в стэке ebp,eax,edx

                call    __delta1_               ;
__delta1_:      pop     ebp                     ; Получение дельта смещения
                sub     ebp,offset __delta1_    ;

                db      0fh,031h                ; Получаем случайное зерно
                mov     [ebp+x],eax             ;

                pop     edx eax ebp             ; Восстанавливаем edx,eax,ebp

                ret                             ; Возврат из подпрограммы

;----[Подпрограмма генерации случаного чмсла в диапазоне]----------------------;

brandom32:                                      ; Эта подпрограмма
                                                ; возвращает случайное число
                                                ; в диапазоне 0..eax-1

                push    edx ecx ebp             ; Сохраняем в стэке edx,ecx,ebp

                call    __delta2_               ;
__delta2_:      pop     ebp                     ; Получение дельта смещения
                sub     ebp,offset __delta2_    ;

                imul    eax,eax,100             ; Умножаем eax на 100
                push    eax                     ; и сохраняем eax в стэке

                call    random32                ; Вызываем подпрограмму
                                                ; генерации случайного числа
                xor     edx,edx                 ; Обнуляем edx
                pop     ecx                     ; Восстанавливаем значение
                                                ; из стэка в ecx
                div     ecx                     ; Делим eax на ecx
                xchg    eax,edx                 ; Помещаем остаток в eax
                xor     edx,edx                 ; Обнуляем edx
                push    100                     ; Помещаем в ecx - 100
                pop     ecx                     ;
                div     ecx                     ; Делим eax на ecx
                pop     ebp ecx edx             ; Восстанавливаем ebp,ecx,edx,
                ret                             ; Возврат из подпрограммы

;----[Подпрограмма генерации случайного числа]---------------------------------;

random32:
                push    ebx edx ecx             ;
                push    ebp                     ; Сохраняем регистры в стэке

                call    __delta3_               ;
__delta3_:      pop     ebp                     ; Получение дельта смещения
                sub     ebp,offset __delta3_    ;

                mov     eax,12345678            ;
                x = dword ptr $-4               ;
                shl     eax,0bh                 ; Выполняем математические
                xor     eax,[ebp+x]             ; преобразования по нужному нам
                mov     edx,362436069           ; алгоритму данная часть
                y = dword ptr $-4               ; выглядела бы на С так:
                mov     [ebp+x],edx             ; unsigned long x=123456789,
                mov     ecx,521288629           ; y=362436069,
                z = dword ptr $-4               ; z=521288629,
                mov     [ebp+y],ecx             ; w=88675123;
                mov     ebx,88675123            ; t=(x^(x<<11));x=y;y=z;z=w;
                w = dword ptr $-4               ; Где t в нашем случае eax
                mov     [ebp+z],ebx             ;
                mov     edx,[ebp+w]             ; Далее идут следующие
                shr     edx,13h                 ; вычисления, которые дают СЧ
                xor     edx,[ebp+w]             ; (w=(w^(w>>19))^(t^(t>>8)));
                xor     edx,eax                 ;
                shr     eax,08h                 ;
                xor     edx,eax                 ;
                mov     [ebp+w],edx             ;
                mov     eax,edx                 ;

                pop     ebp                     ;
                pop     ecx edx ebx             ; Вынимаем регистры из стэка

                retn                            ; Возврат из подпрограммы
 

Как самый оптимальый ГПСЧ для большинства приложений Джордж Марсаглия рекомендует "Xorshift". Если нужны очень большие периоды, тогда нужно использовать ГПСЧ базирующиеся на MWC или CMWC. Использование данных алгоритмов поволяет достигнуть периода 2^113102. Если же достаточно периодов: 2^160, 2^128, 2^96, тогда оптимальным вариантом будет "Xorshift". Данный алгоритм доказал свою стойкость пройдя тесты DIEHARD и может использоваться практически во всех областях.

Правда для серьезных работ, Пьер Льэкюир в своем тексте по анализу генераторов псевдо случайных чисел "Xorshift"[4], рекомендует увеличить количество операций до 7 ("seven xorshift generator"). Данной решение он мотивирует тем, что скорость работы генератора практически не уменьшится, а вот статистические характеристики значительно улучшаться.

При написании статьи использовались материалы:

  1. Marsaglia, George, 2003, Random number generators, Journal of Modern Applied Statistical Methods, 2 No. 2.
  2. Marsaglia, George and Tsang, Wai Wan, 2002, Some difficult-to-pass tests of randomness, Journal Statistical Software, 7, Issue 3.
  3. Marsaglia, George, 2003, Xorshift RNGs, Journal Statistical Software, 8, Issue 14.
  4. F. Panneton and P. L'Ecuyer, "On the Xorshift Random Number Generators", 2004, submitted.
[Вернуться к списку] [Комментарии]
By accessing, viewing, downloading or otherwise using this content you agree to be bound by the Terms of Use! vxer.org aka vx.netlux.org
deenesitfrplruua