我想在 xv6 中实现伪随机数生成器。我正在尝试实现线性同余生成器算法,但我不知道如何播种它。这是我的一段代码。我知道这段代码行不通,因为 X 并没有在全球范围内发生变化。我不知道该怎么做。
static int X = 1;
int random_g(int M)
{
int a = 1103515245, c = 12345;
X = (a * X + c) % M;
return X;
}
不正确的代码。
不要使用随机状态变量%
onX
来更新状态。用于%
形成返回值。
使用无符号类型来避免有符号整数溢出 (UB) - 也许unsigned, unsigned long, unsigned long long
. 更宽提供更长的序列。
为了匹配a = 1103515245, c = 12345,我们想要m = 31
.
static unsigned long X = 1;
int random_g(int M) {
const unsigned long a = 1103515245, c = 12345;
#define m 0x80000000
int r = (X % M) + 1; // [1 ... M]
X = (a * X + c) % m;
return r;
}
消除典型M
偏差所需的附加代码。许多SO都在上面发帖。
我不知道这对你有多大帮助,但如果你有英特尔 Ivy Bridge 或更高版本的处理器,你可以尝试使用该RDRAND
指令。这些方面的东西:
static int X;
int
random_g (int M)
{
asm volatile("byte $0x48; byte $0x0F; byte $0xC7; byte $0xF0"); // RDRAND AX
asm volatile("mov %%ax, %0": "=r"(X)); // X = rdrand_val
int a = 1103515245, c = 12345;
X = (a * X + c) % M;
return X;
}
我没有测试上面的代码,因为我现在不能构建 xv6,但它应该给你一个关于如何工作的提示;利用你的处理器的 rng。
在下面的代码中,random_g
是一个自播种随机数生成器,它返回 和 之间的1
值M
。该main
函数针对 8 的特定情况测试函数M
。
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <time.h>
int random_g( int M )
{
static uint32_t X = 1;
static bool ready = false;
if ( !ready )
{
X = (uint32_t)time(NULL);
ready = true;
}
static const uint32_t a = 1103515245;
static const uint32_t c = 12345;
X = (a * X + c);
uint64_t temp = (uint64_t)X * (uint64_t)M;
temp >>= 32;
temp++;
return (int)temp;
}
int main(void)
{
int i, r;
int M = 8;
int *histogram = calloc( M+1, sizeof(int) );
for ( i = 0; i < 1000000; i++ )
{
r = random_g( M );
if ( i < 10 )
printf( "%d\n", r );
if ( r < 1 || r > M )
{
printf( "bad number: %d\n", r );
break;
}
histogram[r]++;
}
printf( "\n" );
for ( i = 1; i <= M; i++ )
printf( "%d %6d\n", i, histogram[i] );
free( histogram );
}