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

StackOverflow https://stackoverflow.com/questions/90184

  •  01-07-2019
  •  | 
  •  

Вопрос

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

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

Это было полезно?

Решение

Самый простой — просто выбрать два больших относительных простых числа 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 и вычислением модуля.Если вы студент, их довольно просто реализовать на ассемблере, и, возможно, это именно то, что имел в виду преподаватель.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top