0

我想在 xv6 中实现伪随机数生成器。我正在尝试实现线性同余生成器算法,但我不知道如何播种它。这是我的一段代码。我知道这段代码行不通,因为 X 并没有在全球范围内发生变化。我不知道该怎么做。

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

3 回答 3

1

不正确的代码。

不要使用随机状态变量%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都在上面发帖。

  1. Ref:为什么 1103515245 用在 rand 中?http://wiki.osdev.org/Random_Number_Generator
于 2014-10-22T21:08:48.500 回答
0

我不知道这对你有多大帮助,但如果你有英特尔 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。

于 2014-10-22T20:46:32.380 回答
0

在下面的代码中,random_g是一个自播种随机数生成器,它返回 和 之间的1M。该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 );
}
于 2014-10-22T21:18:28.303 回答