Is it a good solution

Question

mitrious 0 Junior Poster in Training

13 Years Ago

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.

c++

2 Contributors
3 Replies
103 Views
8 Hours Discussion Span
Latest Post 13 Years Ago Latest Post by mitrious

All 3 Replies

mike_2000_17 2,669 21st Century Viking

13 Years Ago

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.

Reply to this topic

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.

mitrious 0 Junior Poster in Training · Answer 1 · 2010-10-26T19:41:16+00:00

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)

mitrious 0 Junior Poster in Training · Answer 2 · 2010-10-26T22:17:38+00:00

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

Is it a good solution

Recommended Answers Collapse Answers

All 3 Replies

Recommended Answers