0

I want to implement the pseudo-random number generator in xv6. I am trying to implement Linear congruential generator algorithm, but I am not getting how to seed it. Here is the piece of my code. I know this code won't work because X is not changing globally. I am not getting how doing that.

static int X = 1;
int random_g(int M)
{
   int a = 1103515245, c = 12345;
   X = (a * X + c) % M; 
   return X;
}
lilott8
  • 1,116
  • 2
  • 17
  • 41
Anmol Yousaf
  • 65
  • 1
  • 13
  • 1
    so have you actually tried to use that code? Because I'm pretty sure what you are saying about `X` is not true – UnholySheep Oct 22 '14 at 20:39
  • Yeah. Actually I want that if I call it with same M, it gives me random number between 1 to M. But let's say I am calling it with 8. It gives me 6 each time I call it. – Anmol Yousaf Oct 22 '14 at 20:42

3 Answers3

1

Incorrect code.

Do not use % on X, the random state variable, to update the state. Use % to form the return value.

Use unsigned types to avoid signed integer overflow (UB) - Perhaps unsigned, unsigned long, unsigned long long. Wider affords a longer sequence.

To match a = 1103515245, c = 12345, we want 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;
}

Additional code needed to remove the typical M bias. Many SO post on that.

  1. Ref: Why 1103515245 is used in rand? and http://wiki.osdev.org/Random_Number_Generator
chux - Reinstate Monica
  • 143,097
  • 13
  • 135
  • 256
0

I don't know how much that helps you, but if you have an Intel Ivy Bridge or later generation processor, you could try to use the RDRAND instruction. Something along these lines:

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

I haven't tested the above code, as I can't build xv6 right now, but it should give you a hint as to how you can work; utilising your processor's rng.

NlightNFotis
  • 9,559
  • 5
  • 43
  • 66
  • I would also like to note that the specific `asm volatile` syntax is for gcc. I don't know if it works with llvm. – NlightNFotis Oct 22 '14 at 20:47
  • But not an answer to the question of correcting implementing an PRNG based on (_well studied_) linear congruential generator algorithm using well-known parameters. – mctylr Oct 22 '14 at 22:55
0

In the following code, random_g is a self-seeding random number generator that returns values between 1 and M. The main function tests the function for the specific case where M is 8.

#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 );
}
user3386109
  • 34,287
  • 7
  • 49
  • 68
  • Standard C libraries are not available in the OS. So I can't include them. – Anmol Yousaf Oct 22 '14 at 21:45
  • The libraries are mostly for `main` since it uses `calloc`, `free` and `printf`. In `random_g`, you can get rid of the stuff by declaring `ready` as an `int`, and replacing `false` and `true` with 0 and 1 respectively. Finally, you can get rid of by typedef'ing your own unsigned-32-bit and unsigned-64-bit types. – user3386109 Oct 22 '14 at 21:51
  • @AnmolYousaf As for , if you can't use the `time` function, then you'll have to find some other random source in your system. Typically, the hardware has a free running counter somewhere that can be used for this purpose. – user3386109 Oct 22 '14 at 21:54
  • Yeah. I guess that would be great if I could find some timer in xv6. I have to work on it. Thanks by the way!! – Anmol Yousaf Oct 22 '14 at 21:58