Here's what the book asked

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.

Here's what the book asked

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

This article has been dead for over six months. Start a new discussion instead.