algorithm - 随机函数算法 - 随机数定义




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

@jjrv
你所描述的实际上是一个线性的生成器。 最随机的比特是最高的比特。 要从0..N-1中得到一个数字,你需要将整个值乘以N(32位,32位,给出64位),并使用高32位。

在Knuth中推荐的数字(表1第3.3.4节,TAOCP第2卷,1981年)是1812433253,1566083941,69069和1664525,你不应该只使用任何数字作为(从一个完整值到下一个完整值的乘数)。

你可以选择任何奇数的b 。 (增加)。

我需要一个伪随机数生成器算法为一个课程分配的汇编程序,我宁愿一个简单的算法。 但是,我不能使用外部库。

什么是一个好的,简单的伪随机数发生器算法的汇编?


“计算机程序设计艺术”第2卷有很多关于伪随机数生成的信息。 这些算法在汇编程序中演示,所以您可以自己查看哪些汇编程序中最简单。

如果您可以链接到外部库或目标文件,那么这将是您最好的选择。 那么你可以链接到,例如梅森扭转者

请注意,大多数伪随机数发生器对于加密来说是不安全的,所以如果你需要安全的随机数生成,你需要超越基本算法(也许应该使用特定于操作系统的加密API)。


简单的就是选择两个大的素数a和b,然后把你的随机数乘以a并加上b。 使用模运算符将低位保留为随机数,并保留下一次迭代的完整值。

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


线性同余(X = AX + C mod M)对于汇编程序,PRNG可能是一个很好的选择,因为学生必须处理超过2 ^ 31的中间AX结果的进位位并计算模数。 如果你是学生,他们相当直接地用汇编来实现,可能是讲师的想法。


为什么不使用外部库? 那个轮子已经发明了几百次了,为什么又这样呢?

如果你需要自己实现一个RNG,你需要按需产生数字 - 也就是说你在执行一个rand()函数吗?还是需要产生随机数字流 - 例如内存测试?

你需要一个加密强度的RNG吗? 重复之前需要多长时间? 你必须绝对,积极地保证所有位的均匀分布?

这是几年前我用过的简单黑客技术。 我在嵌入式工作,我需要在上电时测试RAM,我想要的是非常小的,快速的代码和很少的状态,我这样做:

  • 为你的种子开始一个任意的4字节的常量。
  • 计算这4个字节的32位CRC。 这给你接下来的4个字节
  • 将这4个字节反馈回CRC32算法,就好像它们已经被追加了一样。 这8个字节的CRC32是下一个值。
  • 重复只要你想要的。

这只需要很少的代码(尽管你需要一个crc32函数的表),并且状态非常少,但是psuedorandom输出流在重复之前有很长的循环时间。 而且,它不需要处理器上的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 




prng