Thread: Generate unsigned long long type random numbers

if you are using gcc, and have a new enough version, you might consider using one of the new pseudo random number generators provided by the C++ standard library. I realize this is the C forum, but mixing C and C++ code is pretty easy, especially with gcc.

If you want to pack the results of rand into the largest unsigned data type on your system, you could fairly easily automate the process with something like this:

Code:

#include <limits.h>
#include <time.h>
#include <stdlib.h>
#include <inttypes.h>
unsigned long long random( void )
{        
    typedef unsigned long long
        Unsigned;
    static Unsigned
        bits = 0,
        cycles = 0,
        setup = 1;
    const Unsigned
        constant = sizeof( Unsigned ) * CHAR_BIT;
    Unsigned
        result = 0;    
    if( setup )
    {
        setup = 0;
        srand( time( 0 ) );
        Unsigned
            max = RAND_MAX;
        while( max )
        {
            max >>= 1;
            ++bits;
        }
        cycles = constant / bits + ( constant % bits != 0 );
    }
    Unsigned
        count = cycles;    
    while( count-- )
    {
        result <<= bits;
        result ^= rand( );
    }    
    return result;
}
#include <stdio.h>
int main( void )
{
    for( ;; )
    {
        printf( "%llu\n", random( ) );
        getchar( );
    }
}

Originally Posted by rcgldr

I'm not sure what cycles is suppose to count in the example program, but most versions of rand() have a cycle count of 2^32, even though they only return 15 bits of the internal random number.

Complete non-sequitur. The variable in question has nothing to do with the periodicity of the rand function; it simply counts the number of loop cycles needed to fill the variable.

Here's a relatively simple, supposedly high-quality RNG (as far as linear congruential generators go) for 64-bit unsigned values.

Code:

// From: http://www.drdobbs.com/tools/fast-high-quality-parallel-random-number/229625477 (second page)
#include <stdio.h>
#include <time.h>
#include <inttypes.h>

#define rotl(r,n) (((r)<<(n)) | ((r)>>((8*sizeof(r))-(n))))

static uint64_t xx, yy, zz;  // obviously these and the two functions should be in a separate file

void seedRand64(uint32_t seed) {
    size_t n;
    xx =    914489ULL;
    yy =   8675416ULL;
    zz = 439754684ULL;
    for (n=((seed>>22)&0x3ff)+20; n>0; n--) { xx = rotl(xx,8) - rotl(xx,29); }
    for (n=((seed>>11)&0x7ff)+20; n>0; n--) { yy = rotl(yy,21) - yy;  yy = rotl(yy,20); }
    for (n=((seed    )&0x7ff)+20; n>0; n--) { zz = rotl(zz,42) - zz;  zz = rotl(zz,14) + zz; }
}

uint64_t rand64() {
    xx = rotl(xx,8) - rotl(xx,29);
    yy = rotl(yy,21) - yy;  yy = rotl(yy,20);
    zz = rotl(zz,42) - zz;  zz = zz + rotl(zz,14);
    return xx ^ yy ^ zz;
}

void printBinary(uint64_t n) {
    uint64_t m = 0x8000000000000000;
    for ( ; m; m >>= 1)
        putchar(n & m ? '1' : '0');
    putchar('\n');
}

int main(void) {
    uint64_t n;
    size_t i;

    seedRand64(time(0));  // would be nice to have a better seed

    for (i = 0; i < 20; i++) {
        n = rand64();
        printf("%" PRIu64 "\n", n);
//        printBinary(n);
    }

    return 0;
}

Actually this works fine for me:

Code:

#define RAND() rand()&32767

unsigned long long randGen(){
    unsigned long long n = 0;
    n+=RAND();
    n+=(((unsigned long long)RAND()) << 15);
    n+=(((unsigned long long)RAND()) << 30);
    n+=(((unsigned long long)RAND()) << 45);
    n+=((((unsigned long long) RAND())&15) << 60);
    return n;
}

Ofcourse I also set the seed at program start. and oogabooga, I also use your macro idea to ensure that rand() returns only 15 bits number.

Originally Posted by patishi

Actually this works fine for me

I don't see how that's any better than what I originally posted, in fact it's probably a little worse, but whatever. At any rate, you should put parentheses around your macro and you should use hex for the masks since decimal obscures the bit patterns.

I posted the 64-bit rng above for other people who are interested in a better alternative.

> what is the difference between using hex and normal decimals for bit wise oprtations? I always use base 10 numbers whenever i can. what do you mean by obscures the bit patterns?
Nothing, from a functional point of view (i.e. they both do the same). It's an issue of readability. It's far easier to see which bits you're masking off if you do

Code:

rand() & 0x7fff

If you're not familiar with hex yet, then perhaps your way seems easier to understand, but once you become familiar, it's much, much easier to do bit-wise operations using hex constants. Especially when you start getting bit patterns with a real mix of 0's and 1's. Also, the vast majority of all other programmers prefer hex (or octal) constants when working at the bit level.

> and is it really importatnt to put a parentheses around the macro? I usualy don't put parenthesis if there is no need to.
Yes, it's important. In fact, your code can behave improperly without them. Always put them around the entire macro, and around arguments when writing function-like macros. First, take a look at a C operator precedence chart. Notice that & is pretty low on the list. Now, take the following example, where you want to add 42 to some random number:

Code:

#define RAND()    rand()&32767
// now, when you do
int x = RAND() + 42;
// since + is higher precedence than & it is interpreted as
int x = rand() & (32767 + 42);  // equivalent to rand() & 32809, which is NOT what you want

However, the parentheses will ensure that the & is done first, masking off 15 bits first, then adding:

Code:

#define RAND15()    (rand() & 0x7fff)

int x = RAND15() + 42;
// is interpreted correctly as
int x = (rand() & 0x7fff) + 42;

Notice the better name, which suggests 15 bits, and the use of hex for the bit mask.

anduril has already given the answer, but since I've already typed this up:

Hex vs Decimal

Once you get used to it, it's easy to see bit patterns in hex. Each hex digit represents exactly 4 bits and it's easy to memorize the bit patterns for each. So if you see 0x7fff it's obvious it's 111 1111 1111 1111, whereas the bit pattern is entirely non-obvious as 32767. You should always represent bit patterns in hex.


Macros

Parenthesizing macros is important for ensuring proper order of operations since macros are not functions but simply textual replacement (at compile time), so precedence rules can mess things up. Consider this macro:

Code:

#include <stdio.h>

#define ADD_ONE(x) x + 1

void main(void) {
    printf("%d\n", ADD_ONE(5) * 2);
    return 0;
}

One would assume that it would add one first and then multiply by 2, so the answer should presumably be 12, that is, (5 + 1) * 2.

But since a macro just does textual replacement, it actually becomes 5 + 1 * 2, so the multiply is done first and the answer is 5 + 2 or 7.

A macro is not like a function call, which is why they're dangerous and must be properly parenthesized (and even then they're still dangerous).

Not only should you put parens around the whole macro, but even around the use of the parameter. Consider this macro and call:

Code:

#define TIMES_TWO(x) (x * 2)

printf("%d\n", TIMES_TWO(2 + 3));

It looks like the answer whould be 5 * 2 or 10, but instead it will become 2 + 3 * 2 which is 2 + 6 or 8.

So it should be written as

Code:

#define TIMES_TWO(x) ((x) * 2)

which with the above use would become ((2 + 3) * 2) which gives the expected answer.

And if you need a multi-statement macro to work properly as a block, the usual technique is to surround it with a do/while that doesn't loop:

Code:

#define XXX(x) do { /*multiple statements*/ } while(0)

For Zobrist hashing, I have always used Mersenne Twister as the PRNG to initialize the Zobrist key table. It's easily available on line and it's not difficult to use.

There is no guarantee of quality for the built-in rand() function. It is actually very important that the Zobrist keys be as random as possible.

However, there's no need to use different random values each time -- you can pre-generate the Zobrist key table and then include it into your program as a const array.

I looked at the Mersenne algorithm, and it is very difficult for me to understand what's going on there..and i don't like to use algorithms / code parts that i don't understand (unless i really really have no choice) ,although some are consider very very good. so for now i preffered the inferior rand() function in the implementation i posted above. Maybe in time i will learn it, but right now my mind is focused on other subjects..like getting better in C

I checked my randGen() method by printing the numbers and they look pretty random to me