Генератор псевдослучайных чисел на языке ассемблера
Вопрос
Мне нужен алгоритм генератора псевдослучайных чисел для программы на ассемблере, заданной в курсе, и я бы предпочел простой алгоритм.Однако я не могу использовать внешнюю библиотеку.
Что такое хороший и простой алгоритм генератора псевдослучайных чисел для сборки?
Решение
Самый простой — просто выбрать два больших относительных простых числа a и b, затем продолжать умножать случайное число на a и прибавлять b.Используйте оператор по модулю, чтобы сохранить младшие биты в качестве случайного числа и сохранить полное значение для следующей итерации.
Этот алгоритм известен как линейный конгруэнтный генератор.
Другие советы
Том 2 Искусство компьютерного программирования содержит много информации о генерации псевдослучайных чисел.Алгоритмы демонстрируются на ассемблере, поэтому вы сами можете увидеть, какие из них на ассемблере самые простые.
Однако если вы можете создать ссылку на внешнюю библиотеку или объектный файл, это будет лучшим выбором.Тогда вы можете дать ссылку, например, Мерсенн Твистер.
Обратите внимание, что большинство генераторов псевдослучайных чисел нет безопасен для криптографии, поэтому, если вам нужна безопасная генерация случайных чисел, вам нужно выйти за рамки базовых алгоритмов (и, вероятно, следует использовать криптографические API для конкретной ОС).
Простой код для тестирования, не используйте с Crypto
Из «Тестирование компьютерного программного обеспечения», стр. 138.
При 32-битной математике вам не нужна операция MOD 2^32
RNG = (69069*RNG + 69069) MOD 2^32
Что ж, поскольку я не видел ссылки на старый добрый регистр сдвига с линейной обратной связью, я публикую некоторый встроенный C-код на основе SSE.Просто для полноты.Я написал эту вещь пару месяцев назад, чтобы еще раз отточить свои навыки SSE.
#include <emmintrin.h>
static __m128i LFSR;
void InitRandom (int Seed)
{
LFSR = _mm_cvtsi32_si128 (Seed);
}
int GetRandom (int NumBits)
{
__m128i seed = LFSR;
__m128i one = _mm_cvtsi32_si128(1);
__m128i mask;
int i;
for (i=0; i<NumBits; i++)
{
// generate xor of adjecting bits
__m128i temp = _mm_xor_si128(seed, _mm_srli_epi64(seed,1));
// generate xor of feedback bits 5,6 and 62,61
__m128i NewBit = _mm_xor_si128( _mm_srli_epi64(temp,5),
_mm_srli_epi64(temp,61));
// Mask out single bit:
NewBit = _mm_and_si128 (NewBit, one);
// Shift & insert new result bit:
seed = _mm_or_si128 (NewBit, _mm_add_epi64 (seed,seed));
}
// Write back seed...
LFSR = seed;
// generate mask of NumBit ones.
mask = _mm_srli_epi64 (_mm_cmpeq_epi8(seed, seed), 64-NumBits);
// return random number:
return _mm_cvtsi128_si32 (_mm_and_si128(seed,mask));
}
Перевод этого кода на ассемблер тривиален.Просто замените встроенные функции настоящими инструкциями SSE и добавьте вокруг них цикл.
Кстати, последовательность, которую генерирует этот код, повторяется после 4.61169E+18 чисел.Это намного больше, чем вы получите с помощью метода простых чисел и 32-битной арифметики.Если развернуть, то тоже быстрее.
@jjrv
То, что вы описываете, на самом деле является линейным конгрегентным генератором.Самые случайные биты — это старшие биты.Чтобы получить число от 0 до N-1, вы умножаете полное значение на N (32 бита на 32 бита, что дает 64 бита) и используете старшие 32 бита.
Вы не должны просто использовать любое число для а (множитель для перехода от одного полного значения к следующему), числа, рекомендованные Кнутом (таблица 1, раздел 3.3.4 TAOCP, том 2, 1981 г.), составляют 1812433253, 1566083941, 69069 и 1664525.
Вы можете просто выбрать любое нечетное число для б.(дополнение).
Почему бы не использовать внешнюю библиотеку???Это колесо изобретали несколько сотен раз, так зачем же делать его снова?
Если вам нужно реализовать ГСЧ самостоятельно, нужно ли вам создавать числа по требованию, т.е.реализуете ли вы функцию rand() или вам нужно создавать потоки случайных чисел, напримердля тестирования памяти?
Вам нужен RNG, обладающий криптостойкостью?Сколько времени должно пройти, прежде чем это повторится?Должны ли вы абсолютно точно гарантировать равномерное распределение всех битов?
Вот простой хак, который я использовал несколько лет назад.Я работал со встроенными системами, и мне нужно было протестировать оперативную память при включении питания, и мне нужен был очень маленький, быстрый код и очень мало состояний, и я сделал это:
- Начните с произвольной 4-байтовой константы в качестве начального числа.
- Вычислите 32-битную CRC этих 4 байтов.Это дает вам следующие 4 байта
- Верните эти 4 байта в алгоритм CRC32, как если бы они были добавлены.Следующим значением является CRC32 этих 8 байтов.
- Повторяйте столько, сколько хотите.
Это требует очень небольшого количества кода (хотя вам нужна таблица для функции crc32) и имеет очень мало состояний, но псевдослучайный выходной поток имеет очень долгое время цикла, прежде чем он повторится.Кроме того, для процессора не требуется SSE.И если у вас есть под рукой функция CRC32, реализовать ее несложно.
Использование masm615 для компиляции:
delay_function macro
mov cx,0ffffh
.repeat
push cx
mov cx,0f00h
.repeat
dec cx
.until cx==0
pop cx
dec cx
.until cx==0
endm
random_num macro
mov cx,64 ;assum we want to get 64 random numbers
mov si,0
get_num:
push cx
delay_function ;since cpu clock is fast,so we use delay_function
mov ah,2ch
int 21h
mov ax,dx ;get clock 1/100 sec
div num ;assume we want to get a number from 0~num-1
mov arry[si],ah ;save to array you set
inc si
pop cx
loop get_num ;here we finish the get_random number
также вы, вероятно, можете эмулировать сдвиговый регистр с элементами суммы XOR между отдельными битами, что даст вам псевдослучайную последовательность чисел.
Линейный конгруэнтный (X = AX+C mod M) PRNG может быть полезен для курса ассемблера, поскольку вашим ученикам придется иметь дело с битами переноса для промежуточных результатов AX более 2 ^ 31 и вычислением модуля.Если вы студент, их довольно просто реализовать на ассемблере, и, возможно, это именно то, что имел в виду преподаватель.