Blog. Just Blog

Еще один генератор случайных чисел на Ассемблере

Версия для печати Добавить в Избранное Отправить на E-Mail | Категория: Образ мышления: Assembler | Автор: ManHunter
В закромах Родины нашлась реализация еще одного генератора случайных чисел. Он более громоздкий, чем минимальный генератор Парка-Миллера, использует операции с плавающей точкой и кольцевой буфер, но результаты выдает гораздо лучше. Кроме большого кода ему также требуется больше места и в сегменте данных:
  1. section '.data' data readable writeable
  2.  
  3. ; Данные для генератора случайных чисел
  4. JJ      =       10             ; lag 1
  5. KK      =       17             ; lag 2, size of circular buffer
  6. R1      =       19             ; rotate count
  7. R2      =       27             ; rotate count
  8. randp1  dt      1.5            ; used for conversion to float
  9.         dw      0              ; alignment
  10. p1      dd      0              ; pointer in circular buffer
  11. p2      dd      0              ; pointer in circular buffer
  12. randbuf dd      (2*KK) dup(?)  ; circular buffer
Перед первым использованием генератор требуется инициализировать, вызвав функцию WRandomInit с каким-нибудь случайным значением, например, количеством тиков таймера:
  1.         ; Инициализация генератора случайных чисел
  2.         invoke  GetTickCount
  3.         stdcall WRandomInit,eax
  4.         ...
После инициализации генератор можно использовать в двух режимах: генерация одиночного случайного числа размером в два двойных слова (функция WRandom) или генерация случайного числа в заданном диапазоне от 1 до 0FFFFFFFEh (функция WIRandom). Формулировка "одиночное случайное число", наверное, не совсем подходит по смыслу к выполняемому действию, но тавтология "произвольное случайное число" мне показалась хуже.
  1.         ; Получить случайное число
  2.         stdcall WRandom
  3.         ; В регистрах EDX:EAX случайное число
  4.         ...
  5.         ; Получить случайное число от 1000 до 100000
  6.         stdcall WIRandom,1000,100000
  7.         ; В регистре EAX случайное число
  8.         ...
Одиночное случайное число возвращается в паре регистров EDX:EAX, случайное число из заданного интервала возвращается в регистре EAX. Если границы указаны неправильно, то EAX=80000000h. А вот и сам код генератора, данные к нему описаны выше.
  1. ;---------------------------------------------
  2. ; Получить случайное число
  3. ; stdcall WRandom
  4. ; на выходе EDX:EAX - случайное число
  5. ;---------------------------------------------
  6. proc    WRandom
  7.         stdcall WBRandom
  8.         or      edx, 80000000h
  9.         mov     dword [randp1],eax
  10.         mov     dword [randp1+4],edx
  11.         fld1
  12.         fld     [randp1]
  13.         ret
  14. endp
  15.  
  16. ;---------------------------------------------
  17. ; Получить случайное число в нужном интервале
  18. ; stdcall WIRandom,min,max
  19. ; на выходе EAX - случайное число
  20. ; EAX=80000000h - ошибка
  21. ;---------------------------------------------
  22. proc    WIRandom rmin:dword,rmax:dword
  23.         push    ebx
  24.  
  25.         stdcall WBRandom
  26.         ; Проверить корректность задания границ, MIN<MAX
  27.         mov     ebx,[rmax]
  28.         sub     ebx,[rmin]
  29.         js      .WIRandom_1
  30.         inc     ebx
  31.         mov     ecx,edx
  32.         mul     ebx
  33.         mov     eax,ecx
  34.         mov     ecx,edx
  35.         mul     ebx
  36.         add     eax,ecx
  37.         adc     edx,[rmin]
  38.         mov     eax,edx
  39.  
  40.         pop     ebx
  41.         ret
  42.  
  43. .WIRandom_1:
  44.         mov     eax,80000000h
  45.         pop     ebx
  46.         ret
  47. endp
  48.  
  49. ;---------------------------------------------
  50. ; Инициализация генератора случайных чисел
  51. ; stdcall WRandomInit,seed
  52. ;---------------------------------------------
  53. proc    WRandomInit seed:dword
  54.         mov     eax,[seed]
  55.         xor     ecx,ecx
  56. .WRandomInit_1:
  57.         imul    eax,2891336453
  58.         inc     eax
  59.         mov     [randbuf+ecx*4],eax
  60.         inc     ecx
  61.         cmp     ecx,KK*2
  62.         JB      .WRandomInit_1
  63.  
  64.         fld1
  65.         fstp    [randp1]
  66.         mov     [p1],0
  67.         mov     [p2],JJ*8
  68.         stdcall WBRandom
  69.  
  70.         push    edi
  71.  
  72.         mov     edi,30
  73. .WRandomInit_2:
  74.         stdcall WBRandom
  75.         dec     edi
  76.         jnz     .WRandomInit_2
  77.  
  78.         pop     edi
  79.         ret
  80. endp
  81.  
  82. ;---------------------------------------------
  83. ; Вспомогательная процедура генератора
  84. ; В пользовательском не вызывается
  85. ;---------------------------------------------
  86. proc    WBRandom
  87.         push    ebx
  88.         mov     ebx, [p1]
  89.         mov     ecx, [p2]
  90.         mov     edx, [randbuf+ebx]
  91.         mov     eax, [randbuf+ebx+4]
  92.  
  93.         rol     edx, R1
  94.         rol     eax, R2
  95.         add     edx, [randbuf+ecx]
  96.         add     eax, [randbuf+ecx+4]
  97.         mov     [randbuf+ebx], eax
  98.         mov     [randbuf+ebx+4], edx
  99.         sub     ebx, 8
  100.         jnc     .WBRandom_1
  101.         mov     ebx, (KK-1)*8
  102. .WBRandom_1:
  103.         sub     ecx, 8
  104.         jnc     .WBRandom_2
  105.         mov     ecx, (KK-1)*8
  106. .WBRandom_2:
  107.         mov     [p1], ebx
  108.         mov     [p2], ecx
  109.         pop     ebx
  110.         ret
  111. endp
Этот генератор можно использовать в проектах, где требуется более широкий разброс случайных чисел, нежели выдает генератор Парка-Миллера, и где не так критична минимизация кода.

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

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

Комментарии

Отзывы посетителей сайта о статье
Grey (01.10.2015 в 16:40):
СЛЧИС() и другая по мелким делам устраивают. Иногда (я так и не понял при каких обстоятельствах) они дают повтор последовательности один в один. На vscript, штатная Rnd() вообще 100% повтор дает при новом запуске, а СЛЧИС() имхо на ее основе построена. Мы тут модель вероятностную в екселе сделали, чисел больше 100 000 плюс еще другие формулы, она повторы дает, может глюк какой. В общем выпала из доверия.
ManHunter (01.10.2015 в 15:54):
Чем не устроили штатные =СЛЧИС() или =СЛУЧМЕЖДУ(1;100) ?

ЦитатаЯ так понимаю это из за GetTickCount, чем ее заменить?

GetTickCount используется для инициализации ГПСЧ, то есть должна вызываться только один раз и обязательно где-то за пределами функции получения случайного числа. Да и заменить ее нечем, в винде не предусмотрено системных функций для получения случайных значений. Под MS-DOS была изумительная по лаконичности команда для получения случайного байта "in al,40h", а тут увы.
Grey (01.10.2015 в 15:32):
Приклеил я эту функцию к Excel. Вызываю ее в ячейках, пока вызываешь в рукопашку - все путем. Поле протягивания дает одинаковые значения, вот копия с листа:
-2094149727
690108166
-702905294
-1496552323
464573972
1424549589 - тут началось протягивание
1114009017
1114009017
1114009017
1114009017
Я так понимаю это из за GetTickCount, чем ее заменить?
ManHunter (12.12.2011 в 14:36):
Как зависит генерация от мощности компьютера? Не пиши ерунду.
Старк (12.12.2011 в 14:34):
Этот генератор на мощном компьютере одно и тоже число выдавать не будет?
Fedor666 (02.06.2011 в 22:02):
Где, интересно знать, результаты тестов этого чуда? Ent? Deadhard :)
4RESTER (27.10.2010 в 01:36):
Классический приличный RNG -- Mersenne Twister.
serega386 (20.09.2010 в 20:36):
proc    WRandom
        stdcall WBRandom
        or      edx, 80000000h
        mov     dword [randp1],eax
        mov     dword [randp1+4],edx
>>>     fld1
>>>     fld  [randp1]
        ret
endp

>>> для чего эти команды?
ManHunter (17.05.2010 в 10:26):
Я его тестил на больших числах, там он конечно рулит.
Zummenix (17.05.2010 в 09:41):
100 проходов, числа в диапазоне от 1 до 100:
62,30,63,53,66,41,67,11,61,4,85,28,65,73,10,83,4,6,86,32,43,25,62,54,3 6,64,60,69,97,79,43,13,56,68,64,93,23,14,94,28,72,60,8,65,52,7,62,53,4 6,17,53,83,24,45,13,65,48,60,71,44,27,70,39,9,22,24,24,56,80,93,32,55, 82,95,80,21,35,94,38,89,48,69,31,80,43,77,65,81,27,22,56,36,31,3,96,43 ,45,26,87,20
Очень даже неплохо, но некоторые числа повторяются, а некоторых вообще нет :)

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

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

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