Write an algorithm to generate numbers from 1 to 7 with equal probability using a specified function which produces random numbers between 1 to 5 with equal probability.

Suppose the specified function is `random()` which generates random numbers from `1` to `5` with equal probability. The idea is to use the expression `5*(random() - 1) + random()` which uniformly produces random numbers in range `[1-25]`. So if we exclude the possibility of the random number being one among `[8-25]` by repeating the procedure, we’re left with numbers between `[1-7]` having equivalent probability.

##### How this works?

Since `random()` returns random numbers from `1` to `5` with equal probability, `R = 5*(random() - 1)` can be any of `0, 5, 10, 15` or `20`. Now for the second `random()` call, let’s explore all possibilities:

If `R=0`, `R + random()` can be any of `1, 2, 3, 4, 5`

If `R=5`, `R + random()` can be any of `6, 7, 8, 9, 10`

If `R=10`, `R + random()` can be any of `11, 12, 13, 14, 15`

If `R=15`, `R + random()` can be any of `15, 16, 17, 18, 19, 20`

If `R=20`, `R + random()` can be any of `21, 22, 23, 24, 25`

So the expression uniformly distributes the numbers in range `[1-25]`.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <stdio.h> #include <stdlib.h> #include <time.h> // Function to generate a random number from 1 to 5 with equal probability int random() { return (rand() % 5) + 1; } // Function to generate a random number from 1 to 7 with equal probability // by using the specified function int generate() { int r; do { r = 5 * (random() - 1) + random(); } while (r > 7); return r; } int main(void) { // initialize srand with distinctive value srand(time(NULL)); // count array to validate the results int count[8]; memset(count, 0, sizeof count); // make 1000000 calls to the generate() function and store the results for (int i = 1; i <= 1000000; i++) { int val = generate(); count[val]++; } // print the results for (int i = 1; i <= 7; i++) printf("%d ~ %0.2f%\n", i, count[i]/10000.0); return 0; } |

`Output (will vary): `

1 ~ 14.29%

2 ~ 14.25%

3 ~ 14.33%

4 ~ 14.27%

5 ~ 14.26%

6 ~ 14.31%

7 ~ 14.29%

In order to minimize the number of calls to the `random()` function, we can make the while loop stop at `r <= 21` and use modulo operator as shown below:

1 2 3 4 5 6 7 8 9 10 |
int generate() { int r; do { r = 5 * (random() - 1) + random(); } while (r > 21); return (r % 7) + 1; } |

**Thanks for reading.**

Please use our online compiler to post code in comments. To contribute, get in touch with us.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply