Генератор псевдослучайных ситуаций на языке ассемблера

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

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

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

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

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

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

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

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

С 32-битной математикой вам не нужна операция MOD 2^32

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

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

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

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

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

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

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

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

• Начните с произвольной 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