Generate unsigned long long type random numbers

[patishi]

How can i produce such numbers?
I need to use them for generating keys for storing entries in a Hash table. I will be using Zobrist keys scheme in my gomoku Game so i will be needing 225 different unsigned long long random numbers ,one for each square on the board.

I don't think it is necessary for the numbers to be different at each program run, but the important thing is for them to be different from one another.

As i am relatively new to C, i will prefer the simplest approach possible.

[oogabooga]

If they just need to be different from each other why not use the numbers from 0 to 224?
If you need somewhat more random numbers (but not very random, really), you could try this. I'm assuming that by "unsigned long long" you mean an unsigned 64-bit value.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <inttypes.h>

#define RAND() (rand() & 0x7fff)  /* ensure only 15-bits */

typedef uint64_t u64;

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

    srand(time(0));

    for (i = 0; i < 100; i++) {
        n = ((u64)RAND()<<48) ^ ((u64)RAND()<<35) ^ ((u64)RAND()<<22) ^
            ((u64)RAND()<< 9) ^ ((u64)RAND()>> 4);


        printf("%"PRId64"\n", n);
    }
    return 0;
}

[anduril462]

I'm guessing that 225 means you have a 15x15 board. After reading up on Zorbist hashing and Gomoku, I'm guessing you have 225 spaces with 2 different possibilities for each piece (black or white). That means you have 2 * 225 = 450 spots to fill, each of which should have a unique, random bit string. Minor difference, but noteworthy.

Also, I'm guessing that your choice of unsigned long long means you want 64-bit random numbers. Now, the built-in rand() function in C returns type int. If you have a modern, 64-bit system, that probably means 64-bit ints (and unsigned ints), so you can just use unsigned int instead of unsigned long long. That means you can simply call rand() and use that value. If not, you need to know whether you have 32-bit ints or 16-bit (e.g. embedded system or ancient PC). Then, you use the bit-shift operator << and bitwise OR operator | to combine several calls to rand() until you have 64 bits. You can check how big the types are on your system by printing sizeof(unsigned int), sizeof(unsigned long) and sizeof(unsigned long long). Depending on how portable you need this to be, you should look into the fixed-width types (#include <stding.h>, and use uint64_t), and possibly write your own 64-bit PRNG (actually quite easy).

[anduril462]

If they just need to be different from each other why not use the numbers from 0 to 224?

I couldn't figure that out either, until I read up on the Zorbist hashing algo. He does need the extra bits, they're crucial for minimizing collisions when hashing different board states.

[oogabooga]

the built-in rand() function in C returns type int. If you have a modern, 64-bit system, that probably means 64-bit ints (and unsigned ints), so you can just use unsigned int instead of unsigned long long. That means you can simply call rand() and use that value. If not, you need to know whether you have 32-bit ints or 16-bit (e.g. embedded system or ancient PC).

gcc on my 32-bit computer only returns a 15-bit random int.

You can print RAND_MAX to see what the max is.

If rand returns a 64-bit signed int, it's presumably always positive so will only have 63 random bits.

I was assuming the lowest common denominator of rand's, which only returns 15 random bits. That's why I did the & 0x7fff thing to "ensure" 15 bits.

[patishi]

@anduril462 you are correct, I forgot to mention that the table will be a two dimentional array [2][225], e.g 225 squares for each player.
The reason i wanted to use long long type is because i want to make sure that i will be getting 64 bit values. It might be that i will try to run this code on different systems..that's why i don't want to be dependent on my system solely.

[anduril462]

gcc on my 32-bit computer only returns a 15-bit random int.

You can print RAND_MAX to see what the max is.

If rand returns a 64-bit signed int, it's presumably always positive so will only have 63 random bits.

I was assuming the lowest common denominator of rand's, which only returns 15 random bits. That's why I did the & 0x7fff thing to "ensure" 15 bits.

Duh, duh and duh. Must have had my head up my you-know-what there.

The reason i wanted to use long long type is because i want to make sure that i will be getting 64 bit values. It might be that i will try to run this code on different systems..that's why i don't want to be dependent on my system solely.

Better to use a fixed-width type like uint64_t then; unsigned long long may not be 64-bits bits on some systems.

Also, ignore my comments in my first post about what rand() returns, I was just wrong. The function oogabooga provided will probably suffice for your needs (I think it's totally portable, but haven't given it lots of thought). If not, or if you want to write your own, Google will turn up several alternatives. The Mersenne Twister provides good randomness and has a 64-bit variant. If you're careful and use only fixed-width types, your code will be very portable.

[patishi]

Thx for the uint64_t tip! I am not familiar with all the c types .. I am coming from java where you only have byte,short,int and long. I will implement your suggestion

[patishi]

Although oogabooga's solution is probably much better... would it be wrong to do something simpler like this? :

unsigned long long random() 
{ 
   return ((unsigned long)rand() << 32) | (unsigned long)rand(); 
} 

Simply concatenating two 32 bit integers together?

[anduril462]

Well, assuming you get 32-bits of randomness from rand, then no. But you wont, certainly not if you want to be portable. rand() gives a value in the range of [0, RAND_MAX]. And RAND_MAX is only guaranteed to be at least 32767, i.e. rand() only guarantees you 15 bits of randomness. Thus, oogabooga's method is better. And the reason he uses ^ (XOR) instead of | is that, if due to the shifting, you have bits that overlap, using | will actually reduce randomness, since it will turn extra bits on where overlap occurs. That is, you'll end up an uneven distribution of 1's where there is overlap. XOR will "flip" the bits, so you wont end up with a more even (i.e. more random) distribution.

[oogabooga]

Although oogabooga's solution is probably much better... would it be wrong to do something simpler like this? :

unsigned long long random() 
{ 
   return ((unsigned long)rand() << 32) | (unsigned long)rand(); 
} 

Simply concatenating two 32 bit integers together?

You're assuming rand will return 32 random bits, which is not likely.

Try printing RAND_MAX. What is its value?

Also, you said you wanted it to be portable, in which case you must assume rand() will only return 15 random bits.

Or you could implement an rng, which is ultimately the best solution.

[patishi]

Thank you very much for the explanation! This is a great forum!!

EDIT: yes I printed RAND_MAX and it is indeed 32767. only 15 bits

[oogabooga]

To be absolutely certain that all the numbers are unique, you could set the highest (or whatever) 9 bits to a sequence number from 0 to 450. You could do that like so:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <inttypes.h>

#define RAND() (rand() & 0x7fff)  /* ensure only 15-bits */

typedef uint64_t u64;

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

    srand(time(0));

    for (i = 0; i < 450; i++) {
        n = ((u64)i << 54) ^ ((u64)RAND() << 39) ^ ((u64)RAND() << 26)
          ^ ((u64)RAND() << 13) ^ (u64)RAND();
        printf("%"PRId64"\n", n);
    }
    return 0;
}

As for the xor instead of or, I purposely overlapped the last couple of bits because they are the least random, so I figured that xor'ing them with the top two from the next number would help, but overall it's pretty pointless because the resulting numbers will have pretty poor randomness anyway.

[vart]

Since using several rand() calls to generate one number shortens the loop length, I would try ideas from Prelude to rewrite my own random function with native type of int64

Eternally Confuzzled - Random Numbers Tutorial

[oogabooga]

Since using several rand() calls to generate one number shortens the loop length, I would try ideas from Prelude to rewrite my own random function with native type of int64

Eternally Confuzzled - Random Numbers Tutorial

It's been said a few times in this thread that the technique given is not very random. The OP has said that he doesn't need high-quality random numbers. However, the "loop length" is not an issue here since rand is called exactly 1800 times, well below the cycle length.