LinuxQuestions.org
Share your knowledge at the LQ Wiki.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 09-16-2011, 11:23 AM   #1
devUnix
Member
 
Registered: Oct 2010
Location: Bengaluru, India
Distribution: RHEL 5.1 on My PC, & SunOS / Sun Solaris, RHEL, SuSe, Debian, FreeBSD and other Linux flavors @ Work
Posts: 557

Rep: Reputation: 46
Generate Long Digits Random Number in C / C++


Hi Dosto!


How are you doing?

Well, let's get to the problem now.

I need to generate 10 Digits Long Random Numbers (within a range only - I can take care of the range part, though).

rand() function is not working for this purpose.

Let's have a look at some sample runs of the program I have written using rand():


Code:
[demo@localhost bin]$ a.out 7100101000 7100175000
Start: 2147483647
End: 2147483647
TOTAL: 0
Bugged!!! Bugged!!! Bugged!!!

Let us try with fewer digits long number:

Code:
[demo@localhost bin]$ a.out 70000 70010
Start: 70000
End: 70010
TOTAL: 10
70002
70005
70000
70006
70008
70003
70007
70001
70009
70004
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;
}
A Sample Run of the above program:

Code:
[demo@localhost bin]$ gcc long_random.c 
[demo@localhost bin]$ a.out
132777

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.

Last edited by devUnix; 09-16-2011 at 11:29 AM.
 
Old 09-16-2011, 11:34 AM   #2
H_TeXMeX_H
Guru
 
Registered: Oct 2005
Location: $RANDOM
Distribution: slackware64
Posts: 12,928
Blog Entries: 2

Rep: Reputation: 1269Reputation: 1269Reputation: 1269Reputation: 1269Reputation: 1269Reputation: 1269Reputation: 1269Reputation: 1269Reputation: 1269
Use 'unsigned long' to get larger numbers, you are getting integer overflow.
 
0 members found this post helpful.
Old 09-16-2011, 11:52 AM   #3
devUnix
Member
 
Registered: Oct 2010
Location: Bengaluru, India
Distribution: RHEL 5.1 on My PC, & SunOS / Sun Solaris, RHEL, SuSe, Debian, FreeBSD and other Linux flavors @ Work
Posts: 557

Original Poster
Rep: Reputation: 46
Quote:
Originally Posted by H_TeXMeX_H View Post
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.)

Last edited by devUnix; 09-16-2011 at 11:54 AM.
 
Old 09-16-2011, 11:57 AM   #4
SigTerm
Member
 
Registered: Dec 2009
Distribution: Slackware 12.2
Posts: 379

Rep: Reputation: 233Reputation: 233Reputation: 233
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;
}

Last edited by SigTerm; 09-16-2011 at 12:12 PM.
 
0 members found this post helpful.
Old 09-16-2011, 01:25 PM   #5
devUnix
Member
 
Registered: Oct 2010
Location: Bengaluru, India
Distribution: RHEL 5.1 on My PC, & SunOS / Sun Solaris, RHEL, SuSe, Debian, FreeBSD and other Linux flavors @ Work
Posts: 557

Original Poster
Rep: Reputation: 46
Compilation Fails

Quote:
Originally Posted by SigTerm View Post
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]$

Last edited by devUnix; 09-16-2011 at 01:28 PM.
 
Old 09-16-2011, 01:27 PM   #6
SigTerm
Member
 
Registered: Dec 2009
Distribution: Slackware 12.2
Posts: 379

Rep: Reputation: 233Reputation: 233Reputation: 233
Quote:
Originally Posted by devUnix View Post
Code:
[demo@localhost C]$ gcc
This is not C code, use g++.
 
0 members found this post helpful.
Old 09-16-2011, 01:41 PM   #7
devUnix
Member
 
Registered: Oct 2010
Location: Bengaluru, India
Distribution: RHEL 5.1 on My PC, & SunOS / Sun Solaris, RHEL, SuSe, Debian, FreeBSD and other Linux flavors @ Work
Posts: 557

Original Poster
Rep: Reputation: 46
g++ compilation error

Quote:
Originally Posted by SigTerm View Post
This is not C code, use g++.
Not sure on g++. Here is what I got now:

Code:
[demo@localhost C]$ g++ randomize 
randomize: file not recognized: File format not recognized
collect2: ld returned 1 exit status
[demo@localhost C]$
 
Old 09-16-2011, 02:15 PM   #8
TheIndependentAquarius
Senior Member
 
Registered: Dec 2008
Posts: 4,633
Blog Entries: 29

Rep: Reputation: 897Reputation: 897Reputation: 897Reputation: 897Reputation: 897Reputation: 897Reputation: 897
Are you getting the same result with:
g++ -Wall randomize.cpp too?
 
1 members found this post helpful.
Old 09-16-2011, 02:47 PM   #9
ta0kira
Senior Member
 
Registered: Sep 2004
Distribution: FreeBSD 9.1, Kubuntu 12.10
Posts: 3,078

Rep: Reputation: Disabled
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
 
Old 09-16-2011, 03:06 PM   #10
SigTerm
Member
 
Registered: Dec 2009
Distribution: Slackware 12.2
Posts: 379

Rep: Reputation: 233Reputation: 233Reputation: 233
Quote:
Originally Posted by ta0kira View Post
What about something like this:
OP wants 10-digit decimal numbers, like "7100175000". sizeof(unsigned long) can be == 4. Do you see the problem?
 
0 members found this post helpful.
Old 09-16-2011, 03:58 PM   #11
ta0kira
Senior Member
 
Registered: Sep 2004
Distribution: FreeBSD 9.1, Kubuntu 12.10
Posts: 3,078

Rep: Reputation: Disabled
Quote:
Originally Posted by SigTerm View Post
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
 
Old 09-16-2011, 04:36 PM   #12
H_TeXMeX_H
Guru
 
Registered: Oct 2005
Location: $RANDOM
Distribution: slackware64
Posts: 12,928
Blog Entries: 2

Rep: Reputation: 1269Reputation: 1269Reputation: 1269Reputation: 1269Reputation: 1269Reputation: 1269Reputation: 1269Reputation: 1269Reputation: 1269
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 View Post
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 04:41 PM.
 
0 members found this post helpful.
Old 09-16-2011, 04:48 PM   #13
Nominal Animal
Senior Member
 
Registered: Dec 2010
Location: Finland
Distribution: Xubuntu, CentOS, LFS
Posts: 1,723
Blog Entries: 3

Rep: Reputation: 943Reputation: 943Reputation: 943Reputation: 943Reputation: 943Reputation: 943Reputation: 943Reputation: 943
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.

Hope this helps,
 
3 members found this post helpful.
Old 09-16-2011, 04:53 PM   #14
SigTerm
Member
 
Registered: Dec 2009
Distribution: Slackware 12.2
Posts: 379

Rep: Reputation: 233Reputation: 233Reputation: 233
Quote:
Originally Posted by Nominal Animal View Post
Xorshift (pdf)
 
0 members found this post helpful.
Old 09-16-2011, 05:37 PM   #15
Nominal Animal
Senior Member
 
Registered: Dec 2010
Location: Finland
Distribution: Xubuntu, CentOS, LFS
Posts: 1,723
Blog Entries: 3

Rep: Reputation: 943Reputation: 943Reputation: 943Reputation: 943Reputation: 943Reputation: 943Reputation: 943Reputation: 943
Excellent point, SigTerm! Somehow the reference to Xorshift has slipped me by.

To implement Xorshift, replace the first code snippet in my example above with
Code:
#include <stdint.h>

uint32_t random_state[4] = { 123456789, 362436069, 521288629, 88675123 };

static inline uint64_t random_bits(const int bits)
{
	uint64_t        value;
	uint32_t        t;

	if (bits < 1)
		return (uint64_t)0;

	t = random_state[0] ^ (random_state[0] << 11);
	random_state[0] = random_state[1];
	random_state[1] = random_state[2];
	random_state[2] = random_state[3];
	random_state[3] ^= (random_state[3] >> 19) ^ (t ^ (t >> 8));

	if (bits == 32)
		return (uint64_t)random_state[3];
	if (bits < 32)
		return (uint64_t)random_state[3] >> (32 - bits);

	value = ((uint64_t)random_state[3]) << 32;

	t = random_state[0] ^ (random_state[0] << 11);
	random_state[0] = random_state[1];
	random_state[1] = random_state[2];
	random_state[2] = random_state[3];
	random_state[3] ^= (random_state[3] >> 19) ^ (t ^ (t >> 8));

	value |= (uint64_t)random_state[3];

	if (bits < 64)
		value >>= (64 - bits);

	return value;
}
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 05:42 PM.
 
  


Reply

Tags
large, number, random


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
[SOLVED] I need to generate random number either 1 or 0? mvmacd Linux - General 4 01-21-2010 07:50 PM
Generate a random number from a bourne shell script lothario Linux - Software 2 03-02-2007 12:01 AM
How to format a long double number in C++ to display as many digits as possible. TruongAn Programming 4 11-09-2005 11:11 AM
Generate random number with C++ TruongAn Programming 5 11-09-2005 01:01 AM
Python problems trying to generate a random number davholla Programming 0 10-27-2003 05:07 AM


All times are GMT -5. The time now is 03:22 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration