0

I want to generate a random number in which every higher number has half the probability of its predecessor that is if 1 appears 4 times 2 should appear 2 times and three should appear one time and so on the programming language must be c

int getValue(int min,int max) {
    int i=0;
    while(i==0)
        i=rand()%max;
    int j=0;
    while(j==0) {
        printf("%d",j);
        j=rand()%i;
    }
    return j;
}
Paul Ogilvie
  • 25,048
  • 4
  • 23
  • 41
hariprasath parthasarathy
  • 9
  • 5

3 Answers3

1

Following function may be used:

int prioritizdRand(int min, int max)
{

    int result=min;
    int randNum=rand();
    long int start=RAND_MAX/2;

    while(randNum > start)
    {
        if(result> max )
        {
           return min;
        }
        result++;
        start= (start + RAND_MAX)/2;
    }

    return result;
}
cse
  • 4,066
  • 2
  • 20
  • 37
  • Looks wrong to me... lets assume `prioritizdRand(1, 2)`, then its very likely to hit the `result < max` condition before the `randNum > start` condition. But only the second condition would support the desired value distribution. – grek40 May 29 '17 at 11:27
  • Might be true, but sacrificing correctness in order to ensure termination is a pretty tough deal. A little fine tuning on the involved numbers would probably reach the termination goal. Part of the problem is, that you assign a portion of `1/pow(2, max-min)` from your random number space to results that are not valid. – grek40 May 29 '17 at 18:15
  • The exponent for this portion might be off by one, but as already commented, if you just analyze the `prioritizdRand(1, 2)` it's very clear: `1/2` for `result=1`, `1/4` for `result=2`, `1/4` remaining, which will also lead to `result=2` because of the `result < max` condition. Correct distribution would be `2/3` for `result=1` and `1/3` for `result=2` – grek40 May 30 '17 at 05:48
  • Good change. Still not exact (`3/4` `result=1`, `1/4` `result=2`) but the error is far smaller and it will hardly affect the result for larger numbers. Since a technical application (skip list) was mentioned in the question, this should be fine. – grek40 May 30 '17 at 06:22
1

I'd start by normalizing the requested range (later just add min to the random generated number):

int max_rnd = max - min;

Then generate a equally distributed random number in the range 1 to pow(2, max_rnd+1) - 1

int rnd_limit = (1 << (max_rnd + 1)) - 1;
int rnd = (rand() % rnd_limit) + 1;

Round down the base-2-logarithm of the generated random number. The translation of rnd will follow this pattern:

floor(log2(1)) -> 0
floor(log2(2)) -> 1
floor(log2(3)) -> 1
floor(log2(4)) -> 2
...
floor(log2(7)) -> 2
floor(log2(8)) -> 3
...
floor(log2(15)) -> 3
...

So the distribution of results will be the reverse of the expected (double instead of half for higher numbers) but thats easy to change. Effectively, the floor(log2(rnd)) is computing the position of the highest 1 bit in rnd, so it can be implemented with a bitshift loop:

int log2_rnd = 0;
while ((rnd >> log2_rnd) != 1)
{
    ++log2_rnd;
}

Time for the actual result:

return (max_rnd - log2_rnd) + min;

Not covered here: Accuracy of "equally distributed" numbers generated by rand() (specially in combination with modulo) and upper limit of generated numbers.

grek40
  • 13,113
  • 1
  • 24
  • 50
1

a simplistic idea: start with value one, take a random number, add one to value if random number is odd, bitshift one right, repeat

unsigned randhalf()
{
    unsigned ret = 1;
    int rnd = rand();
    while (rnd&1)
    {
        ++ret;
        rnd >>= 1;
    }
    return ret;
}

Or if upper and lower bounds are required:

int randhalf(int min, int max) // bounds are inclusive
{
    int ret = min;
    int rnd = rand();
    while (rnd&1 && ret<max)
    {
        ++ret;
        rnd >>= 1;
    }
    return ret;
}

This will only provide values that are larger than min by however many bits rand() uses.

sp2danny
  • 7,488
  • 3
  • 31
  • 53