题
我需要一个用于课程中分配的汇编程序的伪随机数生成器算法,并且我更喜欢一个简单的算法。但是,我无法使用外部库。
什么是好的、简单的汇编伪随机数生成器算法?
解决方案
简单的方法是选择两个大的相对素数 a 和 b,然后继续将随机数乘以 a 并加上 b。使用模运算符将低位保留为随机数,并保留下一次迭代的完整值。
该算法被称为 线性同余发生器.
其他提示
用于测试的简单代码,请勿与 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));
}
将此代码翻译为汇编程序很简单。只需用真正的 SSE 指令替换内在函数并在其周围添加一个循环即可。
顺便说一句 - 此代码生成的序列在 4.61169E+18 个数字之后重复。这比通过 prime 方法和 32 位算术得到的要多得多。如果展开的话速度也会更快。
@jjrv
你所描述的实际上是一个线性同余发生器。最随机的位是最高位。要获得 0..N-1 之间的数字,请将完整值乘以 N(32 位乘以 32 位,得出 64 位)并使用高 32 位。
你不应该只使用任何数字 A (从一个完整值进展到下一个完整值的乘数),Knuth(表 1 第 3.3.4 TAOCP vol 2 1981)中推荐的数字是 1812433253、1566083941、69069 和 1664525。
您可以选择任何奇数 乙. 。(补充)。
为什么不使用外部库???那个轮子已经被发明了几百次了,为什么还要再发明一次呢?
如果您需要自己实现 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
您也可以使用不同位之间的异或和元素来模拟移位寄存器,这将为您提供伪随机数字序列。
线性同余 (X = AX+C mod M) PRNG 可能是分配给汇编程序课程的一个不错的选择,因为您的学生将必须处理超过 2^31 的中间 AX 结果的进位并计算模数。如果您是学生,那么它们在汇编器中实现起来相当简单,并且可能就是讲师的想法。