6

I need your help and please give me some advice. From programming pearls I know that to generate random 30 bit integer we should write it like this: 

RAND_MAX*rand()+rand()

But what could I do for generating not 30, but 64 bit random integer instead? I think that is very inefficient method if I multiply two 30 bit integers and then multiply again 4 bit integer, so what kind of method should I use? I am using now popcount_1 different method for 64 bit one and I would like to test it on random integers(I am also measuring the time which each one takes to accomplish the task)

Improve this question
1
  • you can also shift and add them up.. Commented Nov 14, 2011 at 10:19

6 Answers 6

Reset to default
9

First, I have my doubts about the solution you post for a 30 bit integer. RAND_MAX itself could be a 31 bit value, and RAND_MAX * rand() + rand() is likely to overflow, producing undefined behavior (and in practice, negative values).

If you need a value larger than the guaranteed minimum of RAND_MAX, or for that matter, anything that isn't significantly smaller than RAND_MAX, the only solution will be to use successive calls to rand(), and combine the values, but you need to do this carefully, and validate the results. (Most implementations of rand() use linear congruent generators, which while adequate for some tasks, aren't particularly good in this case.) Anyway, something like: 

unsigned rand256() { static unsigned const limit = RAND_MAX - RAND_MAX % 256; unsigned result = rand(); while ( result >= limit ) { result = rand(); } return result % 256; } unsigned long long rand64bits() { unsigned long long results = 0ULL; for ( int count = 8; count > 0; -- count ) { results = 256U * results + rand256(); } return results; }

(The code in rand256 is designed to eliminate the otherwise unavoidable bias you get when mapping RAND_MAX values to 256 values.)

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

How do I control the precision in this code. Say I want to generate 61 bit random numbers instead of 64 bits. I think if i start the count from 7 instead of 8, I would get a 56 bit random number. Am I right?
@arunmoezhi If you can generate 64 random bits, you can generate 61 by generating 64, and throwing 3 away; e.g. by masking out the top three bits.
makes sense. Thanks. Your solution looks nice. But it would be more helpful if you can add some explanations to it. It took me some time to understand what you were doing.
3

This could be a solution, without multiplication:

r30 = RAND_MAX*rand()+rand() s30 = RAND_MAX*rand()+rand() t4 = rand() & 0xf res = (r30 << 34) + (s30 << 4) + t4
Improve this answer

4 Comments

This assumes that RAND_MAX is 1<<15. If you do assume this, why not: rand() + rand() << 15 + rand() << 30 + rand() << 45 + (rand() & 0xf) << 60 ? No multiplications at all.
Why not just do something like return ((unsigned long long)rand() << 48) | ((unsigned long long)rand() << 32) | ((unsigned long long)rand() << 16) | ((unsigned long long)rand() & 0xffff); ? Here you have no multiplications at all, just shifts.
Although, yes, you can generate 64 bits It would seem to me the resolution of the random number generated can't be larger than random number seed.
You say "without multiplication" yet there is multiplication there. And this won't be evenly distributed (e.g. there are two different ways that r30 can be equal to RAND_MAX). And of course the unstated assumption that RAND_MAX == 1<<15 is not true on many implementations.
3

If boost is an option, you could use boost random.

Improve this answer

5 Comments

are you sure that it can generate 64bit? Your link states otherweise: "mt19937 produces integers in the range [0, 2^32-1]."
Take a look at the various generators (boost.org/doc/libs/1_47_0/doc/html/boost_random/…), for instance at ranlux64_3.
@duedl0r If it does generate a good random value over the entire interval [0, 2^32-1], then it should be rather trivial to combine two calls to generate a good 64 bit random value. (For a sufficiently loose definition of "good", of course. The basic generator still needs a period of 2^64 or more, or there will be a lot of values which can never be generated.)
Statistically speaking, to generate all values you probably need a generator designed with a period of at least 2^64. Practically speaking, for most applications a simple solution with shifting / multiplications can work well enough.
With the default choice (mt19937), period really isn't an issue. 2^19937 is a whole lot more than the lifetime of the universe.
2

A random 64 bit int is essentially 64 random bits interpreted as an int.

Fill a byte array of length 8 with random bytes (see here for how) and interpret these as an int (see here for how).

Improve this answer

1 Comment

I have a suspicion that with most implementations of rand() you won't get a particularly uniform distribution by doing that.
1

A generic solution:

template <unsigned long long I> struct log2 { static const int result = 1 + log2<I/2>::result; }; template <> struct log2<1> { static const int result = 0; }; template <typename UINT> UINT genrand() { UINT result = 0; int bits = std::numeric_limits<UINT>::digits; int rand_bits = log2<RAND_MAX>::result; while (bits > 0) { int r = rand(); while (r >= (1<<rand_bits)) r = rand(); // Retry if too big. result <<= rand_bits; result += r; bits -= rand_bits; } return result; }

Use: unsigned long long R = genrand<unsigned long long>();.

The bits counter keeps track of the number of bits still needed.

Improve this answer

Comments

0

'Returns a pseudo-random integral value between ​0​ and RAND_MAX (0 and RAND_MAX included).' - http://en.cppreference.com/w/cpp/numeric/random/rand

So you should use RAND_MAX + 1 (it's like generating a number digit by digit and then converting it to base 10) instead of RAND_MAX. This way you can generate numbers with one, two, three etc. digits in base RAND_MAX + 1(possibly with leading zeroes) and convert them to base 10 and get arbitrarily large numbers.

Everything that you obtain larger than your desired MAX_VALUE can be discarded and you still get 1/(MAX_VALUE + 1) probability for obtaining each number.

Note, that this method might take a while, especially if your desired MAX_VALUE is a lot less than the maximum value that can be obtained before discarding the numbers that are not desired, as the expected number of steps to obtain a random number in [0, MAX_VALUE] with this algorithm is: (MAX_OBTAINABLE_VALUE + 1)/(MAX_VALUE + 1)

Improve this answer

Comments