[SOLVED] Generate Long Digits Random Number in C / C++

devUnix · 09-17-2011, 08:12 AM

Quote:

Originally Posted by Anisha Kaul

Are you getting the same result with:
g++ -Wall randomize.cpp too?

Hi Anisha!

Ho are you doing? Long time... hm. Anyways, thanks for the syntax for compiling a g++ program:

Code:

[demo@localhost C]$ mv randomize randomize.cpp
[demo@localhost C]$ g++ -Wall randomize.cpp 
[demo@localhost C]$ ls -ltr
total 9
-rw-rw-r--. 1 demo demo  614 Sep 16 13:18 randomize.cpp
-rwxrwxr-x. 1 demo demo 5782 Sep 17 09:07 a.out

Code:

[demo@localhost C]$ a.out
4.03202e+08

However, the result is something I can't ever comprehend as I could with much difficulty pass my paper of Mathematics. That is why I avoid such examples that deal with numbers.

devUnix · 09-17-2011, 08:19 AM

Quote:

Originally Posted by ta0kira

What about something like this:

Code:

#include <stdio.h>
#include <assert.h>
#include <fcntl.h>
#include <sys/stat.h>


static unsigned long get_random()
{
        static int random = -1;

        if (random < 0) assert((random = open("/dev/urandom", O_RDONLY)) >= 0);

        unsigned long value;
        read(random, &value, sizeof value);
        return value;
}


int main()
{
        int I;
        for (I = 0; I < 10; I++) fprintf(stderr, "%.16lx\n", get_random());
}

Kevin Barry

Thanks, Kavin!

Here's the output:

Code:

[demo@localhost C]$ a.out
2.0784e+08

devUnix · 09-17-2011, 08:27 AM

Quote:

Originally Posted by H_TeXMeX_H

I don't understand why you are using floating point for this.

Maybe what you want is:

PHP Code:


			
#include <stdio.h>

#include <stdlib.h>



int main(void)

{

    unsigned long number;

    srand(getpid());

    number = random() % 7100175000;

    printf("%010lu\n",number);

    return 0;

}

This works with integers.

I would agree with people above in that I would use /dev/random as the source of the seed for srand.

Code:

[demo@localhost C]$ gcc ran.c
ran.c: In function ‘main’:
ran.c:8: warning: integer constant is too large for ‘long’ type
[demo@localhost C]$

SigTerm · 09-17-2011, 12:03 PM

Okay, since you obviously won't "get" it...

Quote:

Originally Posted by devUnix

7100175000

rand() or random() return result that is not larger than RAND_MAX. RAND_MAX can be as low as 32767.
rand() and random() return either int or long.
int or long can be 4 bytes big (32 bits).
The maximum number you can store in 32 bits is 2^31 - 1 (i.e. 2147483643) for signed int and 2^32 - 1 (i.e. 4294967295) for unsigned int.
7100175000 is larger than both of those limits. You'll need at least 33 bits to store this number.
double is a floating point type that ALWAYS stores fractional number and is not suitable for operations where integer precision is required - due to the rounding errors. For example, it is bad idea to store financial data as doubles or floats.

A lot of that info is explained within system manual. Did you read "man random" before saying that system function is "bugged"?

All this means that in order to generate random number that has 10 decimal digits, you have to use proper integer type (that has more than 32 bits) AND write your own version of rand(). You can write it completely from scratch (as a Nominal Animal did) or utilize system mechanisms (/dev/urandom (as ta0kira suggested) or rand() (as I suggested)). Unless you NEED high quality randomness, writing your own generator probably will be an overkill.

devUnix · 09-17-2011, 01:48 PM

Quote:

Originally Posted by SigTerm

Okay, since you obviously won't "get" it...

rand() or random() return result that is not larger than RAND_MAX. RAND_MAX can be as low as 32767.
rand() and random() return either int or long.
int or long can be 4 bytes big (32 bits).
The maximum number you can store in 32 bits is 2^31 - 1 (i.e. 2147483643) for signed int and 2^32 - 1 (i.e. 4294967295) for unsigned int.
7100175000 is larger than both of those limits. You'll need at least 33 bits to store this number.
double is a floating point type that ALWAYS stores fractional number and is not suitable for operations where integer precision is required - due to the rounding errors. For example, it is bad idea to store financial data as doubles or floats.

A lot of that info is explained within system manual. Did you read "man random" before saying that system function is "bugged"?

All this means that in order to generate random number that has 10 decimal digits, you have to use proper integer type (that has more than 32 bits) AND write your own version of rand(). You can write it completely from scratch (as a Nominal Animal did) or utilize system mechanisms (/dev/urandom (as ta0kira suggested) or rand() (as I suggested)). Unless you NEED high quality randomness, writing your own generator probably will be an overkill.

First, I liked your idea of writing my own Random Number Generator. Secondly, I did not get it when H_TeXMeX_H mentioned: "I don't understand why you are using floating point for this." because I forgot that double is a real / floating type of number data types. Thirdly, I did not mean that the system function "bugged" - it was my program that "bugged".

Actually, I generally do not write programs in C or C++. I had to turn to it just for the problem in question only. Initially I wrote a Shell Script for generating Random Numbers which were relatively of fewer digits long as the prefix (ideally first 6 digits) was known and hence fixed. Say: 1000 to 10000. But $RANDOM would not generate numbers larger than 32767 or near around that (as per the manual). The ABS (Adv. Bash Script) Guide (my most favourite Shell Script Guide) found on www.tldp.org says that to set a Floor / Lower Limit such as 1000 simply discard those numbers less than 1000. So, in case of a Lower Limit of 10000 it would take a lot of time in simply discarding unwanted numbers.

Yes, I did make use of "/dev/urandom" device file:

Code:

SEED=`head -n 1 /dev/urandom | od -N 1 | awk '{print $2}'`
RANDOM=$SEED
GET_RANDOM=$RANDOM

but when I was asked to deal with 10 Digits long numbers, my Shell Script would not fit in the picture anywhere. It could not even deal with generating 1000 to 9000 in 80 minutes or so. Just to get the last number "8999" it took over 20 minutes and that too in vain. I had to interrupt the execution of the program / shell script.

My C program did wonders! I entered the limit 1000 and 10000 and hit the enter key and the output was on my Computer's Screen!

Code:

[demo@localhost bin]$ time random_it 1000 10000 > 1K_to_10K

real	0m1.239s
user	0m0.272s
sys	0m0.005s

(I just executed the Shell Script program I had written. I had to cancel the execution because it was taking time in generating the last number 99 given the range of 1 to 100):

Code:

 
[demo@localhost bin]$ time random_it.sh
^C

real	3m31.990s
user	0m29.156s
sys	1m5.757s

That proves that a C program really works much faster than a simple Shell Script program. But Shell Script has it own unique significance and undeniable importance in the world of Unix / Linux.

Well, I have stated above the background of why I turned to C for some specific purpose. Thanks to all of you!

Nominal Animal · 09-17-2011, 11:16 PM

If speed is of an essence, or you need to generate a lot of large integers, consider this program:

Code:

#include <unistd.h>
#include <fcntl.h>
#include <stdint.h>
#include <errno.h>

static const uint64_t bit63 = (uint64_t)9223372036854775808.0;

/* Reverse output buffer, for outputting integers in an undefined order.
*/
static char        out_data[65536];
static char       *out_next = out_data + sizeof(out_data);
static char *const out_ends = out_data + sizeof(out_data);
static int         out_errno = 0;

/* Flush output buffer.
*/
static void out_flush(void)
{
	char        *p = out_next;
	char *const  q = out_ends;
	ssize_t      n;

	out_next = out_ends;

	while (p < q) {
		n = write(STDOUT_FILENO, p, (size_t)(q - p));
		if (n > (ssize_t)0) {
			p += n;
		} else
		if (n != (ssize_t)-1) {
			if (!out_errno)
				out_errno = EIO;
			return;
		} else
		if (errno != EINTR) {
			if (!out_errno)
				out_errno = errno;
			return;
		}
	}

	return;
}

/* Add an int64_t to the output buffer.
*/
static void out_i64(const int64_t value)
{
	uint64_t  u = (value < 0) ? -value : value;

	if (out_next <= out_data + 22)
		out_flush();

	*(--out_next) = '\n';

	do {
		*(--out_next) = '0' + (int)(u % (uint64_t)10);
		u /= (uint64_t)10;
	} while (u);

	if (value < 0)
		*(--out_next) = '-';

	return;
}


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

/* Xorshift pseudorandom number generator.
*/
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).
*/
static 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;
}

static inline int bits_used(uint64_t value)
{
        int b = 1;

#ifdef __GNUC__
        if (sizeof(unsigned long) >= 8)
                return 64 - __builtin_clzl((unsigned long)value);
        if (sizeof(unsigned long long) >= 8)
                return 64 - __builtin_clzll((unsigned long long)value);
#endif

        if (value >= (uint64_t)4294967296ULL) { b += 32; value >>= 32; }
        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;
}

static int parse_int64(const char *const string, int64_t *const ptr)
{
	const unsigned char *str  = (const unsigned char *)string;
	int                  sign = 0;
	uint64_t             val  = 0;

	if (!str)
		return EINVAL;

	while (*str == '\t' || *str == '\n' || *str == '\v' ||
	       *str == '\f' || *str == '\r' || *str == ' ')
		str++;

	while (*str == '-' || *str == '+')
		if (*(str++) == '-')
			sign = !sign;

	if (!(*str >= '0' && *str <= '9'))
		return ENOENT;

	while (*str >= '0' && *str <= '9') {
		const uint64_t old = val;

		val = (uint64_t)10 * val + (uint64_t)(*(str++) - '0');

		/* Overflow? */
		if (val < old)
			return EDOM;
	}

	if (sign) {
		/* Overflow? */
		if (val > bit63)
			return EDOM;

		if (ptr)
			*ptr = -val;
	} else {
		/* Overflow? */
		if (val >= bit63)
			return EDOM;

		if (ptr)
			*ptr = val;
	}

	while (*str == '\t' || *str == '\n' || *str == '\v' ||
	       *str == '\f' || *str == '\r' || *str == ' ')
		str++;

	return (*str) ? EILSEQ : 0;
}

static inline const char *const strend(const char *string)
{
#ifdef __GNUC__
	return string + __builtin_strlen(string);
#endif
	while (*string) string++;
	return string;
}

static int wr(const char *const message)
{
	if (message) {
		const char        *p = message;
		const char *const  q = strend(message);
		ssize_t            n;

		while (p < q) {
			n = write(STDERR_FILENO, p, (size_t)(q - p));
			if (n > (ssize_t)0)
				p += n;
			else
			if (n != (ssize_t)-1)
				return EIO;
			else
			if (errno != EINTR)
				return errno;
		}

		return 0;
	}

	return EINVAL;
} 

int main(int argc, char *argv[])
{
	int64_t  count, min, max;
	uint64_t range, value;
	int      bits;

	if (argc != 4) {
		wr("\n"
		   "Usage: "); wr(argv[0]); wr("\n"
		   "       "); wr(argv[0]); wr(" numbers min max\n"
		   "\n"
		   "This program will output 'numbers' pseudorandom integers\n"
		   "between min and max, inclusive, using the Xorshift algorithm.\n"
		   "(In other words, min and max may occur in the output.)\n"
		   "Each number is output on a separate line.\n"
		   "\n"
		   "Random number state is initialized from /dev/urandom.\n"
		   "Minimum recognized integer is -9223372036854775808, and\n"
		   "maximum recognized integer is  9223372036854775807.\n"
		   "\n");
		return (argc <= 1) ? 0 : 4;
	}

	if (parse_int64(argv[1], &count) || count < (int64_t)1) {
		wr(argv[1]); wr(": Invalid number of values to output.\n");
		return 1;
	}
	if (parse_int64(argv[2], &min)) {
		wr(argv[2]); wr(": Invalid minimum bound.\n");
		return 2;
	}
	if (parse_int64(argv[3], &max)) {
		wr(argv[3]); wr(": Invalid maximum bound.\n");
		return 3;
	}
	if (max <= min) {
		wr(argv[3]); wr(": Maximum bound must be greater than minimum ("); wr(argv[2]); wr(").\n");
		return 3;
	}

	if (prng_randomize("/dev/urandom"))
		wr("Warning: Cannot use /dev/urandom to randomize state.\n");

	range = max - min;
	bits = bits_used(range);

	if (bits > 32) {
		while (count-->(int64_t)0) {
			do {
				value = (uint64_t)prng_u32();
				value <<= 32;
				value ^= (uint64_t)prng_u32();
				value >>= 64 - bits;
			} while (value > range);
			out_i64(min + value);			
		}

	} else {
		while (count-->(int64_t)0) {
			do {
				value = prng_u32();
				value >>= 32 - bits;
			} while (value > range);
			out_i64(min + value);
		}
	}

	out_flush();
	return 0;
}

It uses the Xorshift random number generator, and (adapted versions of) the code I posted earlier in this thread. To avoid the printf() bottleneck (!), it uses a reverse output buffer, which allows for extremely fast output of integers (although the order in which each integer is output is "random"), using only division by 10 and modulo 10. It is locale insensitive, and uses only low-level I/O, not stdio.h.

Even on a lowly single-core Atom N270 processor, it can generate and output about a million signed ten-digit pseudorandom integers (-9999999999 to 9999999999, inclusive) per second. Or, about six million one-digit pseudorandom integers, -9 to 9, inclusive, per second. Or, about four hundred thousand 64-bit signed integers (-9223372036854775808 to 9223372036854775807, inclusive) per second.

I compiled it using

Code:

gcc -Wall -pedantic -O3 -std=c99 -o big-ints big-ints.c

and tested using

Code:

time ./big-ints 1000000 -9999999999 9999999999 >/dev/null

in case you want to compare it on your machine. Run it without parameters to see help/usage.

devUnix · 09-18-2011, 04:43 AM

Quote:

Originally Posted by Nominal Animal

If speed is of an essence, or you need to generate a lot of large integers, consider this program:

Code:

#include <unistd.h>
#include <fcntl.h>
#include <stdint.h>
#include <errno.h>

static const uint64_t bit63 = (uint64_t)9223372036854775808.0;

/* Reverse output buffer, for outputting integers in an undefined order.
*/
static char        out_data[65536];
static char       *out_next = out_data + sizeof(out_data);
static char *const out_ends = out_data + sizeof(out_data);
static int         out_errno = 0;

/* Flush output buffer.
*/
static void out_flush(void)
{
	char        *p = out_next;
	char *const  q = out_ends;
	ssize_t      n;

	out_next = out_ends;

	while (p < q) {
		n = write(STDOUT_FILENO, p, (size_t)(q - p));
		if (n > (ssize_t)0) {
			p += n;
		} else
		if (n != (ssize_t)-1) {
			if (!out_errno)
				out_errno = EIO;
			return;
		} else
		if (errno != EINTR) {
			if (!out_errno)
				out_errno = errno;
			return;
		}
	}

	return;
}

/* Add an int64_t to the output buffer.
*/
static void out_i64(const int64_t value)
{
	uint64_t  u = (value < 0) ? -value : value;

	if (out_next <= out_data + 22)
		out_flush();

	*(--out_next) = '\n';

	do {
		*(--out_next) = '0' + (int)(u % (uint64_t)10);
		u /= (uint64_t)10;
	} while (u);

	if (value < 0)
		*(--out_next) = '-';

	return;
}


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

/* Xorshift pseudorandom number generator.
*/
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).
*/
static 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;
}

static inline int bits_used(uint64_t value)
{
        int b = 1;

#ifdef __GNUC__
        if (sizeof(unsigned long) >= 8)
                return 64 - __builtin_clzl((unsigned long)value);
        if (sizeof(unsigned long long) >= 8)
                return 64 - __builtin_clzll((unsigned long long)value);
#endif

        if (value >= (uint64_t)4294967296ULL) { b += 32; value >>= 32; }
        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;
}

static int parse_int64(const char *const string, int64_t *const ptr)
{
	const unsigned char *str  = (const unsigned char *)string;
	int                  sign = 0;
	uint64_t             val;

	if (!str)
		return EINVAL;

	while (*str == '\t' || *str == '\n' || *str == '\v' ||
	       *str == '\f' || *str == '\r' || *str == ' ')
		str++;

	while (*str == '-' || *str == '+')
		if (*(str++) == '-')
			sign = !sign;

	if (!(*str >= '0' && *str <= '9'))
		return ENOENT;

	while (*str >= '0' && *str <= '9') {
		const uint64_t old = val;

		val = (uint64_t)10 * val + (uint64_t)(*(str++) - '0');

		/* Overflow? */
		if (val < old)
			return EDOM;
	}

	if (sign) {
		/* Overflow? */
		if (val > bit63)
			return EDOM;

		if (ptr)
			*ptr = -val;
	} else {
		/* Overflow? */
		if (val >= bit63)
			return EDOM;

		if (ptr)
			*ptr = val;
	}

	while (*str == '\t' || *str == '\n' || *str == '\v' ||
	       *str == '\f' || *str == '\r' || *str == ' ')
		str++;

	return (*str) ? EILSEQ : 0;
}

static inline const char *const strend(const char *string)
{
#ifdef __GNUC__
	return string + __builtin_strlen(string);
#endif
	while (*string) string++;
	return string;
}

static int wr(const char *const message)
{
	if (message) {
		const char        *p = message;
		const char *const  q = strend(message);
		ssize_t            n;

		while (p < q) {
			n = write(STDERR_FILENO, p, (size_t)(q - p));
			if (n > (ssize_t)0)
				p += n;
			else
			if (n != (ssize_t)-1)
				return EIO;
			else
			if (errno != EINTR)
				return errno;
		}

		return 0;
	}

	return EINVAL;
} 

int main(int argc, char *argv[])
{
	int64_t  count, min, max;
	uint64_t range, value;
	int      bits;

	if (argc != 4) {
		wr("\n"
		   "Usage: "); wr(argv[0]); wr("\n"
		   "       "); wr(argv[0]); wr(" numbers min max\n"
		   "\n"
		   "This program will output 'numbers' pseudorandom integers\n"
		   "between min and max, inclusive, using the Xorshift algorithm.\n"
		   "(In other words, min and max may occur in the output.)\n"
		   "Each number is output on a separate line.\n"
		   "\n"
		   "Random number state is initialized from /dev/urandom.\n"
		   "Minimum recognized integer is -9223372036854775808, and\n"
		   "maximum recognized integer is  9223372036854775807.\n"
		   "\n");
		return (argc <= 1) ? 0 : 4;
	}

	if (parse_int64(argv[1], &count) || count < (int64_t)1) {
		wr(argv[1]); wr(": Invalid number of values to output.\n");
		return 1;
	}
	if (parse_int64(argv[2], &min)) {
		wr(argv[2]); wr(": Invalid minimum bound.\n");
		return 2;
	}
	if (parse_int64(argv[3], &max)) {
		wr(argv[3]); wr(": Invalid maximum bound.\n");
		return 3;
	}
	if (max <= min) {
		wr(argv[3]); wr(": Maximum bound must be greater than minimum ("); wr(argv[2]); wr(").\n");
		return 3;
	}

	if (prng_randomize("/dev/urandom"))
		wr("Warning: Cannot use /dev/urandom to randomize state.\n");

	range = max - min;
	bits = bits_used(range);

	if (bits > 32) {
		while (count-->(int64_t)0) {
			do {
				value = (uint64_t)prng_u32();
				value <<= 32;
				value ^= (uint64_t)prng_u32();
				value >>= 64 - bits;
			} while (value > range);
			out_i64(min + value);			
		}

	} else {
		while (count-->(int64_t)0) {
			do {
				value = prng_u32();
				value >>= 32 - bits;
			} while (value > range);
			out_i64(min + value);
		}
	}

	out_flush();
	return 0;
}

It uses the Xorshift random number generator, and (adapted versions of) the code I posted earlier in this thread. To avoid the printf() bottleneck (!), it uses a reverse output buffer, which allows for extremely fast output of integers (although the order in which each integer is output is "random"), using only division by 10 and modulo 10. It is locale insensitive, and uses only low-level I/O, not stdio.h.

Even on a lowly single-core Atom N270 processor, it can generate and output about a million signed ten-digit pseudorandom integers (-9999999999 to 9999999999, inclusive) per second. Or, about six million one-digit pseudorandom integers, -9 to 9, inclusive, per second. Or, about four hundred thousand 64-bit signed integers (-9223372036854775808 to 9223372036854775807, inclusive) per second.

I compiled it using

Code:

gcc -Wall -pedantic -O3 -std=c99 -o big-ints big-ints.c

and tested using

Code:

time ./big-ints 1000000 -9999999999 9999999999 >/dev/null

in case you want to compare it on your machine. Run it without parameters to see help/usage.

Guru! You're great!

Code:

[demo@localhost C]$ time randomIt 100 9999999989 9999999990 | tail -n 2
9999999989
9999999989

real	0m0.004s
user	0m0.000s
sys	0m0.000s
[demo@localhost C]$ time randomIt 100 9999999989 9999999990 | tail -n 2

Code:

[demo@localhost C]$ time randomIt 900 9999990100 9999991000 | sort -nu | wc -l
551 

real	0m0.016s
user	0m0.002s
sys	0m0.006s
[demo@localhost C]$

Your devised program really outputs large numbers without failing!

In order to check that I get unique random numbers (equivalent to the first parameter: count (program 100 1 100)) in the final output, I know what to do next (or shall be able to figure it out as that logic is in place in my C program that works fine for fewer digits long numbers).

But I must state: I do not want to copy & paste your program and put to use. I want to understand it and the logic / algorithm that you have applied to it. Your program is a good case-study for those who want a large random number generator and want to see how it is designed and made to work!

Your 321 Lines Long C Program is really awesome! Did you put that much effort just to help me or us?

Code:

if (SOLUTION_PROVIDED_BY == "Nominal Animal"){
     printf("SUCCESS");
     return 0;
}
else {
     printf("NEED MORE RESOURCES");
     return 1;
}

Nominal Animal · 09-19-2011, 03:20 PM

Quote:

Originally Posted by devUnix

In order to check that I get unique random numbers

To check the distribution, I use awk to generate a histogram (of all the things awk sees -- may be useful for a variety of things):

Code:

./test 1000000 -99 99 \
| awk '{ n++; c[$1]++ }
   END { m=100.0/n
         for (i in c)
            printf("%15s\t%7.3f%% %d\n", i, c[i]*m, c[i])
       }' | sort -g

Plot the output in for example gnuplot.

Since the above will not check for holes, I sometimes use a variant,

Code:

MIN=-99 MAX=99
./test 1000000 $MIN $MAX \
| awk -v min=$MIN -v max=$MAX '{ n++; c[$1]++ }
   END { for (i in c)
             if (i-min < 0 || i-max > 0 ) {
                 printf("%s outside the allowed range [%s, %s]!\n", i, min, max)
                 exit(1)
             }
         a = n / (max - min + 1)
         m = 100.0 / n
         for (i = min; i <= max; i++)
             printf("%15d\t%7.3f%% %+7.3f%% %d %+d\n", i, m*c[i], 100.0*(c[i] - a)/a, c[i], c[i] - a)
       }'

which outputs the relative frequencies of each integer in the given range, too.

Both of those check only the output, not the "randomness" of the pseudorandom number generator.

Quote:

Originally Posted by devUnix

But I must state: I do not want to copy & paste your program and put to use. I want to understand it and the logic / algorithm that you have applied to it.

That is excellent to hear; I highly approve.

I myself am trying to learn to better comment the logic behind the code, as opposed to commenting the often obvious. (Instead of using the comments to describe what the code does, I'd like to say why something is done.) There is always room for improvement.

For example, consider the exclusion method. I use it instead of the (RANDOM % RANGE) method, to avoid any bias depending on the range. I generate exactly the needed N bits for each value, but exclude (less than 50% on average) those that are outside the range. If you end up using non-uniform random numbers, you will be using the exclusion method elsewhere, too. For example, to generate 2D or 3D points within a unit circle/sphere (a circle or sphere centered around origin, radius 1), you generate random points within a unit cube, and discard those that are further than 1 from origin. So understanding the exclusion method is much more important than understanding my implementation.

I did not bother to polish and clean up the program, so it's full of all kinds of weirdnesses; overall, the program flow should be relatively straight-forward, though. If you need clarifications on something, feel free to ask!

Quote:

Originally Posted by devUnix

Did you put that much effort just to help me or us?

Yes, and no. The Xorshift pseudorandom number generator had slipped me by, so I wanted to try it out anyway. Since I had showed the other bits earlier already, putting it all together was just a finishing touch.

I love the way interesting problems here tend to get solutions that approach the issue from wildly different directions. I believe that variety drives better solutions. (The old saying: if the only tool you have is a hammer, all problems tend to look like nails. If you have enough good tools, you start to think what you want to accomplish first.)

H_TeXMeX_H · 09-20-2011, 10:29 AM

For this big-ints program I get:

Code:

bash-4.1$ ./big-ints 1000000 -9999999999 9999999999
1000000: Invalid number of values to output.

Just for practice I wrote a program that uses /dev/urandom directly, as it is the kernel pseudo-RNG.

Code:

// print random numbers from /dev/urandom
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char * argv[])
{
	// not init
	FILE *urandom; // file handle for /dev/urandom
	unsigned long i; // counter
	
	// init
	unsigned long num = 0;
	unsigned long min = 0;
	unsigned long max = 0;
	unsigned long read = 0;
	
	// parse argv
	if (4 == argc)
	{
		sscanf(argv[1], "%lu", &num);
		sscanf(argv[2], "%lu", &min);
		sscanf(argv[3], "%lu", &max);
	}
	else
	{
		printf("Usage:\n%s number minimum maximum\nExample:\n%s 100 1 100\n", argv[0], argv[0]);
		exit(1);
	}
	
	// open /dev/urandom as readonly binary
	urandom = fopen("/dev/urandom", "rb");
	if (urandom == NULL)
	{
		perror("!!! ERROR: could not open /dev/urandom for reading !!!");
		exit(1);
	}
	
	// print random numbers
	for (i=0; i < num; i++)
	{
		// read from urandom
		if (fread(&read, sizeof(read), 1, urandom) < 1)
		{
			perror("!!! ERROR: failed to read from /dev/urandom !!!");
			exit(1);
		}
		printf("%lu\n", read % (max - min + 1) + min);
		// % mod + min
		// max = mod + min - 1
		// mod = max - min + 1
	}
	
	// close /dev/urandom
	fclose(urandom);
	
	return 0;
}

Nominal Animal · 09-20-2011, 12:51 PM

Quote:

Originally Posted by H_TeXMeX_H

For this big-ints program I get:

Code:

bash-4.1$ ./big-ints 1000000 -9999999999 9999999999
1000000: Invalid number of values to output.

That is strange, I cannot reproduce that.. Ah, it appears there was a bug in parse_int64(); I forgot to initialize val to zero. Could you modify the line uint64_t val; to uint64_t val=0; and restest, please? I've modified my post above, as well, if you'd just rather re-copy-paste the sources.

Quote:

Originally Posted by H_TeXMeX_H

Just for practice I wrote a program that uses /dev/urandom directly, as it is the kernel pseudo-RNG.

Nice, but on 32-bit architectures, you're still limited to [0, 4294967295].

H_TeXMeX_H · 09-20-2011, 01:20 PM

Yes, it works now, thanks. Quite an interesting program, and it is probably the fastest way to do it.