Blog. Just Blog

Генератор случайных чисел на Ассемблере

Версия для печати Добавить в Избранное Отправить на E-Mail | Категория: Образ мышления: Assembler | Автор: ManHunter
При написании программ часто возникает необходимость получить последовательность случайных чисел. В языках высокого уровня существуют штатные функции, а для Ассемблера я использую так называемый "Минимальный генератор Парка-Миллера" (Minimal portable random generator by Park and Miller). От аналогичных алгоритмов его отличает очень малый размер и равномерное распределение получаемых случайных чисел. Математическую модель и описание работы алгоритма можно без труда найти в интернете, поэтому эту информацию я здесь не привожу.
  1. ;---------------------------------------------
  2. ; Park Miller random number algorithm
  3. ; Получить случайное число 0 ... 99999
  4. ; stdcall WRandom
  5. ; на выходе EAX - случайное число 
  6. ;---------------------------------------------
  7. proc    WRandom
  8.         push    edx ecx
  9.         mov     eax,[random_seed]
  10.         xor     edx,edx
  11.         mov     ecx,127773
  12.         div     ecx
  13.         mov     ecx,eax
  14.         mov     eax,16807
  15.         mul     edx
  16.         mov     edx,ecx
  17.         mov     ecx,eax
  18.         mov     eax,2836
  19.         mul     edx
  20.         sub     ecx,eax
  21.         xor     edx,edx
  22.         mov     eax,ecx
  23.         mov     [random_seed],ecx
  24.         mov     ecx,100000
  25.         div     ecx
  26.         mov     eax,edx
  27.         pop     ecx edx
  28.         ret
  29. endp
  30.  
  31. ;---------------------------------------------
  32. ; Получить случайное число в нужном интервале
  33. ; Требуется процедура WRandom
  34. ; stdcall WIRandom,min,max
  35. ; на выходе EAX - случайное число   
  36. ;---------------------------------------------
  37. proc    WIRandom rmin:dword,rmax:dword
  38.         push    edx ecx
  39.         mov     ecx,[rmax]
  40.         sub     ecx,[rmin]
  41.         inc     ecx
  42.         stdcall WRandom
  43.         xor     edx,edx
  44.         div     ecx
  45.         mov     eax,edx
  46.         add     eax,[rmin]
  47.         pop     ecx edx
  48.         ret
  49. endp
  50.  
  51. ;---------------------------------------------
  52. ; Инициализация генератора случайных чисел
  53. ; stdcall WRandomInit 
  54. ;---------------------------------------------
  55. proc    WRandomInit
  56.         push    eax edx
  57.         rdtsc
  58.         xor     eax,edx
  59.         mov     [random_seed],eax
  60.         pop     edx eax
  61.         ret
  62. endp
После небольшой доработки он получил возможность генерировать случайные числа в заданном интервале.

Пример использования генератора:
  1. ; Сегмент данных
  2. section '.data' data readable writeable
  3. ...
  4. random_seed dd 0  ; Переменная для хранения промежуточных результатов
  5.                   ; работы генератора
  6.  
  7. ; Сегмент кода
  8. section '.code' code readable executable
  9. ...
  10. ; Инициализация генератора
  11. stdcall  WRandomInit
  12.  
  13. ; Получить случайное число в интервале  0...99999
  14. stdcall  WRandom
  15. ; EAX=случайное число
  16.  
  17. ; Получить случайное число в интервале min...max (включая границы)
  18. stdcall  WIRandom,5,20
  19. ; EAX=случайное число в интервале от 5 до 20
Примечание: процедура инициализации должна обязательно вызываться перед первым обращением к генератору, а переменная random_seed должна находиться в сегменте, доступном для записи. При вызове процедуры WIRandom дополнительных проверок на правильность границ не производится, на их последовательность (условие min < max) - тоже.

UPD: с подачи Дениса Внукова был выявлен серьезный косяк генератора. При нулевом или очень большом (типа 0xFFFFFFFE) значении random_seed генератор намертво зацикливался, возвращая каждый раз 0. Это можно обойти, добавив в WRandom дополнительную проверку значения random_seed. Как побочный положительный момент, генератор становится самоинициализирующимся и больше не требует вызова WRandomInit. Функция WIRandom остается без изменений.
  1. ;---------------------------------------------
  2. ; Park Miller random number algorithm
  3. ; Получить случайное число 0 ... 99999
  4. ; stdcall WRandom
  5. ; на выходе EAX - случайное число
  6. ;---------------------------------------------
  7. proc    WRandom
  8.         push    edx ecx
  9.         mov     eax,[random_seed]
  10.         ; Модификация против зацикливания генератора
  11.         ; на случай если в random_seed будет нулевое значение
  12.         or      eax,eax
  13.         jnz     @f
  14.         ; Инициализация генератора при первом вызове или зацикливании
  15.         rdtsc
  16.         xor     eax,edx
  17.         mov     [random_seed],eax
  18. @@:
  19.         xor     edx,edx
  20.         mov     ecx,127773
  21.         div     ecx
  22.         mov     ecx,eax
  23.         mov     eax,16807
  24.         mul     edx
  25.         mov     edx,ecx
  26.         mov     ecx,eax
  27.         mov     eax,2836
  28.         mul     edx
  29.         sub     ecx,eax
  30.         xor     edx,edx
  31.         mov     eax,ecx
  32.         mov     [random_seed],ecx
  33.         mov     ecx,100000
  34.         div     ecx
  35.         mov     eax,edx
  36.         pop     ecx edx
  37.         ret
  38. endp
Спасибо Денису за указанный косяк в реализации алгоритма. Если для реализации вашего проекта требуется более мощный генератор случайных чисел, то можете посмотреть еще вот такой вариант.

Поделиться ссылкой ВКонтакте Поделиться ссылкой на Facebook Поделиться ссылкой на LiveJournal Поделиться ссылкой в Мой Круг Добавить в Мой мир Добавить на ЛиРу (Liveinternet) Добавить в закладки Memori Добавить в закладки Google
Просмотров: 21609 | Комментариев: 7

Внимание! Статья опубликована больше года назад, информация могла устареть!

Комментарии

Отзывы посетителей сайта о статье
ManHunter (04.12.2012 в 08:43):
Иван, если прочитать еще что-то кроме "Информатики для младших классов", то можно обнаружить тот факт, что параметрами генераторов случайных чисел кроме быстродействия являются такие характеристики, как период, качество покрытия, взаимозависимость между соседними числами и другие. Именно для достижения максимальной случайности и пишутся все ГСЧ длинной более чем "всего из 5-6 сторк" (С). Поэтому свою категоричность оставь для школьных уроков. И да, чтоб ты знал, самый охуенный ГСЧ был под DOS'ом, он занимает всего одну строчку кода и совсем не использует регистры. Но это так, для общего развития.

Шедевр про "внешнюю оперативную память" понравился. Проверь книжку на всякий случай, там похоже вкралась опечатка. Память бывает внешняя ИЛИ оперативная, но не вместе.
Иван (03.12.2012 в 23:57):
Ну, что сказать всё это ерунда. Всё начинаем сначало. Если поискать книжку по схемотехнике цифровых устойств. То в ней есть описание генератора псевдослучайной последовательности из одного регистра. Если понять как он работает,то не трудно написать код на ассемблере всего из 5-6 сторк. И это будет наиболее оптимальным вариантом по быстродействию. Проверено на личном опыте. Писал подпрограммы проверки внешней оперативной памяти объёмом 256 кБ. Время выполнения около 1 секунды.
Agranom (24.12.2010 в 22:10):
Спасибо огоромное, целиком куросовую на этом генираторе построил!
Strike (16.06.2010 в 18:07):
ELM есть в твоей функции пара недочетов:
1)  не xchg esi,eax, а  xchg eax,esi позволяет сэкономить 1 байт и увеличивает скорость.
2)xor edx,esi
  xor edx,edx
Данные команды бесполезны т.к. последняя стирает результат предыдущей.
ELM (23.03.2010 в 11:00):
я использую такую иницыацыю
proc RandomNum,Min,Max   ;на выходе в eax рандом байт в диапазоне
        push ecx edx ebx edi esi
        rdtsc
;        push    eax
        xchg    esi,eax
        xchg    edi,edx
;        pop     eax
;        and     eax,0x000000ff   
;        invoke  Sleep,eax       
        rdtsc
        xor     eax,edi
        xor     edx,esi
        xor     edx,edx
        mov     ecx,[Max]
        add     ecx,1h
        sub     ecx,[Min]
        div     ecx
        add     edx,[Min]
        mov     eax,edx
        pop esi edi ebx edx ecx
        ret
endp
Norbert123 (11.03.2010 в 02:07):
спасибо
(я моленько сплагиатю данный код :-)
Rambler (05.10.2009 в 20:57):
THX!

Добавить комментарий

Заполните форму для добавления комментария
Имя*:
Текст комментария (не более 2000 символов)*:

*Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п., а также флуд и сообщения не по теме, будут удаляться. Нарушителям может быть заблокирован доступ к сайту.
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2017
При использовании материалов ссылка на сайт обязательна
Время генерации: 0.09 сек. / MySQL: 2 (0.0037 сек.) / Память: 4.5 Mb
Наверх