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

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

Если бы можно связаться с внешней библиотекой или объектным файлом, тем не менее, который был бы лучшим выбором. Затем Вы могли связаться с, например, вихрь Мерсенна.

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

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

От Тестирования Программного обеспечения, страницы 138

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

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

Хорошо - Так как я не видел ссылки на старый добрый Линейный Сдвиговый регистр Обратной связи, я отправляю некоторый SSE внутренний основанный C-код. Только для полноты. Я записал что вещь несколько месяцев назад для увеличения резкости моих навыков 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));
}

Перевод этого кода к ассемблеру тривиален. Просто замените intrinsics реальными инструкциями SSE и добавьте цикл вокруг этого.

Btw - последовательность этот код генерирует повторения после 4.61169E+18 числа. Это намного больше, чем Вы доберетесь с помощью главного метода и арифметики на 32 бита. Если развернуто это быстрее также.

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

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

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

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

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

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

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

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

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

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

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