rand in a closed interval on the ints

[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

[Eric Sosman]

Frank Silvermann wrote:

[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

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].

--
Eric Sosman
es*****@acm-dot-org.invalid

[Frank Silvermann]

Eric Sosman wrote:

Frank Silvermann wrote:

[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." [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

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].

#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

[Frank Silvermann]

Eric Sosman wrote:

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].

/* 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

[Michael Mair]

Frank Silvermann schrieb:

Eric Sosman wrote:

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].

/* 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.

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
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[Frank Silvermann]

Michael Mair wrote:

Frank Silvermann schrieb:

Eric Sosman wrote:

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].

/* 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.

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".

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). 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.

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

[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[i]=rand_in_range(0, top_range) + 1;
printf(" q[i]= %d while top_range= %d\n", q[i], top_range);
top_range = top_range - q[i];
}
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

[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[i];
A[i] = 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[i] >= x));
if (i < j) {
temp = A[i];
A[i] = A[j];
A[j] = temp;
} else
return j;
}
}

[Frank Silvermann]

Dann Corbit wrote:

#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[i];
A[i] = 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[i] >= x));
if (i < j) {
temp = A[i];
A[i] = A[j];
A[j] = temp;
} else
return j;
}
}

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

[CBFalconer]

Frank Silvermann wrote:

.... 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

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/>

[Richard Heathfield]

CBFalconer said:

Frank Silvermann wrote:

... 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

It doesn't. However the function does.

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;

}

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)