11

I'm implementing universal hashing and using the following universal hash function :

h(k)=((A*k)mod 2^64) rsh 64-r

where A is a random number between

2^61 and 2^62.

The rand() function in C++ has return type integer and it can't generate that big numbers. So how can i generate random numbers in this range? (numbers should be very random i.e. every number should have equal probability to be selected)

Note: 

long long int random=rand();

doesn't work as the number returned by rand is int.

Shafik Yaghmour
  • 154,301
  • 39
  • 440
  • 740
Ahmed
  • 2,176
  • 5
  • 26
  • 40
  • 6
    Read about [the new PRNG support that was introduced in C++11](http://en.cppreference.com/w/cpp/numeric/random). – Some programmer dude Jan 13 '14 at 16:17
  • 2
    If you had a good PRNG at hand (and not `std::rand()`) you could just generate N bits out of it and concatenate them. Or generate M bits at once, and concatenate them. Since if its good, each bit has the same probability, as such concatenating them is safe. – PlasmaHH Jan 13 '14 at 16:26

2 Answers2

22

In C++11 you can use the random header and std::uniform_int_distribution along with a 64-bit instance of std::mersenne_twister_engine this should do what you want (see it live):

#include <iostream>
#include <random>
#include <cmath>

int main()
{
    std::random_device rd;

    std::mt19937_64 e2(rd());

    std::uniform_int_distribution<long long int> dist(std::llround(std::pow(2,61)), std::llround(std::pow(2,62)));

    std::cout << std::llround(std::pow(2,61)) << std::endl; 
    std::cout << std::llround(std::pow(2,62)) << std::endl; 

    for (int n = 0; n < 10; ++n) {
            std::cout << dist(e2)<< ", " ;
    }
    std::cout << std::endl ;
}

If C++11 is not an option then it seems there is source code available for several 64-bit Mersenne Twister implementations.

Shafik Yaghmour
  • 154,301
  • 39
  • 440
  • 740
8
((long long)rand() << 32) | rand()

EDIT: that's assuming that rand() produces 32 random bits, which it might not.

Seva Alekseyev
  • 59,826
  • 25
  • 160
  • 281
  • 3
    Note that this won't actually produce very good results. (because std::rand is terrible) +1 – Billy ONeal Jan 13 '14 at 16:28
  • 1
    Note: On a crap-tastic MS VC++ environment where RAND_MAX is a legacy pitiful 0x7FFF, this won't work. – WhozCraig Jan 13 '14 at 16:28
  • @Whoz: It is just as crap-tastic on every other implementation I've seen. `std::rand` is 99.9% of the time powered by a linear congruential generator of some description -- the range that it returns is a minor problem in comparison. – Billy ONeal Jan 13 '14 at 16:37
  • 1
    @BillyONeal If limited by 0x7FFF, its a *huge* problem in this case, as the numbers generated would not be in the desired range *at all*, much less uniformly distributed in said-range (2^61..2^62). – WhozCraig Jan 13 '14 at 16:40
  • @Whoz: If `rand` is an LCG (which again, it is on every implementation I've ever seen), then it is not uniformly distributed within the range defined by `RAND_MAX`. And so the result here will not be uniformly distributed anyway. – Billy ONeal Jan 13 '14 at 16:43
  • 1
    @BillyONeal oh I never claimed it was the *only* thing holding this answer back from being workable. I'd implement this as Shafik has done without doubt. My point was this is *dependent* on top-range of RAND_MAX, which isn't always where people think it is. But I certainly agree with you as well; even if the top-end were 0x7FFFFFFFF (as it is on most sane 32-bit `int` platforms save for MS) this still suffers from the uniformity issue with a LCG that you describe. – WhozCraig Jan 13 '14 at 16:47
  • @Whoz: (In particular LCGs have a period equaling their output size. Thus, given what the upper 32 bits are in this example, the lower 32 bits will always be the same; there are only 32 bits worth of possible outputs here, even if `RAND_MAX` is `std::numeric_limits::max()`.) – Billy ONeal Jan 13 '14 at 16:47
  • `rand()` doesn't produce 32 bits on any platform (since it produces a non-negative value for a signed type). It produces 31 or 15 bits on popular implementations. So even if `rand()` produces 31 bits, the values produces by this answer will always have bits 15 and 31 set to 0. – interjay Jun 05 '16 at 12:04