Fast SSE Pseudo Random Number Generator

Introduction

This is a kind of save point for the knowledge acquired during test data generation. The generator, using the code is faster than standard C library random functions, works almost everywhere and does not depend on the other things.

Background

The code created during the test data generator implementation. Standard library was too slow and there was no desire to get a dependency to the other libraries. Another intention was to make code to be cross platform compliable. The code will work on any SSE/SIMD compatible CPUs. It was not tested on RISC or ARM-alike CPUs.

Using the Code

The code itself is not big or complex:

/* definition for RAND_MAX constant */
#include <stdlib.h>
/* random number storage */
static unsigned long long g_seed;

/**
 * Used to seed the generator
 * @param seed initializing "generator"
 */
void fast_srand(unsigned int seed)
{
    g_seed = seed;
}

/**
 * Compute a pseudo random integer. Output value in range [0, RAND_MAX]
 * @return pseudo random integer
 */
int fast_rand()
{
    g_seed = (214013*g_seed+2531011);
    return (g_seed>>32)&RAND_MAX;
}

The code is not fully mine. I found the main idea it on the Internet. I tried to compare the code with standard library functions (rand/random) and tried to read random data from /dev/urandom.

Performance and Randomness Tests

I was asked to compare performance and randomness of the generator from the article and the most available library generators.

Test Code

I wrote a test code:

/* definition for RAND_MAX constant */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define DEF_RANDOM_COUNT 10000
/* random number storage */
static unsigned long long g_seed;

/**
 * Used to seed the generator
 * @param seed initializing "generator"
 */
void fast_srand(unsigned int seed)
{
    g_seed = seed;
}

/**
 * Compute a pseudo random integer. Output value in range [0, RAND_MAX]
 * @return pseudo random integer
 */
int fast_rand()
{
    g_seed = (214013*g_seed+2531011);
    return (g_seed>>32)&RAND_MAX;
}
int cStrToInt(const char* sz)
{
    char* pEnd;
    if(sz==NULL)    {
        return 0;
    }
    return strtol(sz,&pEnd, 10);
}

int main(int argc, char* argv[])  {
    int i, n;
    int randomCount = DEF_RANDOM_COUNT;
    int randomType = 0;
    int dontPrint = 0;
    for(i=1; i<argc; i++)   {
        if(argv[i][0]=='-') {
            switch(argv[i][1])  {
                case 't':/* type */
                    if(i+1<argc)    {
                        randomType = cStrToInt(argv[++i]);
                    }
                    break;
                case 'c':
                    if(i+1<argc)    {
                        randomCount = cStrToInt(argv[++i]);
                    }
                    break;
                case 'p':
                    dontPrint = 1;
                    break;
            }
        }
        else    {
            randomCount = cStrToInt(argv[i]);
        }
    }
    if(randomCount<0)   {
        randomCount = DEF_RANDOM_COUNT;
    }
    switch(randomType)  {
        case 2:
            srandom(time(NULL));
            break;
        case 1:
            srand(time(NULL));
            break;
        default:
            fast_srand(time(NULL));
            break;
    }
    for(i=0; i<randomCount; i++)    {
        switch(randomType)  {
            case 2:
                n = random();
                break;
            case 1:
                n = rand();
                break;
            default:
                n = fast_rand();
                break;
        }
        if(dontPrint)   {
            continue;
        }
        printf("%d\n",fast_rand());
    }
}

I saved test code as rndGenTest.c and compiled the code with the command below:

gcc rndGenTest.c -o rndGenTest 

Performance

The performance comparison results on my Debian WSL were (first result for the code from article, second - srand/rand, third - srandom/random):

-bash $ time ./rndGenTest -p 10000000 ; time ./rndGenTest -p -t 1 10000000  ; time ./rndGenTest -p -t 2 10000000

real    0m0.034s
user    0m0.030s
sys     0m0.000s

real    0m0.071s
user    0m0.066s
sys     0m0.000s

real    0m0.057s
user    0m0.052s
sys     0m0.000s

Randomness

I also run on my Debian WSL a quick randomness test for all of these generators (first result for the code from article, second - srand/rand, third - srandom/random):

-bash $ ./rndGenTest 1000000 | sort -u | wc -l ; ./rndGenTest -t 1 1000000 | sort -u | wc -l ; ./rndGenTest -t 2 1000000
 | sort -u | wc -l
999766
999762
999762

Points of Interest

I was really surprised with the code speed comparison. The code from the article could be twice faster than the library code. I think I can find an explanation why this had happened, but...

Anyway, the generator from the article is quite good to generate big test data.

History

• 19^th February, 2024: Initial text
• 20^th February, 2024: Append with test section