Random Number Generation with Equal Probability

From Software Engineers Wiki
Jump to: navigation, search

You have a function f1() that generates 0 or 1 with the equal probability. Write a function f200() that generates a number between 1 and 200 with equal probability.

Answer 1

Generate the random number between 0 and 255. If the generated random number is in [1..200], return the number. Otherwise re-generate the number. Since ecause f1() can either generate 0 or 1, we can only generate random number in equal probability in range of [1..2^n].

int f200(void)
{
        int result;

        do {
                /* generate a random number between 0 - 255 */
                result = (f1() << 7) | (f1() << 6) | (f1() << 5) | (f1() << 4) | (f1() << 3) | (f1() << 2) | (f1() << 1) | f1();
        } while (result < 1 || result > 200);

        return result;
}

To verify the logic.

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

void f1_init(void)
{
        srandom(time(NULL));
}

int f1(void)
{
        return random() & 1;
}

int main(void)
{
        const int max_random = 200;
        const int max_tries = (max_random) * 100;

        int i;
        int counts[max_random];

        f1_init();
        memset(counts, 0, sizeof counts);

        for (i = 0; i < max_tries; ++i)
                ++counts[f200() - 1];

        for (i = 0; i < max_random; ++i)
                printf("%3d: %d (%f%%)\n", i + 1, counts[i], (float) (counts[i] * 100) / max_tries);

        return 0;
}

Reference

Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox