Printable View
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.
PS: Taking 5 readings because, somehow in my machine, the first one is mostly coming 0;Code: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;
}
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.
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 ?
No, because it is not a real file. There is no hard disk IO bottleneck.Quote:
Originally Posted by manasij7479
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 !Quote:
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.
Excellent... any other bottlenecks to be aware about, when using in a game loop ?Quote:
No, because it is not a real file. There is no hard disk IO bottleneck.
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().Quote:
Originally Posted by manasij7479
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.
Unfortunately, even after removing most of the bells and whistles from the function,
... it turns out to be more than 4000 times slower than rand() ! .. maybe some optimization is at play here ?Code:int random()
{
ifstream in;
in.open("/dev/urandom");
return in.get();
}
and compare is :Code:#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;
}
Code: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";
}
>> maybe some optimization is at play here ?
No. One is a system call, the other isn't.
gg
rand() is a system call ?Quote:
Originally Posted by Codeplug
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.
Code:#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;
}
I notice most of the time reading urandom is sys time:Code:#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;
}
real 0m19.972s
user 0m0.601s
sys 0m19.365s
/dev/urandom is definitely a kernel service.Quote:
Originally Posted by manasij7479
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.
Use a pseudorandom number generator, such as Xorshift, and only seed it from /dev/urandom. Here is some example C99 code:
I initially published the above source code here in mid-September. It seems to be quite well behaved ("random"), and it is quite efficient, too.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;
}
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:
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.)Code:/* 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;
}
Hope this helps.