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

You see, when I gave 10 Digits Long Numbers, the Program Bugged! But when I gave 5 Digits Number to deal with then it went happily!

I tried some other function namely: random():

Code:

cat long_random.c
#include <stdio.h>
#include <stdlib.h>
int main(){
long double number;
srand(getpid());
number = random() % 7100175000;
printf("%Lg",number);
return 0;
}

Compiling the above program:

Code:

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

Let us try with a fewer digits long number:

Code:

[demo@localhost bin]$ cat long_random.c
#include <stdio.h>
#include <stdlib.h>
int main(){
long double number;
srand(getpid());
number = random() % 175000;
printf("%Lg",number);
return 0;
}

So, the bottom line of the problem, as explained above, is: Is there a way to get a large random number in C or C++?

Please note that:

I am using a Linux Box - not a Windows Box to test that, and

I need 10 Digits Long Random Numbers because they are going to be used as an MDN or a Mobile Number because the project that I am working on is a VAS Project.

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

Posts: 576

Original Poster

Rep:

Quote:

Originally Posted by H_TeXMeX_H

Use 'unsigned long' to get larger numbers, you are getting integer overflow.

I have used "unsigned long" as well as "long double" in my first program shown above. None works.

One more thing:
long double num;
num = random();
printf("%Lg",num);

gives numbers in a scientific notation. How can we convert a scientific number in a human readable number? (However, not so important it is as of now.)

#include <stdio.h>
#include <stdlib.h>
typedef unsigned long long Rand;
Rand bigRand(Rand range = 0){
int numIterations = 0;
for (Rand test = range ? range: ~Rand(0); test > 0; numIterations++){
test /= (Rand)RAND_MAX;
}
Rand result = 0;
for (int i = 0; i < numIterations; i++)
result = result * RAND_MAX + rand();
return range ? result % range: result;
}
int main(int argc, char** argv){
for (int i = 0; i < 10; i++){
Rand tmp = bigRand();
#if defined(WIN32)|| defined(WIN64) || defined(_WIN32) || defined(_WIN64)
printf("%I64u\n", tmp);
#else
printf("%llu\n", tmp);
#endif
}
return 0;
}

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

Posts: 576

Original Poster

Rep:

Compilation Fails

Quote:

Originally Posted by SigTerm

Code:

#include <stdio.h>
#include <stdlib.h>
typedef unsigned long long Rand;
Rand bigRand(Rand range = 0){
int numIterations = 0;
for (Rand test = range ? range: ~Rand(0); test > 0; numIterations++){
test /= (Rand)RAND_MAX;
}
Rand result = 0;
for (int i = 0; i < numIterations; i++)
result = result * RAND_MAX + rand();
return range ? result % range: result;
}
int main(int argc, char** argv){
for (int i = 0; i < 10; i++){
Rand tmp = bigRand();
#if defined(WIN32)|| defined(WIN64) || defined(_WIN32) || defined(_WIN64)
printf("%I64u\n", tmp);
#else
printf("%llu\n", tmp);
#endif
}
return 0;
}

Compilation Errors:

Code:

[demo@localhost C]$ gcc randomize.c
randomize.c:6: error: expected ‘;’, ‘,’ or ‘)’ before ‘=’ token
randomize.c: In function ‘main’:
randomize.c:19: error: ‘for’ loop initial declarations are only allowed in C99 mode
randomize.c:19: note: use option -std=c99 or -std=gnu99 to compile your code
[demo@localhost C]$ gcc -std=gnu99 randomize.c
randomize.c:6: error: expected ‘;’, ‘,’ or ‘)’ before ‘=’ token
randomize.c: In function ‘main’:
randomize.c:20: warning: implicit declaration of function ‘bigRand’
[demo@localhost C]$

By the way, thanks for these two lines in your code:

Code:

typedef unsigned long long Rand;

and

Code:

printf("%llu\n", tmp);

I did not know "long long" type... thing.

Here is some extra info with regard to the compiler:

Code:

[demo@localhost C]$ gcc --version
gcc (GCC) 4.4.4 20100726 (Red Hat 4.4.4-13)
Copyright (C) 2010 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
[demo@localhost C]$

OP wants 10-digit decimal numbers, like "7100175000". sizeof(unsigned long) can be == 4. Do you see the problem?

I was demonstrating an approach, not a solution. I didn't feel like solving OP's exact problem. That's why I said "something like this" rather than "this". Anyway, reading /dev/urandom is a legitimate way to generate random data of any width.
Kevin Barry

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.

Quote:

Originally Posted by devUnix

I need 10 Digits Long Random Numbers because they are going to be used as an MDN or a Mobile Number because the project that I am working on is a VAS Project.

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

Last edited by H_TeXMeX_H; 09-16-2011 at 03:41 PM.

Let us break the process into constituent problems.

To generate a pseudorandom integer in range [min,max] inclusive -- meaning we may return min and max too --, we need a function that generates a pseudorandom integer in range [0,range] inclusive. Usually the range is specified to not include the upper boundary (i.e. [0,range-1]), but you will want the range to be inclusive for simplicity. Note that we don't need to deal with signed or negative numbers.

Let's assume we have a function FOO(), which returns FOO_BITS random bits. Since we are working with unsigned integers, we don't need to worry about sign, so we can just concatenate enough bits. Consider this C99 code:

Code:

#include <stdint.h>
#define FOO_BITS 16
#define FOO() (rand() & 65535)
static inline uint64_t random_bits(const int bits)
{
int bits_need = (bits < 64) ? bits : 64;
int bits_have;
uint64_t value = 0;
/* Concatenate enough pseudorandom bits */
for (bits_have = 0; bits_have < bits_need; bits_have += FOO_BITS)
value |= ((uint64_t)FOO()) << bits_have;
/* We got at most 64 bits. */
if (bits_have > 64)
bits_have = 64;
/* Strip excess bits. */
if (bits_have > bits_need)
value >>= bits_have - bits_need;
return value;
}

Note that if you want uniform random number without a small-number bias, you should not use random MODULO (range+1) ; it will have a slight bias for very small numbers, increasing the closer range is to the maximum random value. For small ranges it may be undetectable, but in the general case it is not. To avoid this, I recommend the exclusion method.

If you use the built-in rand(), feel free to use the modulo method. The built-in rand(), as well as other linear congruential pseudorandom number generators, are not random enough anyway to worry about such a small bias in the results. Remember to include the stdlib.h header file, and set a suitable random number seed using srand(), though.

In the exclusion method, we generate a random integer with exactly as many bits as is needed for the maximum allowed random number. (This is the point why we want the range to be inclusive, since then it is this number.) If the random number is larger than the maximum allowed, discard it and generate a new one. If you work out the math, you will find out that the probability for discarding a generated value is always less than 50%.

To find out the number of bits in an uint64_t, I use

Code:

static inline int bits(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;
}

There are faster methods for the workaround, but I prefer this one for conciseness. Many other C99 compilers have the same built-ins; I'm only certain of GCC, though. When any level of code optimization is used, the compiler should discard the unused code paths, yielding very fast code.

Let's add the missing bit of code: the pseudorandom number generation to fit a specified range. Remember, both limits are inclusive, i.e. the function may return minimum or maximum or anything in between.

Code:

static inline int64_t rnd(const int64_t minimum, const int64_t maximum)
{
if (minimum < maximum) {
const uint64_t range = maximum - minimum;
const int nbits = bits(range);
uint64_t value;
do {
value = random_bits(nbits);
} while (value > range);
return (int64_t)minimum + (int64_t)value;
}
if (maximum < minimum) {
const uint64_t range = minimum - maximum;
const int nbits = bits(range);
uint64_t value;
do {
value = random_bits(nbits);
} while (value > range);
return (int64_t)maximum + (int64_t)value;
}
/* minimum == maximum */
return minimum;
}

As you can see, only bit operations, addition and substraction are needed. This means you can quite easily extend this to arbitrary-sized integers.

Like I said, C library rand() is quite poor. I recommend using a Mersenne Twister for 32- or 64-bit words. I've found that it is usually better to use a secondary array to store "tempered" values -- the secondary array can be several times the MT array, and you can generate multiple "rounds" at a time, taking advantage of cache locality, but using more memory of course.

To read the random number seed (actually, full 128-bit state) from e.g. /dev/urandom -- which I too agree is a good idea --, you can use e.g.

Code:

#include <unistd.h>
#include <fcntl.h>
#include <errno.h>
/* Read new random state from the specified device; recommend
* /dev/urandom
* The function returns 0 if success, error (errno) otherwise.
*/
int randomize_state(const char *const filename)
{
char *const q = (char *)random_state + sizeof(random_state);
char *p;
int descriptor, result;
ssize_t n;
if (!filename || !*filename)
return EINVAL;
do {
descriptor = open(filename, O_RDONLY | O_NOCTTY);
} while (descriptor == -1 && errno == EINTR);
if (descriptor == -1)
return errno;
do {
p = (char *)random_state;
while (p < q) {
n = read(descriptor, p, (size_t)(q - p));
if (n > 0)
p += n;
else
if (n != (ssize_t)-1) {
const int saved_errno = EIO;
do {
result = close(descriptor);
} while (result == -1 && errno == EINTR);
return saved_errno;
} else
if (errno != EINTR) {
const int saved_errno = errno;
do {
result = close(descriptor);
} while (result == -1 && errno == EINTR);
return saved_errno;
}
}
/* All-zeros is an invalid state.
* In the unlikely event we got that,
* just read new state.
*/
} while (!random_state[0] && !random_state[1] &&
!random_state[2] && !random_state[3]);
do {
result = close(descriptor);
} while (result == -1 && errno == EINTR);
if (result == -1)
return errno;
return 0;
}

For those interested, Xorshift has a period of (2**128)-1 (or 340282366920938463463374607431768211455), whereas Mersenne Twister has (2**19937)-1 (a six-thousand digit number starting with 4). Both are large enough to not repeat in practice, I think.

Last edited by Nominal Animal; 09-16-2011 at 04:42 PM.

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