PDA

View Full Version : How feasible is this way of generating random numbers ?



manasij7479
10-19-2011, 07:08 AM
I know they are covered in the standard library, but couldn't resist to experiment.
This could be slow due to opening the file, but still have a look....and try to benchmark if it is not obviously flawed.


int random(int low,int up)
{
ifstream in;
in.open("/dev/urandom");
int count = 5;
long num;
while(count--)
num+=in.get()*(count+1);
in.close();
return (num%(up+1-low))+low;
}
PS: Taking 5 readings because, somehow in my machine, the first one is mostly coming 0;

Elkvis
10-19-2011, 07:19 AM
I use /dev/random for most of my linux random number needs, and it seems to work pretty well, although you should know that /dev/random may block while waiting for the entropy pool to fill. /dev/urandom will never block, so it may be a better choice.

EDIT: /dev/urandom will not generate strong random numbers if the entropy pool is empty. if a cryptographically secure random number generator (csrng) is what you're after, /dev/random is the way to go.

manasij7479
10-19-2011, 07:21 AM
That is why I put urandom here.(..making a small game.. and waiting could be bad)
Is there any difference in performance with the standard rand ?

MK27
10-19-2011, 07:49 AM
This could be slow due to opening the file

No, because it is not a real file. There is no hard disk IO bottleneck.

manasij7479
10-19-2011, 07:53 AM
EDIT: /dev/urandom will not generate strong random numbers if the entropy pool is empty. if a cryptographically secure random number generator (csrng) is what you're after, /dev/random is the way to go.
No, In my game, it really won't matter if the next 3 'monsters' in a row have a similar health, but it would, if each takes 4 to 5 seconds to appear.. or worse, freezing !


No, because it is not a real file. There is no hard disk IO bottleneck.
Excellent... any other bottlenecks to be aware about, when using in a game loop ?

MK27
10-19-2011, 07:58 AM
That is why I put urandom here.(..making a small game.. and waiting could be bad)
Is there any difference in performance with the standard rand ?

I'd guess that urandom is faster when the entropy pool is available, because it does not have to do anything, whereas rand() involves some calculation, doesn't it? If the entropy pool is exhausted, urandom uses a pseudo-generator, which I presume would make it much like rand().

Simple thing to benchmark tho.

Also: you could maintain your own sort of entropy pool by reading a stack of numbers at once and then popping them off when needed.

manasij7479
10-19-2011, 09:08 AM
Unfortunately, even after removing most of the bells and whistles from the function,


int random()
{
ifstream in;
in.open("/dev/urandom");
return in.get();
}

... it turns out to be more than 4000 times slower than rand() ! .. maybe some optimization is at play here ?


#include<iostream>
#include<fstream>
#include<cstdlib>
#include "../bench/bench.h"
using namespace std;
namespace mm
{
int random()
{
ifstream in;
in.open("/dev/urandom");
return in.get();
}


}
void a()
{
srand(time(NULL));
long x= 1000;
while(x--)
rand();
}
void b()
{
long x= 1000;
while(x--)
mm::random();
}


int main()
{
compare(a,b);
return 0;
}

and compare is :


template<typename F1,typename F2>
void compare(F1 fp1,F2 fp2)
{
double t1,t2;
clock_t ini = clock();
fp1();
clock_t fin = clock();
t1 = double((fin - ini))/double(CLOCKS_PER_SEC/1000);
ini = clock();
fp2();
fin = clock();
t2 = double((fin - ini))/double(CLOCKS_PER_SEC/1000);
std::cout<<"First one took: "<<t1<<" ms\n";
std::cout<<"Second one took: "<<t2<<" ms\n";
}

Codeplug
10-19-2011, 09:54 AM
>> maybe some optimization is at play here ?
No. One is a system call, the other isn't.

gg

manasij7479
10-19-2011, 09:57 AM
>> maybe some optimization is at play here ?
No. One is a system call, the other isn't.

gg
rand() is a system call ?

MK27
10-19-2011, 09:58 AM
Yeah, I tried something like that; generating 10000000 random numbers with rand() took 0.12s, reading /dev/urandom took 20s, which is still ~200x slower.



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

int main(void) {
int x, i;

srand(time(NULL));

for (i = 0; i < 10000000; i++) {
x = rand();
}

return 0;
}




#include <stdio.h>
#include <fcntl.h>

int main(void) {
int x, i,
fd = open("/dev/urandom", O_RDONLY),
sz = sizeof(int);

if (fd < 3) {
perror("open");
return -1;
}

for (i = 0; i < 10000000; i++) {
if (read(fd, &x, sz) != sz) fprintf(stderr,"short read!\n");
}

close(fd);

return 0;
}


I notice most of the time reading urandom is sys time:

real 0m19.972s
user 0m0.601s
sys 0m19.365s


rand() is a system call ?

/dev/urandom is definitely a kernel service.

I had thought rand() depended on accessing a special hardware generator (which would make it a system call too), but I now think it is 100% a product of the C lib.

Nominal Animal
10-19-2011, 05:00 PM
Use a pseudorandom number generator, such as Xorshift, and only seed it from /dev/urandom. Here is some example C99 code:


#include <unistd.h>
#include <sys/types.h>
#include <fcntl.h>
#include <errno.h>
#include <stdint.h>

/* Xorshift state - default
*/
static uint32_t prng_state[4] = { 123456789, 362436069, 521288629, 88675123 };

/* Generate a new 32-bit unsigned pseudorandom integer using Xorshift algorithm
*/
static inline uint32_t prng_u32(void)
{
uint32_t t = prng_state[0] ^ (prng_state[0] << 11);
prng_state[0] = prng_state[1];
prng_state[1] = prng_state[2];
prng_state[2] = prng_state[3];
prng_state[3] ^= (prng_state[3] >> 19) ^ (t ^ (t >> 8));
return prng_state[3];
}

/* Read new pseudorandom number generator state from device.
* Returns 0 if successful, errno otherwise (and state unchanged).
* (Reads 16 bytes from /dev/urandom to prng_state.)
*/
int prng_randomize(const char *const device)
{
uint32_t state[4] = { 0, 0, 0, 0 };
char *const q = (char *)&state[4];
char *p;
ssize_t n;
int descriptor, result;

if (!device || !device)
return EINVAL;

do {
descriptor = open(device, O_RDONLY | O_NOCTTY);
} while (descriptor == -1 && errno == EINTR);
if (descriptor == -1)
return errno;

do {
p = (char *)&state[0];

while (p < q) {

n = read(descriptor, p, (size_t)(q - p));
if (n > (ssize_t)0) {
p += n;
} else
if (n != (ssize_t)-1) {
do {
result = close(descriptor);
} while (result == -1 && errno == EINTR);
return errno = EIO;
} else
if (errno != EINTR) {
const int saved_errno = errno;
do {
result = close(descriptor);
} while (result == -1 && errno == EINTR);
return errno = saved_errno;
}
}

} while (!state[0] && !state[1] && !state[2] && !state[3]);

do {
result = close(descriptor);
} while (result == -1 && errno == EINTR);
if (result == -1)
return errno;

prng_state[0] = state[0];
prng_state[1] = state[1];
prng_state[2] = state[2];
prng_state[3] = state[3];

return 0;
}

/* Helper function: Count the number of bits value needs
*/
static inline unsigned int bits_used(uint32_t value)
{
int b = 1;

#ifdef __GNUC__
if (sizeof(unsigned long) == 4)
return 32 - __builtin_clzl((unsigned long)value);
if (sizeof(unsigned int) == 4)
return 32 - __builtin_clz((unsigned int)value);
#endif

if (value >= (uint64_t)65536) { b += 16; value >>= 16; }
if (value >= (uint64_t)256) { b += 8; value >>= 8; }
if (value >= (uint64_t)16) { b += 4; value >>= 4; }
if (value >= (uint64_t)4) { b += 2; value >>= 2; }
if (value >= (uint64_t)2) { b += 1; value >>= 1; }

return b;
}

/* Generate a pseudorandom number [min, max), i.e. [min, max-1].
* Remember to initialize the seed using prng_initialize(),
* or you will always receive the same sequence.
*/
int prng_irange(const int min, const int max)
{
if (max > min) {

const uint32_t range = (uint32_t)(max - min);
const uint32_t mask = (0xFFFFFFFFUL) >> (32 - bits_used(range));
uint32_t value;

do {
value = prng_u32() & mask;
} while (value > range);

return min + (int)value;

} else
return min;
}

I initially published the above source code here (http://www.linuxquestions.org/questions/programming-9/generate-long-digits-random-number-in-c-c-903389/page2.html#post4474892) in mid-September. It seems to be quite well behaved ("random"), and it is quite efficient, too.

The prng_initialize() function will read the new 16-byte state from /dev/urandom, giving you a different sequence. You only need to call that once at the beginning of your program.

The prng_irange(min,max) function returns a pseudorandom integer, min <= result < max. It uses the exclusion method, which avoids the (very small) bias for small values when using the modulus operator. (If the range is not divisible by the modulus, then the "topmost" part of the range will fall on the smaller end of the range, yielding smaller values a bit more often than large values.)

In a game the difference is trivial, so you might not need that; instead, you might use the following variant. It uses an inclusive range, does not care if min > max, and uses the modulus operator:


/* Return a pseudorandom integer [min, max].
* This function may return both min and max; the range is inclusive.
*/
int prng_int(const int min, const int max)
{
if (max > min)
return min + (prng_u32() % (uint32_t)(max - min + 1));
else if (min > max)
return max + (prng_u32() % (uint32_t)(min - max + 1));
else
return min;
}

If you need to generate a large number of pseudorandom integers within a constant range, modifying the prng_irange(min,max) function will most likely be the fastest option. This is because you only need to calculate the range and mask once for the entire set, and generating (on average, never more than two numbers per one used) the discarded numbers may be faster than taking a modulus. (Modulus happens to be a pretty slow operation.)

Hope this helps.