Мне нужен алгоритм генератора псевдослучайных чисел для программы на ассемблере, назначенной в курсе, и я бы предпочел простой алгоритм. Однако я не могу использовать внешнюю библиотеку.
Что такое хороший простой алгоритм генератора псевдослучайных чисел для сборки?
Самый простой - просто выбрать два больших относительных простых числа a и b, затем продолжить умножение случайного числа на a и прибавление b. Используйте оператор по модулю, чтобы оставить младшие биты как случайное число и сохранить полное значение для следующей итерации.
Этот алгоритм известен как линейный конгруэнтный генератор.
Том 2 Искусство компьютерного программирования содержит много информации о генерации псевдослучайных чисел. Алгоритмы демонстрируются на ассемблере, поэтому вы можете сами убедиться, какие из них самые простые на ассемблере.
Однако, если вы можете ссылаться на внешнюю библиотеку или объектный файл, это будет вашим лучшим выбором. Затем вы можете создать ссылку, например, на Mersenne Twister.
Обратите внимание, что большинство генераторов псевдослучайных чисел небезопасны для криптографии, поэтому, если вам нужна безопасная генерация случайных чисел, вам нужно выйти за рамки основных алгоритмов (и, вероятно, следует использовать криптографические 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-битной арифметики. В развернутом виде тоже быстрее.
Почему бы не использовать внешнюю библиотеку ??? Это колесо изобретали несколько сотен раз, так зачем делать это снова?
Если вам нужно реализовать ГСЧ самостоятельно, нужно ли вам производить числа по запросу - то есть вы реализуете функцию rand () - или вам нужно создавать потоки случайных чисел - например, для тестирования памяти?
Вам нужен ГСЧ с криптостойкостью? Сколько времени должно пройти, прежде чем оно повторится? Вы должны абсолютно точно гарантировать равномерное распределение всех битов?
Вот простой прием, который я использовал несколько лет назад. Я работал со встроенным устройством, и мне нужно было проверить оперативную память при включении, и мне нужен был действительно небольшой, быстрый код и очень мало состояния, и я сделал следующее:
Это занимает очень мало кода (хотя вам нужна таблица для функции 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 и вычисления модуля. Если вы студент, их довольно просто реализовать на ассемблере, и, возможно, это именно то, что имел в виду лектор.
