Blog. Just Blog

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

Версия для печати Добавить в Избранное Отправить на E-Mail 03.09.2008 | Категория: Образ мышления: Assembler | Автор: ManHunter
При написании программ часто возникает необходимость получить последовательность случайных чисел. В языках высокого уровня существуют штатные функции, а для Ассемблера я использую так называемый "Минимальный генератор Парка-Миллера" (Minimal portable random generator by Park and Miller). От аналогичных алгоритмов его отличает очень малый размер и равномерное распределение получаемых случайных чисел. Математическую модель и описание работы алгоритма можно без труда найти в интернете, поэтому эту информацию я здесь не привожу.
Code (Assembler) : Убрать нумерацию
  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
После небольшой доработки он получил возможность генерировать случайные числа в заданном интервале.

Пример использования генератора:
Code (Assembler) : Убрать нумерацию
  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 остается без изменений.
Code (Assembler) : Убрать нумерацию
  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) Поделиться ссылкой на Friendfeed Добавить в Яндекс.Закладки Добавить в закладки Memori Добавить в закладки Google
Просмотров: 8535 | Комментариев: 5

Комментарии

Отзывы посетителей сайта о статье
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 символов)*:

Все поля обязательны для заполнения.
Комментарии, содержащие рекламу, ненормативную лексику, оскорбления и т.п. будут удаляться. Злостным нарушителям доступ к сайту может быть заблокирован.
Это я :-)
Если программист в девять утра уже на работе, значит он там же и ночевал
Главная страница Web-мастеру и не только Образ мышления: Assembler Мои программы Software Темная сторона Силы Обзоры техники А еще я туда ем! Жизнь в оффлайне Всякая всячина
Карта сайта Ссылки Обратная связь Правила сайта Настройки сайта RSS-канал

Вам помог этот сайт?
Сказать спасибо! Поблагодарили 7,542 раза
<< 2012 - МАЙ >>
Пн Вт Ср Чт Пт Сб Вс
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      
Нашли на сайте орфографическую ошибку? Выделите ее мышкой и нажмите
Ctrl
+
Пробел

Буду очень благодарен, если размеcтите мою кнопочку:
Личный блог ManHunter'а
Valid CSS Valid XHTML 1.0 Transitional Valid mobileOK Basic Valid RSS
Google PageRank: 3 Google PR: 3 Яндекс тИЦ: 70 Яндекс тИЦ: 70
Google Page Speed score: 94/100 Google Page Speed score: 94/100
Сейчас я слушаю
---
Имя:

Сообщение:

Осталось символов: 200

   
-
Наверх
Powered by PCL's Speckled Band Engine 0.2 RC3
© ManHunter / PCL, 2008-2012
При использовании материалов ссылка на сайт обязательна
Время генерации: 0,12 сек. / MySQL: 2 (0,0006 сек.) / Память: 3,5 Mb
Наверх