Псевдослучайный генератор на ассемблере

Question

Мне нужен алгоритм генератора псевдослучайных чисел для ассемблерной программы, назначенной в курсе, и я бы предпочел простой алгоритм. Однако я не могу использовать внешнюю библиотеку.

Что такое хороший, простой алгоритм генератора псевдослучайных чисел для сборки?

Answer 1

Легко выбрать два больших относительных простых числа a и b, затем умножить случайное число на a и добавить b. Используйте оператор по модулю, чтобы младшие биты оставались случайным числом, и сохраните полное значение для следующей итерации.

Этот алгоритм известен как линейный конгруэнтный генератор .

Answer 2

Простой код для тестирования, не используйте с Crypto

Из раздела «Тестирование компьютерного программного обеспечения», стр. 138

При использовании 32-битной математики операция не требуется MOD 2^32

RNG = (69069*RNG + 69069) MOD 2^32

Answer 3

Том 2 из Искусство компьютерного программирования содержит много информации о генерации псевдослучайных чисел. Алгоритмы демонстрируются на ассемблере, так что вы можете сами убедиться в простоте ассемблера.

Если вы можете сделать ссылку на внешнюю библиотеку или объектный файл, это будет лучшим выбором. Тогда вы можете указать ссылку, например, Mersenne Twister .

Обратите внимание, что большинство генераторов псевдослучайных чисел не безопасны для криптографии, поэтому, если вам нужно безопасное генерирование случайных чисел, вам нужно выйти за рамки базовых алгоритмов (и, вероятно, следует использовать специфичные для ОС API-интерфейсы шифрования) .

Answer 4

Что ж, поскольку я не видел ссылки на старый добрый регистр сдвига с линейной обратной связью, я публикую некоторый внутренний код на основе 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-битной арифметики. Если развернуть, то и быстрее.

Answer 5

Использование 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 

Answer 6

Почему бы не использовать внешнюю библиотеку ??? Это колесо было изобретено несколько сотен раз, так зачем это делать снова?

Если вам нужно реализовать RNG самостоятельно, вам нужно производить числа по требованию - то есть вы реализуете функцию rand () - или вам нужно создавать потоки случайных чисел - например, для тестирования памяти?

Вам нужен ГСЧ с криптостойкостью? Как долго это должно идти, прежде чем это повторяется? Вы должны абсолютно, положительно гарантировать равномерное распределение всех бит?

Вот простой взлом, который я использовал несколько лет назад. Я работал во встроенном режиме, и мне нужно было тестировать ОЗУ при включении питания, и я хотел действительно маленький, быстрый код и очень небольшое состояние, и я сделал это:

• Начните с произвольной 4-байтовой константы для вашего начального числа.
• Вычисляет 32-битный CRC из этих 4 байтов. Это дает вам следующие 4 байта
• Верните эти 4 байта в алгоритм CRC32, как если бы они были добавлены. CRC32 из этих 8 байтов является следующим значением.
• Повторяйте столько, сколько хотите.

Это занимает очень мало кода (хотя вам нужна таблица для функции crc32) и имеет очень небольшое состояние, но выходной поток с псевдослучайным циклом имеет очень большое время цикла перед повторением. Кроме того, он не требует SSE на процессоре. И, если у вас есть удобная функция CRC32, реализовать ее тривиально.

Answer 7

@ jjrv
То, что вы описываете, на самом деле является линейным конгенциальным генератором. Самые случайные биты являются старшими битами. Чтобы получить число от 0..N-1, вы умножаете полное значение на N (32 бита на 32 бита, что дает 64 бита) и используете старшие 32 бита.

Вы не должны просто использовать любое число для a (множитель для перехода от одного полного значения к следующему), числа, рекомендуемые в Кнуте (Таблица 1, раздел 3.3.4 TAOCP vol 2 1981), равны 1812433253, 1566083941, 69069 и 1664525.

Вы можете просто выбрать любой нечетный номер для b . (дополнение).

Answer 8

Линейный конгруэнтный (X = AX + C mod M) PRNG может быть хорошим для назначения на курс ассемблера, так как вашим студентам придется иметь дело с переносными битами для промежуточных результатов AX за 2 ^ 31 и вычислением модуля. Если вы студент, они довольно просты в использовании на ассемблере и могут быть тем, что имел в виду лектор.

Answer 9

также вы, вероятно, можете эмулировать сдвиговый регистр с элементами суммы XOR между отдельными битами, что даст вам псевдослучайную последовательность чисел.