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

コードが正しくありません。

ランダムな状態変数である%onを使用して状態を更新しないでください。戻り値を形成するために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典型的なバイアスを取り除くために必要な追加のコード。多くのSOがそれに投稿しています。

  1. 参照: 1103515245 がランドで使用されるのはなぜですか? およびhttp://wiki.osdev.org/Random_Number_Generator
于 2014-10-22T21:08:48.500 に答える
0

それがどれほど役立つかはわかりませんが、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 を利用します。

于 2014-10-22T20:46:32.380 に答える
0

次のコードでは、 はとrandom_gの間の値を返す自己シード乱数ジェネレーターです。この関数は、が 8である特定のケースについて関数をテストします。1MmainM

#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 に答える