The implementation of nrand in §7.4.4/135 will not work for arguments greater
than RAND_MAX. Usually, this restriction is no problem, because RAND_MAX is often the
largest possible integer anyway. Nevertheless, there are implementations under which
RAND_MAX is much smaller than the largest possible integer. For example, it is not
uncommon for RAND_MAX to be 32767 (215 -1) and the largest possible integer to be
2147483647 (231 -1). Reimplement nrand so that it works well for all values of n.

here's the original nrand() function:

``````int nrand(int n)
{
if (n <= 0 || n > RAND_MAX)
throw domain_error("Argument to nrand is out of range");
const int bucket_size = RAND_MAX / n;
int r;
do r = rand() / bucket_size;
while (r >= n);
return r;
}``````

here's the solution I created:

``````int nrand(int n)
{
if(n <= 0)
throw domain_error("Argument to nrand is out of range");

int r;

if(n > RAND_MAX){
typedef vector<int> veci;
typedef vector<veci> vecv;

int x = 0;

do ++x;
while(n % x != 0 && n/x > RAND_MAX);

int y = 0, z = n/x;
vecv rec(x);
for(int i = 1; i != x; ++i){
while(y != z){
rec[i -1].push_back(y);
++y;
}
z += z;
}
vecv::size_type v;
do v = rand();
while(v >= rec.size());

veci::size_type rn;
do rn = rand();
while(rn >= rec[v].size());

r = rec[v][rn];

}else{
const int bucket_size = RAND_MAX/n;

do r = rand()/bucket_size;
while(r >= n);
}
return r;
}``````

it should work like: (simulation with small numbers)

if RAND_MAX was 5
and
n = 18
then we'd get
x = 6
and we'd get 6 vectors with
0, 1, 2
3, 4, 5
6, 7, 8
9, 10, 11
12, 13, 14
15, 16, 17
PS: it's to get an element inside a vector so if the size is 18 I need numbers from 0 to 17 (hence why I started with 0 and not 1)

so the program should randomly select and of the numbers from 0 - 17 ... with the same chance of getting any of them.

The implementation of nrand in §7.4.4/135 will not work for arguments greater
than RAND_MAX. Usually, this restriction is no problem, because RAND_MAX is often the
largest possible integer anyway. Nevertheless, there are implementations under which
RAND_MAX is much smaller than the largest possible integer. For example, it is not
uncommon for RAND_MAX to be 32767 (215 -1) and the largest possible integer to be
2147483647 (231 -1). Reimplement nrand so that it works well for all values of n.

here's the original nrand() function:

``````int nrand(int n)
{
if (n <= 0 || n > RAND_MAX)
throw domain_error("Argument to nrand is out of range");
const int bucket_size = RAND_MAX / n;
int r;
do r = rand() / bucket_size;
while (r >= n);
return r;
}``````

here's the solution I created:

``````int nrand(int n)
{
if(n <= 0)
throw domain_error("Argument to nrand is out of range");

int r;

if(n > RAND_MAX){
typedef vector<int> veci;
typedef vector<veci> vecv;

int x = 0;

do ++x;
while(n % x != 0 && n/x > RAND_MAX);

int y = 0, z = n/x;
vecv rec(x);
for(int i = 1; i != x; ++i){
while(y != z){
rec[i -1].push_back(y);
++y;
}
z += z;
}
vecv::size_type v;
do v = rand();
while(v >= rec.size());

veci::size_type rn;
do rn = rand();
while(rn >= rec[v].size());

r = rec[v][rn];

}else{
const int bucket_size = RAND_MAX/n;

do r = rand()/bucket_size;
while(r >= n);
}
return r;
}``````

it should work like: (simulation with small numbers)

if RAND_MAX was 5
and
n = 18
then we'd get
x = 6
and we'd get 6 vectors with
0, 1, 2
3, 4, 5
6, 7, 8
9, 10, 11
12, 13, 14
15, 16, 17
PS: it's to get an element inside a vector so if the size is 18 I need numbers from 0 to 17 (hence why I started with 0 and not 1)

so the program should randomly select and of the numbers from 0 - 17 ... with the same chance of getting any of them.

in the example above it would work cuz the numbers of the 6 vectors would be between 0 and 5 ... but if x was like 7 it wouldn't have worked ... that's the only problem I have found for this solution =S (anyone find any other problems? I'm trying to solve this one)

The first thing you need to observe is "complexity". Intuitively, finding a random number between [0,n] shouldn't be much more complex whether n is smaller or greater than RAND_MAX. So, just a first look at your implementation reveals that something is wrong if the code is so much larger than the previous version and uses a bunch of temporary vectors too. Pay a little bit of attention to the "expected" complexity and you can know right away if your implementation is effective.

Now, let me give a few inline comments:

``````int nrand(int n)
{
if(n <= 0)
throw domain_error("Argument to nrand is out of range");

int r;

if(n > RAND_MAX){
typedef vector<int> veci;
typedef vector<veci> vecv;

int x = 0;

do { //put the curly braces here, don't make it too easy to get an infinite loop.
++x;
} while(n % x != 0 && n/x > RAND_MAX);
//I think the above condition is too easy to meet! this will stop at first iteration because n % x == 0 for x==1, always.

int y = 0, z = n/x; //please use more intuitive names then "x", "y", "n" and "z"
vecv rec(x);
for(int i = 0; i < x; ++i) { //use the usual bounds, the one you had was not correct anyways (it skipped the last element).
while(y != z) {
rec[i].push_back(y); //do you really want to create a vector of size n, which could be 2147483647 (i.e. 8.5 GB on a 32bit computer!)
++y;
}
z += z; //????????
}
vecv::size_type v;
do {
v = rand();
} while(v >= rec.size());

veci::size_type rn;
do {
rn = rand();
} while(rn >= rec[v].size());

r = rec[v][rn];

}else{
const int bucket_size = RAND_MAX/n;

do {
r = rand()/bucket_size;
} while(r >= n);
}
return r;
}``````

I highly recommend doing it recursively, like this:

``````int nrand(int n)
{
if(n <= 0)
throw domain_error("Argument to nrand is out of range");

int r;

if(n > RAND_MAX){
return nrand(n % RAND_MAX) + RAND_MAX * nrand(n / RAND_MAX);
}else{
const int bucket_size = RAND_MAX/n;

do {
r = rand()/bucket_size;
} while(r >= n);
}
return r;
}``````

Isn't that simpler? And, as expected, the complexity of nrand for n being higher or smaller than RAND_MAX is about the same.

The first thing you need to observe is "complexity". Intuitively, finding a random number between [0,n] shouldn't be much more complex whether n is smaller or greater than RAND_MAX. So, just a first look at your implementation reveals that something is wrong if the code is so much larger than the previous version and uses a bunch of temporary vectors too. Pay a little bit of attention to the "expected" complexity and you can know right away if your implementation is effective.

Now, let me give a few inline comments:

``````int nrand(int n)
{
if(n <= 0)
throw domain_error("Argument to nrand is out of range");

int r;

if(n > RAND_MAX){
typedef vector<int> veci;
typedef vector<veci> vecv;

int x = 0;

do { //put the curly braces here, don't make it too easy to get an infinite loop.
++x;
} while(n % x != 0 && n/x > RAND_MAX);
//I think the above condition is too easy to meet! this will stop at first iteration because n % x == 0 for x==1, always.

int y = 0, z = n/x; //please use more intuitive names then "x", "y", "n" and "z"
vecv rec(x);
for(int i = 0; i < x; ++i) { //use the usual bounds, the one you had was not correct anyways (it skipped the last element).
while(y != z) {
rec[i].push_back(y); //do you really want to create a vector of size n, which could be 2147483647 (i.e. 8.5 GB on a 32bit computer!)
++y;
}
z += z; //????????
}
vecv::size_type v;
do {
v = rand();
} while(v >= rec.size());

veci::size_type rn;
do {
rn = rand();
} while(rn >= rec[v].size());

r = rec[v][rn];

}else{
const int bucket_size = RAND_MAX/n;

do {
r = rand()/bucket_size;
} while(r >= n);
}
return r;
}``````

I highly recommend doing it recursively, like this:

``````int nrand(int n)
{
if(n <= 0)
throw domain_error("Argument to nrand is out of range");

int r;

if(n > RAND_MAX){
return nrand(n % RAND_MAX) + RAND_MAX * nrand(n / RAND_MAX);
}else{
const int bucket_size = RAND_MAX/n;

do {
r = rand()/bucket_size;
} while(r >= n);
}
return r;
}``````

Isn't that simpler? And, as expected, the complexity of nrand for n being higher or smaller than RAND_MAX is about the same.

Thx ... yeah ... I thought it was way to complex =S ... thx dude ... I understood what you did there ...

It was very helpful ... and thx for the notes ... I'll pay attention to this stuff next time ... thx

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.