汇编语言中的伪随机生成器

Question

汇编语言中的伪随机生成器

algorithmassemblyprng

6

我需要一个汇编程序的伪随机数生成算法，最好是一个简单的算法。但是，我不能使用外部库。

有哪些适合汇编语言的好的、简单的伪随机数生成算法？

- TCJ

你能解释一下这是干什么的吗？加密、游戏和随机算法确实有不同的要求和权衡。 - Bill Barksdale

9个回答

3

《计算机程序设计艺术》第二卷涵盖了大量关于伪随机数生成的信息。这些算法是用汇编语言演示的，因此您可以自行查看哪些是最简单的汇编语言算法。

如果您可以链接到外部库或对象文件，那将是最好的选择。然后，您可以链接到例如Mersenne Twister。

请注意，大多数伪随机数生成器不适用于加密，因此如果您需要安全的随机数生成，则需要超越基本算法（并且可能应该利用特定于操作系统的加密API）。

- Derek Park

3

用于测试的简单代码，请勿与加密一同使用

来自《软件测试计算机》，第138页

由于是32位数学运算，您不需要使用操作MOD 2^32

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

- ICW

2

好的 - 由于我没有看到关于老式线性反馈移位寄存器的参考，我发布了一些基于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));
}

将这段代码翻译成汇编语言很容易。只需用真正的SSE指令替换内置函数，并添加一个循环即可。

顺便说一下，这段代码生成的序列在4.61169E+18个数字后会重复。这比使用质数方法和32位算术得到的数字要多得多。如果展开，速度也会更快。

- Nils

1

使用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

- jason

1

为什么不使用外部库？这个轮子已经被发明了几百次了，所以为什么要再造一个呢？

如果你需要自己实现一个 RNG，你需要按需生成数字吗 - 比如实现一个 rand() 函数 - 还是需要生成随机数流 - 例如用于内存测试？

你需要一个加密强度的 RNG 吗？它需要多久才能重复？你是否必须绝对、绝对保证所有位的均匀分布？

这里有一个我几年前使用的简单技巧。我当时在嵌入式领域工作，需要在上电时测试 RAM，我想要非常小、快速的代码和很少的状态，并且我这样做：

从任意的 4 字节常量开始作为种子。
计算这 4 个字节的 32 位 CRC。那就给你下一组 4 个字节。
将这 4 个字节反馈到 CRC32 算法中，就好像它们已经被附加一样。这 8 个字节的 CRC32 就是下一个值。
循环操作直到满足需求。

这段代码很简单（虽然您需要一个crc32函数的表），而且状态非常少，但伪随机输出流在重复之前具有非常长的周期时间。此外，它不需要处理器上的SSE。假设您已经掌握了CRC32函数，实现起来就轻而易举。

- Die in Sente

1

@jjrv
你所描述的实际上是一个线性同余生成器。最随机的位是最高位。要从0..N-1中获取一个数字，您需要将完整值乘以N（32位乘以32位得到64位），并使用高32位。

您不应该只使用任何数字作为a（从一个完整值进展到下一个的乘数），Knuth（表1第3.3.4节TAOCP vol 2 1981）中推荐的数字是1812433253、1566083941、69069和1664525。

您可以选择任何奇数作为b。（加法）。

- paperhorse

LCG使用模运算符。这会保留低位，而不是高位。 - Derek Park

jjrv的生成器是x =（x * a + b）％（2 ** 32）。[模2 ** 32由硬件隐式完成]。然后他返回r = x％N。这只是范围缩减（如果他正在模拟骰子，则N可能为6）。 Knuth（3.6 vi）和维基百科（“进一步问题..”）提到最低位不太随机。 - paperhorse

0

你也可以使用在单独的位之间模拟移位寄存器的XOR和元素，从而给出伪随机数序列。

- dimarzionist

0

线性同余（X = AX+C mod M）PRNG可能是分配给汇编课程的好选择，因为您的学生将不得不处理中间AX结果超过2^31的进位位以及计算模数。如果您是学生，则实现这些相当简单，并且可能是讲师考虑的内容。

- Nigel Campbell

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jjrv · Accepted Answer

一个简单的方法是选择两个大的互质数a和b，然后将您的随机数乘以a并加上b。使用模运算符将低位作为您的随机数，并保留完整值用于下一次迭代。

这个算法被称为线性同余生成器。