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

ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Welcome to LinuxQuestions.org, a friendly and active Linux Community.

You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!

Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.

If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.

Having a problem logging in? Please visit this page to clear all LQ-related cookies.

Introduction to Linux - A Hands on Guide

This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.

Click Here to receive this Complete Guide absolutely free.

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.

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.

Distribution: RHEL 5.1 on My PC, & SunOS / Sun Solaris, RHEL, SuSe, Debian, FreeBSD and other Linux flavors @ Work

Posts: 582

Original Poster

Rep:

Shell Script and C

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:

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!

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.

Distribution: RHEL 5.1 on My PC, & SunOS / Sun Solaris, RHEL, SuSe, Debian, FreeBSD and other Linux flavors @ Work

Posts: 582

Original Poster

Rep:

An Excellent Large Digits Pseudo-Random Number Generator

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.

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;
}

Last edited by devUnix; 09-18-2011 at 04:50 AM.
Reason: Thread Marked as "Solved"

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.)

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;
}

Last edited by H_TeXMeX_H; 09-20-2011 at 11:31 AM.

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].

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.