Like Tree1Likes
  • 1 Post By Nominal Animal

How feasible is this way of generating random numbers ?

This is a discussion on How feasible is this way of generating random numbers ? within the Linux Programming forums, part of the Platform Specific Boards category; I know they are covered in the standard library, but couldn't resist to experiment. This could be slow due to ...

  1. #1
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498

    How feasible is this way of generating random numbers ?

    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.
    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;    
    }
    PS: Taking 5 readings because, somehow in my machine, the first one is mostly coming 0;
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  2. #2
    Registered User
    Join Date
    Oct 2006
    Posts
    2,266
    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.
    Last edited by Elkvis; 10-19-2011 at 07:22 AM.

  3. #3
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    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 ?
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by manasij7479 View Post
    This could be slow due to opening the file
    No, because it is not a real file. There is no hard disk IO bottleneck.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    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 ?
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  6. #6
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by manasij7479 View Post
    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.
    Last edited by MK27; 10-19-2011 at 08:02 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  7. #7
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Unfortunately, even after removing most of the bells and whistles from the function,
    Code:
    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 ?
    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;
    }
    and compare is :
    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";
        }
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  8. #8
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,630
    >> maybe some optimization is at play here ?
    No. One is a system call, the other isn't.

    gg

  9. #9
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    Quote Originally Posted by Codeplug View Post
    >> maybe some optimization is at play here ?
    No. One is a system call, the other isn't.

    gg
    rand() is a system call ?
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  10. #10
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    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;
    }
    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;
    }
    I notice most of the time reading urandom is sys time:

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


    Quote Originally Posted by manasij7479 View Post
    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.
    Last edited by MK27; 10-19-2011 at 10:04 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  11. #11
    Registered User
    Join Date
    Oct 2011
    Posts
    825
    Use a pseudorandom number generator, such as Xorshift, and only seed it from /dev/urandom. Here is some example C99 code:
    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 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:
    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;
    }
    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.
    manasij7479 likes this.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Generating Random Numbers
    By Flakster in forum C++ Programming
    Replies: 14
    Last Post: 08-22-2005, 12:50 PM
  2. Generating Random Numbers
    By pizzapie in forum C++ Programming
    Replies: 17
    Last Post: 09-23-2004, 02:46 AM
  3. Generating Random Numbers
    By FromHolland in forum C++ Programming
    Replies: 6
    Last Post: 06-16-2003, 09:05 AM
  4. Help generating random numbers in MFC
    By drb2k2 in forum C++ Programming
    Replies: 3
    Last Post: 04-08-2003, 08:52 AM
  5. Generating Random Numbers
    By knight543 in forum C++ Programming
    Replies: 3
    Last Post: 01-11-2002, 05:55 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21