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

Метки: 

Задач, в которых возникает необходимость генерировать случайные числа в заданном диапазоне значений, существует великое множество: это и игры, где создание разнообразных игровых полей, движение объектов да и довольно большое количество логики подчинено случайности, это и шифрование и другие области применения. Другими словами, любой уважающий себя разработчик всегда должен иметь под рукой генератор случайных чисел. При программировании на языках высокого уровня все достаточно прозаично, там имеется целый арсенал штатных функций, однако в ходе разработки кода на низкоуровневом языке Ассемблера зачастую приходится реализовывать процедуру создания случайного числа самостоятельно, изобретая велосипед от начала и до конца или заимствуя и дорабатывая чужой код :) Одним словом, возникает огроменное поле для творчества. При изучении большого количества материала, найденного в Сети, выяснилось что уже достаточно давно существует так называемый линейный конгруэнтный метод, как один из методов генерации псевдослучайных чисел, суть которого сводится к вычислению последовательности случайных чисел на основе начального значения с использованием достаточно простого алгоритма. Существует несколько вариаций метода, в том числе и смешанный конгруэнтный метод, самой известной реализацией которого является так называемый минимальный стандартный генератор случайных чисел, предложенный Стивеном Парком (Stephen Park) и Кейтом Миллером (Keith Miller) в 1988 году, так же называемый минимальным генератором Парка-Миллера. В общем то, не составило большого труда собрать воедино разрозненную информацию для написания "собственного" генератора случайных чисел на FASM.

Код я реализовал в виде процедуры, что бы удобнее было использовать её в своих проектах, вот и сам исходник:

Я попытался сделать процедуру GetRandomNumber наиболее универсальной в использовании, поэтому она принимает на входе два параметра: minValue и maxValue, задающие (соответственно) начальное и конечное числа диапазона, в котором сформируется псевдослучайное число. Код процедуры начинается (строка 3) с помещения в регистр eax стартового/предыдущего числа последовательности (переменная seed). Если обратить внимание на описание линейного конгруэнтного метода, то можно заметить, что значение переменной используется в качестве и начального либо предыдущего при генерировании текущего члена последовательности. В строке 4 мы проверяем не является ли стартовое/предыдущее число нулевым, и если оно таковым является (что недопустим для алгоритма) - то уходим на генерирование стартового числа при помощи системной функции GetTickCount (строка 7), возвращающей количество миллисекунд, прошедших с момента запуска системы, а затем инициализируем переменную seed полученным значением. Таким образом, функция GetTickCount используется у нас для создания стартового члена последовательности, а так же в случае, если любой член последовательности оказался нулевым.

Заместо функции GetTickCount можно было бы использовать инструкцию rdtsc, которая выполняется заметно быстрее, однако она имеет ряд ограничений и не до конца мной оттестирована.

В строках 11-27 реализован непосредственно сам алгоритм генерирования случайного числа. Давайте рассмотрим его подробнее. В строках 11-13 происходит деление предыдущего числа последовательности на константу 127773 (которая является одной из констант в формуле линейного конгруэнтного метода). Затем частное от деления сохраняем в стек, и умножаем получившийся остаток на вторую константу 16807. Далее восстанавливаем сохраненное частное от первого деления из стека, сохраняем в стек частное от второго деления, перемножаем частное от первого деления с третьей константой 2836. Восстанавливаем из стека частное от второго деления, вычитаем из неё значение результата перемножения и получившееся значение сохраняем в переменную seed для использования при вычислении следующего числа последовательности (при последующих вызовах процедуры). Но это еще не все, перед нами стоит задача создать число в заданном диапазоне, поэтому код в строках 25-31 предназначен для введения полученного случайного числа в заданный интервал (диапазон).
Отдельно бы хотелось поговорить о переменной seed. Поскольку она активно фигурирует в коде нашего генератора случайных чисел, переменная должна иметь разрядность двойного слова и размещаться в секции данных:

Конечно же, можно разместить переменную непосредственно в теле процедуры GetRandomNumber, однако в таком случае не забывайте выставлять атрибут writeable для секции кода, поскольку если этого не сделать запросто можно поймать исключение о нарушении прав доступа.

Инициализировать переменную seed необходимо именно значением 0, потому как при внимательном изучении кода процедуры можно заметить, что стартовое число генерируется только в том случае, если переменная равна 0, а все очередные значения последовательности вырабатываются вычислениями относительно предыдущего значения.
Вызов процедуры генерации случайного числа в коде приложения производится командой:

,где входные параметры A и B представляют из себя числа, определяющие соответственно начальное и конечное значения диапазона, в котором должно быть сгенерировано случайное число. Выходным параметром является регистр eax, в котором и возвращается случайное число.

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *