rand in a closed interval on the ints

F

Frank Silvermann

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>





#define MIN_WORD_LENGTH 9
#define MAX_WORD_LENGTH 15
#define SWAP(m, n) (tmp = (m), (m) = (n), (n) = tmp)



void permute(char *, int);
int * partition(int, int);
int rand_in_range(int, int, int);

int main(void)
{
char p[] = "abcdefghijklmnopqrstuvwxyz";
char q[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
char r[] = "0123456789";
int a[3], m, tja,i ,j;
/* all declarations in main need to be north of here */

a[0] = sizeof (p) - 1;
a[1] = sizeof (q) - 1;
a[2] = sizeof (r) - 1;
/* calculate size of alphabet */
m = 26 + 26 + 10;
printf("tja %d %d %d %d \n", a[0], a[1], a[2], m);
/* seed timer */
srand(time(NULL));
/* call rand with hard code */
tja = rand_in_range(3, 7, 7);
printf("tja is %d\n", tja);
/* call rand 10 thousand times */
j = 0;
for (i=0; i < 10000; i++)
{

tja = rand_in_range(3, 7, 7);
j += tja;
}
printf("j is %d\n", j);

return 0;
}


void permute(char *m , int n)
{ ; }
int * partition(int m, int n)
{ ;
return NULL;
}
int rand_in_range(int m, int n, int o)
{
/*seed srand in main */
/* [m, n] is range */
int t, top, diff;
diff = n - m;
o=0*(int)("ace in \0");
top = RAND_MAX - (RAND_MAX % diff);

/* control */
do t = rand(); while (t > top);
o = t % (diff + 1);
return o;
}
/* end source */
I believe this gives a pseudo random in a closed interval with a flat
p.d.f. . Does it look right, besides having some extraneous source? frank
 
E

Eric Sosman

Frank said:
[I've snipped away the 95% of the code that the original
> post called "extraneous source." It's a puzzlement why
> the original poster, knowing that it was extraneous,
> didn't snip it himself. Maybe next time he'll post a
> question about three lines of code, and embed it in the
> complete text of "Ulysses."
>
int rand_in_range(int m, int n, int o)
{
/*seed srand in main */
/* [m, n] is range */
int t, top, diff;
diff = n - m;
o=0*(int)("ace in \0");
top = RAND_MAX - (RAND_MAX % diff);

/* control */
do t = rand(); while (t > top);
o = t % (diff + 1);
return o;
}
/* end source */
I believe this gives a pseudo random in a closed interval with a flat
p.d.f. . Does it look right, besides having some extraneous source? frank
Click to expand...

No, it does not look right -- and in this case, looks
are not deceiving. Quite aside from the useless third
argument and the silly dabbling with a useless pointer,
the function is wrong. For example, consider what happens
if it is asked for a value in [42,42].
 
F

Frank Silvermann

Eric said:
Frank said:
[I've snipped away the 95% of the code that the original
post called "extraneous source." It's a puzzlement why
the original poster, knowing that it was extraneous,
didn't snip it himself. Maybe next time he'll post a
question about three lines of code, and embed it in the
complete text of "Ulysses."
Click to expand...
Click to expand...
[snipped away the other 95 percent]
It was hard for me to determine what was relevant. Although I didn't
use the SWAP macro for on the original post, I was glad to have it
around to deal with the expected and unmathematical objection that they
be reversed.
I believe this gives a pseudo random in a closed interval with a flat
p.d.f. . Does it look right, besides having some extraneous source?
frank
Click to expand...

No, it does not look right -- and in this case, looks
are not deceiving. Quite aside from the useless third
argument and the silly dabbling with a useless pointer,
the function is wrong. For example, consider what happens
if it is asked for a value in [42,42].
Click to expand...

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>


#define SWAP(m, n) (tmp = (m), (m) = (n), (n) = tmp)
#define ITERATIONS 100


int rand_in_range(int, int);

int main(void)
{
int tja, i , j, tmp, m, n;
float mu;
/* all declarations in main need to be north of here */

/* seed timer */
srand(time(NULL));

/* call rand */
j = 0;
m = 40;
n = 3;

if (m > n) SWAP(m, n);
printf("range is [%d, %d]\n", m, n);
mu = (float)ITERATIONS *((float)m +(float)(m - n) /(float)2);
printf("mu is %f\n", mu);
for (i=0; i < ITERATIONS; i++)
{
tja = rand_in_range(m, n);
if (i < 10) printf("return is %d\n", tja);
j += tja;
}
printf("j is %d\n", j);

return 0;
}



int rand_in_range(int m, int n)
{
/*seed srand in main */
/* [m, n] is range */
int t, top, diff, o, tmp;
if (m == n) return m;
if (m > n) SWAP(m, n);
diff = n - m;

top = RAND_MAX - (RAND_MAX % diff);


/* control */
do t = rand(); while (t > top);
o = t % (diff + 1) ;
o = o + m;
return o;
}
/* end source */
I think this is getting closer. The mu fiasco shows why it's sometimes
hard to trim out of a function on the fly. If ITERATIONS is a positive
power of ten, then the expected value is going to be the average of the
two inputs with the decimal point moved. frank
 
F

Frank Silvermann

Eric said:
Frank said:
[I've snipped away the 95% of the code that the original [snip]
I believe this gives a pseudo random in a closed interval with a flat
p.d.f. . Does it look right, besides having some extraneous source?
frank
Click to expand...

No, it does not look right -- and in this case, looks
are not deceiving. Quite aside from the useless third
argument and the silly dabbling with a useless pointer,
the function is wrong. For example, consider what happens
if it is asked for a value in [42,42].
Click to expand...

/* rand_in_range.c : contributors: usual suspects in clc */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define SWAP(m, n) (tmp = (m), (m) = (n), (n) = tmp)
#define ITERATIONS 100

int rand_in_range(int, int);

int main(void)
{
int tja, i , j, m, n;
/* all declarations in main need to be north of here */
/* seed timer */
srand(time(NULL));
/* call rand and count returns */
j = 0;
m = 8;
n = 3;
printf("range is [%d, %d]\n", m, n);
for (i=0; i < ITERATIONS; i++)
{
tja = rand_in_range(m, n);
if (i < 10) printf("return is %d\n", tja);
j += tja;
}
printf("total is %d\n", j);
return 0;
}

int rand_in_range(int m, int n)
{
/*seed srand in main */
/* [m, n] is range */
int t, top, diff, p, tmp;
if (m == n) return m;
if (m > n) SWAP(m, n);
diff = n - m;
top = RAND_MAX - (RAND_MAX % (diff + 1) + 1);

/* control */
do t = rand(); while (t > top);
p = t % (diff + 1) ;
p = p + m;
return p;
}
/* end source */
I think this is right. frank
 
M

Michael Mair

Frank said:
Eric said:
Frank said:
[I've snipped away the 95% of the code that the original
Click to expand...
[snip]
I believe this gives a pseudo random in a closed interval with a flat
p.d.f. . Does it look right, besides having some extraneous source?
frank
Click to expand...


No, it does not look right -- and in this case, looks
are not deceiving. Quite aside from the useless third
argument and the silly dabbling with a useless pointer,
the function is wrong. For example, consider what happens
if it is asked for a value in [42,42].
Click to expand...

/* rand_in_range.c : contributors: usual suspects in clc */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define SWAP(m, n) (tmp = (m), (m) = (n), (n) = tmp)
#define ITERATIONS 100

int rand_in_range(int, int);

int main(void)
{
int tja, i , j, m, n;
/* all declarations in main need to be north of here */
/* seed timer */
srand(time(NULL));
/* call rand and count returns */
j = 0;
m = 8;
n = 3;
printf("range is [%d, %d]\n", m, n);
for (i=0; i < ITERATIONS; i++)
{
tja = rand_in_range(m, n);
if (i < 10) printf("return is %d\n", tja);
j += tja;
}
printf("total is %d\n", j);
return 0;
}

int rand_in_range(int m, int n)
{
/*seed srand in main */
/* [m, n] is range */
int t, top, diff, p, tmp;
if (m == n) return m;
if (m > n) SWAP(m, n);
diff = n - m;
top = RAND_MAX - (RAND_MAX % (diff + 1) + 1);

/* control */
do t = rand(); while (t > top);
p = t % (diff + 1) ;
p = p + m;
return p;
}
/* end source */
I think this is right.
Click to expand...

It looks right -- had you formatted the code in a more
readable manner, this would have been easier.
Three remarks:
1) You are "admitting" that your implementation is based on
rand().
I'd rather use an
void init_rand_in_range (long seed);
function from the start -- even if it only wraps srand(), this
will make it easier if you ever want to use another pseudorandom
number generator -- just "compile and link" instead of "replace
all srand() calls in every bit of code by an init....() call".
2) In older rand() implementations, there often were problems
with the modulo approach as you got shorter cycle lengths
than for the division approach (see below).
3) Be verbose:
int rand_in_range(int m, int n)
{
/*seed srand in main */
/* [m, n] is range */
int roll_again_threshold, divisor, result;
int offset = m;
int num_results = n - m + 1;

if (num_results == 1) {
return m;
}
if (num_results <= 0) {
num_results = m - n + 1;
offset = n;
}

roll_again_threshold = RAND_MAX - RAND_MAX%num_results;
divisor = roll_again_threshold/num_results;

do {
result = rand();
} while (result >= roll_again_threshold);
result /= divisor;
return offset + result;
}

This is exaggerated but IMO more helpful than your code:
Why say "diff + 1" if you mean the number of results?
Or t and p? top vs roll_again_threshold is mostly a matter
of taste -- the latter offers itself for the division.


Cheers
Michael
 
F

Frank Silvermann

Michael said:
Frank said:
Eric said:
Frank Silvermann wrote:

[I've snipped away the 95% of the code that the original
[snip]

I believe this gives a pseudo random in a closed interval with a
flat p.d.f. . Does it look right, besides having some extraneous
source? frank


No, it does not look right -- and in this case, looks
are not deceiving. Quite aside from the useless third
argument and the silly dabbling with a useless pointer,
the function is wrong. For example, consider what happens
if it is asked for a value in [42,42].
Click to expand...

/* rand_in_range.c : contributors: usual suspects in clc */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define SWAP(m, n) (tmp = (m), (m) = (n), (n) = tmp)
#define ITERATIONS 100

int rand_in_range(int, int);

int main(void)
{
int tja, i , j, m, n;
/* all declarations in main need to be north of here */
/* seed timer */
srand(time(NULL));
/* call rand and count returns */
j = 0;
m = 8;
n = 3;
printf("range is [%d, %d]\n", m, n);
for (i=0; i < ITERATIONS; i++)
{
tja = rand_in_range(m, n);
if (i < 10) printf("return is %d\n", tja);
j += tja;
}
printf("total is %d\n", j);
return 0;
}

int rand_in_range(int m, int n)
{
/*seed srand in main */
/* [m, n] is range */
int t, top, diff, p, tmp;
if (m == n) return m;
if (m > n) SWAP(m, n);
diff = n - m;
top = RAND_MAX - (RAND_MAX % (diff + 1) + 1);

/* control */
do t = rand(); while (t > top);
p = t % (diff + 1) ;
p = p + m;
return p;
}
/* end source */
I think this is right.
Click to expand...

It looks right -- had you formatted the code in a more
readable manner, this would have been easier.
Three remarks:
1) You are "admitting" that your implementation is based on
rand().
I'd rather use an
void init_rand_in_range (long seed);
function from the start -- even if it only wraps srand(), this
will make it easier if you ever want to use another pseudorandom
number generator -- just "compile and link" instead of "replace
all srand() calls in every bit of code by an init....() call".
Click to expand...
That's where I'm headed with this, but I need to stay in the shallows
for a little longer.
2) In older rand() implementations, there often were problems
with the modulo approach as you got shorter cycle lengths
than for the division approach (see below).
Click to expand...
I had forgotten that C was going to give me modulo without trying so hard.
3) Be verbose:
int rand_in_range(int m, int n)
{
/*seed srand in main */
/* [m, n] is range */
int roll_again_threshold, divisor, result;
int offset = m;
int num_results = n - m + 1;

if (num_results == 1) {
return m;
}
if (num_results <= 0) {
num_results = m - n + 1;
offset = n;
}

roll_again_threshold = RAND_MAX - RAND_MAX%num_results;
divisor = roll_again_threshold/num_results;

do {
result = rand();
} while (result >= roll_again_threshold);
result /= divisor;
return offset + result;
}

This is exaggerated but IMO more helpful than your code:
Why say "diff + 1" if you mean the number of results?
Or t and p? top vs roll_again_threshold is mostly a matter
of taste -- the latter offers itself for the division.
Click to expand...
This looks right on the nuts to me. I could, for this function's sake,
now sack the SWAP macro. You probably skimmed right past it, but given
that I'm going to need it elsewhere, I might as well use it. Your
roll_again_threshold versus my top is a subtle comparison. At first
they appear different but your while condition allows one more or less
than mine. roll_again_threshold must be right (modulo num_results) else
cases will not be equiprobable. At this point, I believe we are both
within two of the correct value. gruss, frank
 
F

Frank Silvermann

Michael Mair wrote:
[snip, see upthread]

/* partition1.c */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#define SWAP(m, n) (tmp = (m), (m) = (n), (n) = tmp)

int rand_in_range(int, int);
int * partition(int, int);

int main(void)
{
int m=8, n=3;
int *p;
/* all declarations in main need to be north of here */
/* seed timer */
srand(time(NULL));
/* call partition and examine returns */
p = malloc((n)*sizeof(int));

printf("set has %d elements and %d partitions\n", m, n);

p = partition(m,n);
printf("m in n chunks: %d %d %d\n", p[0], p[1], p[2]);
return 0;
}

int rand_in_range(int m, int n)
{
/*seed srand in main */
/* [m, n] is range */
int roll_again_threshold, divisor, result,

tmp, offset, num_results;

if (m>n) SWAP(m, n);
offset = m;
num_results = n - m + 1;

if (num_results == 1) {
return m;
}


roll_again_threshold = RAND_MAX -

RAND_MAX%num_results;
divisor = roll_again_threshold/num_results;

do {
result = rand();
} while (result >= roll_again_threshold);
result /= divisor;
return offset + result;
}

int * partition(int m, int n)
{
int top_range, i;
int *q;
/* end declarations */
/* if n>m bomb out */
if (n > m) return NULL;
top_range = m - n;
q = malloc((n)*sizeof(int));
for (i=0; i<(n-1); i++)
{
q=rand_in_range(0, top_range) + 1;
printf(" q= %d while top_range= %d\n", q, top_range);
top_range = top_range - q;
}
q[n-1]=top_range + 1;
return q;
}
/* end source */
I'm at my wit's end to write this function that would give a random
partition. At this point, the number of partitions is hard-coded at
three. The 3 returned values with q don't even add to the number of
elements in the set, so I'm in trouble. There will, I think, be further
trouble with their order. It seems to be a recurring theme, in
particular in TAOCP, that the best way to implement random behavior is
to do it at every step along the way. The mallocs look right to me.
Grateful for any hints. frank
 
D

Dann Corbit

#include <stdlib.h>
typedef double Etype; /* season to taste */

extern Etype RandomSelect(Etype * A, size_t p, size_t r, size_t i);
extern size_t RandRange(size_t a, size_t b);
extern size_t RandomPartition(Etype * A, size_t p, size_t r);
extern size_t Partition(Etype * A, size_t p, size_t r);

/*
**
** In the following code, every reference to CLR means:
**
** "Introduction to Algorithms"
** By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
** ISBN 0-07-013143-0
*/


/*
** CLR, page 187
*/
Etype RandomSelect(Etype A[], size_t p, size_t r, size_t i)
{
size_t q,
k;
if (p == r)
return A[p];
q = RandomPartition(A, p, r);
k = q - p + 1;

if (i <= k)
return RandomSelect(A, p, q, i);
else
return RandomSelect(A, q + 1, r, i - k);
}

/* C-FAQ */
size_t RandRange(size_t a, size_t b)
{
size_t c = (size_t) ((double) rand() / ((double) RAND_MAX + 1)
* (b - a));
return c + a;
}

/*
** CLR, page 162
*/
size_t RandomPartition(Etype A[], size_t p, size_t r)
{
size_t i = RandRange(p, r);
Etype Temp;
Temp = A[p];
A[p] = A;
A = Temp;
return Partition(A, p, r);
}

/*
** CLR, page 154
*/
size_t Partition(Etype A[], size_t p, size_t r)
{
Etype x,
temp;
size_t i,
j;

x = A[p];
i = p - 1;
j = r + 1;

for (;;) {
do {
j--;
} while (!(A[j] <= x));
do {
i++;
} while (!(A >= x));
if (i < j) {
temp = A;
A = A[j];
A[j] = temp;
} else
return j;
}
}
 
F

Frank Silvermann

Dann said:
#include <stdlib.h>
typedef double Etype; /* season to taste */

extern Etype RandomSelect(Etype * A, size_t p, size_t r, size_t i);
extern size_t RandRange(size_t a, size_t b);
extern size_t RandomPartition(Etype * A, size_t p, size_t r);
extern size_t Partition(Etype * A, size_t p, size_t r);

/*
**
** In the following code, every reference to CLR means:
**
** "Introduction to Algorithms"
** By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
** ISBN 0-07-013143-0
*/


/*
** CLR, page 187
*/
Etype RandomSelect(Etype A[], size_t p, size_t r, size_t i)
{
size_t q,
k;
if (p == r)
return A[p];
q = RandomPartition(A, p, r);
k = q - p + 1;

if (i <= k)
return RandomSelect(A, p, q, i);
else
return RandomSelect(A, q + 1, r, i - k);
}

/* C-FAQ */
size_t RandRange(size_t a, size_t b)
{
size_t c = (size_t) ((double) rand() / ((double) RAND_MAX + 1)
* (b - a));
return c + a;
}

/*
** CLR, page 162
*/
size_t RandomPartition(Etype A[], size_t p, size_t r)
{
size_t i = RandRange(p, r);
Etype Temp;
Temp = A[p];
A[p] = A;
A = Temp;
return Partition(A, p, r);
}

/*
** CLR, page 154
*/
size_t Partition(Etype A[], size_t p, size_t r)
{
Etype x,
temp;
size_t i,
j;

x = A[p];
i = p - 1;
j = r + 1;

for (;;) {
do {
j--;
} while (!(A[j] <= x));
do {
i++;
} while (!(A >= x));
if (i < j) {
temp = A;
A = A[j];
A[j] = temp;
} else
return j;
}
}
Click to expand...

Gosh, this opens up a whole new set of problems for me. In stddef.h for
me I have:
/* define the implementation dependent size types */

#ifndef _SIZE_T_DEFINED
typedef unsigned int size_t;
#define _SIZE_T_DEFINED
#endif

,so I would think that making these calls with unsigned ints would be
alright, but when I tried to do this with RandRange, my return is the
same every time I run the resulting executable:
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
extern size_t RandRange(size_t a, size_t b);

/* attribution: CLR */

int main(void)
{

unsigned int a, b, c;
srand(time(NULL));
a = 40;
b = 90;
c = RandRange( a, b);

printf("return is %u\n", c);
return 0;
}



/* C-FAQ */
size_t RandRange(size_t a, size_t b)
{
size_t c = (size_t) ((double) rand() / ((double) RAND_MAX
+ 1)
* (b - a));
return c + a;
}
/* end source */
Furthermore, I don't see how the RHS of the assignment to c would give
you a number between 'a' and 'b'. To make matters worse, I was unable
to find enlightenment in the FAQs. I appreciate your help, but I'm
still sunk. frank
 
C

CBFalconer

Frank said:
.... snip ...

/* C-FAQ */
size_t RandRange(size_t a, size_t b)
{
size_t c = (size_t) ((double) rand() / ((double) RAND_MAX + 1) * (b - a));
return c + a;
}
/* end source */
Furthermore, I don't see how the RHS of the assignment to c would give
you a number between 'a' and 'b'. To make matters worse, I was unable
to find enlightenment in the FAQs. I appreciate your help, but I'm
still sunk. frank
Click to expand...

It doesn't. However the function does.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>
 
R

Richard Heathfield

CBFalconer said:
It doesn't. However the function does.
Click to expand...

Only if b is greater than or equal to a, and provided you don't want b to be
an allowable result unless it is 0.

And why all those casts? And why the lousy names a and b?

Here's a version which eschews the casts, fixes the names, and sorts out the
problem of the parameters being in an inconvenient order.

#include <stdlib.h>
size_t RandRange(size_t low, size_t high)
{
if(low > high)
{
size_t t = low; low = high; high = t;
}
return (high - low + 1) * (rand() / (RAND_MAX + 1.0) + low;

}
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

How do you guys limit rand() results to a range? 133
Fibonacci 0
Need help in debugging tic tac toe (Beginner) 0
filling array with rand numbers 41
Need help in debugging tic tac toe (beginner) 2
Could you fix my code please? (i get no output after inputing the number) 1
Adding adressing of IPv6 to program 1
How to fix this code? 1

Members online

No members online now.
Total: 31 (members: 1, guests: 30)
Robots: 449

Forum statistics

Threads
473,769
Messages
2,569,580
Members
45,055
Latest member
SlimSparkKetoACVReview

Latest Threads

Top