2
\$\begingroup\$

A function random_int_with_probability that returns a random number within a range, where the chance to get a bigger value decreases linearly towards the maxima. In the example below, the chance decreases by 10%, meaning to you will have guaranteed 100% chance to at least get 1, then have 90% to get 2, 3 at 80% and so on. Of course to get an exact number the probability has to be calculated using the rectangular distribution formula (correct me if I am wrong).

As an optimization I would be happy to actually use a mathematical expression instead of the loop.

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

int random_int (int minValue, int maxValue)
{
    return minValue + (int)rand() % (maxValue - minValue);
}

int random_bool_with_probability (double percentage)
{
    return ((rand() % 100) <= percentage);
}

int random_int_with_probability (int minValue, int maxValue, int progressionIncrement)
{
    int pi = 100;
    double mi = 0;
 
    for(mi = minValue; mi <= maxValue; mi++)
    {
        int p = random_bool_with_probability(pi);
 
        if(p == 0)
            break;
 
        pi -= progressionIncrement;
    }
 
    return random_int(minValue, mi);
}

/* Test */
int main (void)
{
    int counter = 0;

    srand(time(NULL));

    while(counter < INT_MAX-1)
    {
        int stat = random_int_with_probability(1, 10, 10);

        counter++;

        if(stat >= 9)
            break;
    }

    printf("You pulled out the maximum value of 9 at attempt %i\n", counter);

    return 0;
}
\$\endgroup\$
2
  • \$\begingroup\$ Am I wrong to think that random_int_with_probability(1, 10, 10) is just uniform probability? \$\endgroup\$
    – slepic
    Commented Nov 30, 2022 at 4:37
  • \$\begingroup\$ @slepic In this case, it appears so, but I am not an expert. \$\endgroup\$
    – Edenia
    Commented Nov 30, 2022 at 4:58

2 Answers 2

2
\$\begingroup\$

Code doesn't match description

The explanation corresponds to a uniform distribution (except that the last value may have lower likelihood (if pi reaches or crosses zero) or higher likelihood (if pi never reaches zero)). But that's not the distribution we get:

#include <stdio.h>
#include <string.h>
int main (void)
{
    const size_t max = 10;
    size_t counter[max];

    srand((unsigned)time(NULL));

    memset(counter, 0, sizeof counter);
    for (int i = 0;  i < 1000000;  ++i) {
        ++counter[random_int_with_probability(1, (int)max, 100/(int)max)];
    }

    for (size_t i = 0;  i < max;  ++i) {
        printf("%2zu: %zu\n", i, counter[i]);
    }
}
 0: 0
 1: 355444
 2: 264735
 3: 178902
 4: 107455
 5: 56304
 6: 25059
 7: 9051
 8: 2500
 9: 493

If you can clearly express the probability density function that's required, then we should be able to generate a single random number and algorithmically transform that into the output range, with no loops or extra randomness.


Pedantry around random numbers

The rand() function generates numbers uniformly distributed in [0, RAND_MAX]. If we simply reduce to a range of size n using %, we'll get a slightly skewed distribution unless n is a factor of RAND_MAX + 1. Normal practice is to generate a new random number if the first attempt yields a number less than RAND_MAX % n + 1, so that we still have uniform distribution. This effect becomes more significant as n gets larger.


Compiler warnings

Compiling with gcc -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds -Wconversion -Wstrict-prototypes -fanalyzer reveals that

  • mi should probably be an integer
  • We need to include <limits.h>
\$\endgroup\$
2
  • \$\begingroup\$ Style: I find it interesting folks who code C++ well using ++counter[...] and not counter[...]++ in C.. Perhaps it should have been called ++C? 😉 \$\endgroup\$ Commented Nov 30, 2022 at 11:53
  • 1
    \$\begingroup\$ ++C is the language for those who care a lot about performance. \$\endgroup\$ Commented Nov 30, 2022 at 12:00
3
\$\begingroup\$

OP has not posted a review goal. Perhaps add a clear goal.

Below are some observations.


Off by 1

random_int(1, 10) generates one of 9 values. Given maxValue, minValue, I'd expect 10. If maxValue was meant to be the maximum possible value plus 1, use another name.
(int) not needed - no need to cast an int to an int.

int random_int (int minValue, int maxValue) {
  // return minValue + (int)rand() % (maxValue - minValue);
  return minValue + rand() % (maxValue - minValue + 1);
}

Code still has problems when maxValue - minValue >= RAND_MAX. RAND_MAX may be as small as 32767. Solution not shown.

()

Outside () not needed. () around rand() % 100 not needed either, but reasonable to leave those.

// return ((rand() % 100) <= percentage);
return (rand() % 100) <= percentage;

Why double?

Only integer objects needed.

int pi = 100;
...
  int p = random_bool_with_probability(pi);

// int random_bool_with_probability (double percentage)
int random_bool_with_probability (int percentage)

If code really wants a double, then return ((rand() % 100) <= percentage); needs rework to properly handle calls like random_bool_with_probability(100.0/3.0).

Random bool?

random_bool_with_probability() returns an int. Given the name, bool makes more sense.

// int random_bool_with_probability (double percentage)
bool random_bool_with_probability (double percentage)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.