P: n/a

#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  
Share this Question
P: n/a

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*****@acmdotorg.invalid  
P: n/a

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  
P: n/a

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  
P: n/a

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

EMail: Mine is an /at/ gmx /dot/ de address.  
P: n/a

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  
P: n/a

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<(n1); 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[n1]=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 hardcoded 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  
P: n/a

#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 0070131430
*/
/*
** 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);
}
/* CFAQ */
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;
}
}  
P: n/a

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 0070131430 */
/* ** 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); }
/* CFAQ */ 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;
}
/* CFAQ */
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  
P: n/a

Frank Silvermann wrote:
.... snip ... /* CFAQ */ 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/>  
P: n/a

CBFalconer said: Frank Silvermann wrote: ... snip ... /* CFAQ */ 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)   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 1902
 replies: 10
 date asked: Jun 10 '06
