Джорджем Марсаглией, позднее, был написан ещё более мощный алгоритм генерации
случайных чисел и он был назван им "Mother-of-All random
number". Этот алгоритм базируется на умножении с переносом и имеет период
2^250. Реализация и этого алгоритма на ассемблере была сделана Агнером Фогом и увидеть
её вы можете на его домашней странице.
Но предыдущие алгоритмы не подходят в тех случаях, когда необходима скорость.
Поэтому, всё тем же Джорджем Марсаглией был разработан очень быстрый
PRNG. Назвал он его "Xorshift". Преимуществом данного алгоритма является его
скорость, данный PRNG в 5 раз быстрее, чем "Marsaglia-Multicarry". Он как и
предыдущие алгоритмы данного автора прошёл тесты DIEHARD. Данные тесты
определяют пригодность генератора псевдослучайных чисел к применению в
статистике.
Далее рассмотрим реализацию данного алгоритма на С:
unsigned long xor128()
{
static unsigned long x3456789,
y62436069,
zR1288629,
wИ675123;
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
mov ecx,521288629
z = dword ptr $-4
mov [ebp+y],ecx
mov ebx,88675123
w = dword ptr $-4
mov [ebp+z],ebx
mov edx,[ebp+w]
shr edx,13h
xor edx,[ebp+w]
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" рекомендует увеличить количество операций
до 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.
