435,482 Members | 3,157 Online
Need help? Post your question and get tips & solutions from a community of 435,482 IT Pros & Developers. It's quick & easy.

# rand in a closed interval on the ints

 P: n/a #include #include #include #include #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 Jun 10 '06 #1
10 Replies

 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*****@acm-dot-org.invalid Jun 10 '06 #2

 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 #include #include #include #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 Jun 10 '06 #3

 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 #include #include #include #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 Jun 10 '06 #4

 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 #include #include #include #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. Jun 10 '06 #5

 P: n/a Michael Mair wrote: [snip, see upthread] /* partition1.c */ #include #include #include #include #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 Jun 12 '06 #7

 P: n/a #include 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; } } Jun 12 '06 #8

 P: n/a Dann Corbit wrote: #include 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 #include #include 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 Jun 12 '06 #9

 P: n/a 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: Also see Jun 13 '06 #10

 P: n/a 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 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) Jun 13 '06 #11

### This discussion thread is closed

Replies have been disabled for this discussion.