C-Function to generate random 53-Bit numbers

user_5790979 0
Viewed 83

I did wrote a function, with that I want to generate unique random numbers, which have not more than 53 Bit. I would be happy, if you do a critical look at the source:

#include <stdlib.h>
#include <unistd.h>
#include <locale.h>
#include <sys/time.h>
#include <time.h>
#include <sys/types.h>
#include <stdio.h>
#include <math.h>
#include <stdint.h>

uint64_t cp_random_53bit(void)
{
    // max 53 Bit:
    // 0x0020000000000000LU == 9007199254740992
    // CBIT31          0x80000000U
    // CBIT52          0x0010000000000000LU
    uint64_t                result  = 0;
    struct drand48_data     dseed   = {0};
    long int                sr_init = 0;
    long int                lg1, lg2;
    sr_init = time(0) + clock();
    srand48_r(sr_init, &dseed);
    lrand48_r(&dseed, &lg1);    // returns 32 Bit value
    lrand48_r(&dseed, &lg2);
    if( sizeof(long int) == 4)
    {
        result = ((uint64_t)lg1 << 20) + lg2;
    }
    else if( sizeof(long int) == 8)
    {
        result = (lg1 << 20) + lg2;
    }
    return result;
}

// compile: gcc -g3 -o bit53id bit53id.c

int main(int argc, char** argv, char** env)
{
    uint64_t    val53;
    int         idx;
    setlocale(LC_ALL, "de_DE.UTF-8");
    tzset();
    // show some values
    for(idx=0; idx < 25; idx++)
    {
        val53   = cp_random_53bit();
        printf("cp_random_53bit: %lu (%lX)\n", val53, val53);
    }
    // check for values greater than 0x0020000000000000LU -1LU
    for(idx = 0; idx < 10000000; idx++)
    {
        val53   = cp_random_53bit();
        if( val53 > 9007199254740991 )
            printf("cp_random_53bit returns %lu\n", val53);
    }
}

In my tests it was successfull many millions of numbers. I do not know how great the danger of a collision is.

I made tests with drand48_r too, to get double values. They are between 0.0 and 1.0 and I found no good way to convert them to 53 bit integers.

random c
1 Answers

There are multiple problems in your code:

  • you should only initialize the 48-bit pseudo-random number generator once at program startup, not every time you request a new number.

  • as commented by chux, lrand48_r only generates 31 bits, so the expressions do not produce 53 bits of random contents: you only get 51 bits (20 + 31), and sometimes an extra bit (approximately one chance in 1 million), when the addition produces a larger result. The expression must be changed to generate exactly 53 uniformly distributed bits.

Here is a modified version:

#include <locale.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>

static struct drand48_data dseed;

void cp_random_53bit_init(void) {
    srand48_r(time(NULL) + clock(), &dseed);
}

uint64_t cp_random_53bit(void) {
    // max 53 Bit:
    long int lg1, lg2;
    lrand48_r(&dseed, &lg1);  // lg1 has 31 random bits
    lrand48_r(&dseed, &lg2);  // lg2 has 31 random bits
    // combine the bits to obtain 53 random bits
    return ((uint64_t)lg1 << (53 - 31)) ^ lg2;
}

// compile: gcc -g3 -o bit53id bit53id.c

int main(int argc, char **argv, char **env) {
    uint64_t    val53;
    int         idx;

    setlocale(LC_ALL, "de_DE.UTF-8");
    tzset();
    cp_random_53bit_init();

    // show some values
    for (idx = 0; idx < 25; idx++) {
        val53 = cp_random_53bit();
        printf("cp_random_53bit: %llu (%llX)\n",
               (unsigned long long)val53, (unsigned long long)val53);
    }
    // check for values greater than 0x0020000000000000LU -1LU
    for (idx = 0; idx < 10000000; idx++) {
        val53 = cp_random_53bit();
        if (val53 > 9007199254740991)
            printf("cp_random_53bit returns %llu\n", (unsigned long long)val53);
    }
    return 0;
}
user_45932670
Related