基于LCG的伪随机数发生器

Question

我想用xv6实现伪随机数生成器。我正在尝试实现Linear congruential generator算法，但我不知道如何播种它。这是我的代码片段。我知道这段代码不会工作，因为X不是全局改变的。我不明白是怎么做的。

static int X = 1;
int random_g(int M)
{
   int a = 1103515245, c = 12345;
   X = (a * X + c) % M; 
   return X;
}

Answer 1

代码不正确。

不要在随机状态变量X上使用%更新状态。使用%形成返回值。

使用无符号类型以避免有符号整数溢出(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偏差。很多人都在这上面发帖。

1. 参考：Why 1103515245 is used in rand?和http://wiki.osdev.org/Random_Number_Generator

Answer 2

我不知道这对您有多大帮助，但如果您使用的是Intel 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。

Answer 3

在下面的代码中，random_g是一个自播种随机数生成器，它返回介于1和M之间的值。当M为8时，main函数针对特定情况测试函数。

#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 );
}