Efficient algorithm for counting frequency of a numbers in intervals

Question

I need to build a bar graph that illustrate a distribution of pseudorandom numbers that determined by linear congruential method

$$X_n+1 = (a X_n + c) \mod m$$ $$U = X/m$$

on the interval [0,1]

For example:

Interval           Frequency     
[0;0,1]            0,05
[0,1;0,2]          0,15
[0,2;0,3]          0,1
[0,3;0,4]          0,12
[0,4;0,5]          0,1
[0,5;0,6]          0,15
[0,6;0,7]          0,05
[0,7;0,8]          0,08
[0,8;0,9]          0,16
[0,9;1,0]          0,4

I used such a method:

float mas[10] = {0,0,0,0,0,0,0,0,0,0};
void metod1()
{
    int x=-2, m=437, a=33, c=61;
    float u;
    for(int i=0;i<m;i++){
        x=(a*x + c) % m;
        u=(float)x/(float)m;
        int r;
        r = ceil(u*10);
        mas[r] = mas[r] + 1;
    }
    for(i=0;i<10;i++) cout<<"["<<(float)i/10<<";"<<(float)(i+1)/10<<"]"<<" | "<<mas[i]<<"\n-----------------"<<endl;
    return;
}

If you know another efficient algorithm for this problem, that isn't straightforward, I would appreciate it.

Answer 1

In addition to @Edward's great analysis, I'd add this: name your variables appropriately! What are x, m, a, c, u, and r?

It looks like m is the number of random numbers to generate. So why not name it numRands or something like that? (Or if you prefer a different style, call it num_rands.)

It looks like x is some sort of state for the generator - initially the seed, then the current state after that. Perhaps naming it seed or state could help?

a and c seem to be a scale and add term, so perhaps they could be named scale and offset or something like that? (At the very least, a comment explaining how they work would be a good idea.)

u is the random value converted to a float between -1 and 1, and is the final value you're trying to calculate. It could be called randomVal or result, or something like that.

And finally, r appears to be which bin the numbers will end up in. Name it bin.

Edit: As @DarrelHoffman points out, the name of the function could be greatly improved, too. I agree with his suggestion of countFrequency() or something similar.

And while we're on the subject, this could be made more object-oriented, too. The state and method of calculation of the random number generator shouldn't really be known or accessible to other classes or code. That way, if you decide you want to change it to a better method in the future, you can keep the interface, but replace the inner workings and any code that calls it should just work.

You could make a RandGen class that looks something like this:

class RandGen {
public:
    RandGen(const long seed, const unsigned long maxNumRands) : state(seed), maxRands(maxNumRands) {}
    float getNextRand();

private:
    long    state = -2;
    unsigned long maxRands   = 1000;
};

float RandGen::getNextRand()
{
    const long  scale   = 33;
    const long  offset  = 61;
    state   = (state * scale + offset) % maxRands;
    return (float)state / (float)maxRands;
}

Then your frequency counting function could just call getNextRand(), something like this:

void countFrequency(float frequencies[], const unsigned long numFrequencies,
                    const unsigned long numRands)
{
    RandGen randGen(-2, numRands);
    for (int i = 0; i < numRands; ++i)
    {
        int r = randGen.getNextRand() * 10.0;
        frequencies [ r ] += 1;
    }
}

It would be a good idea to separate out the printing of the frequencies, too:

void printFrequency(float frequencies[], const unsigned long numFrequencies)
{
    for (int i = 0; i < numFrequencies; ++i)
    {
        const float rangeMin    = (float)i / 10.0;
        const float rangeMax    = (float)(i + 1) / 10.0;
        std::cout << "[" << rangeMin << ";" << rangeMax << "]"
            << " | " << frequencies [ i ] << "\n-----------------" << std::endl;
    }
}

(And if you want to be really object-oriented, you would probably be better off using a std::vector for frequencies[] than passing around an array and a count, too.)

Answer 2

I see a number of things that could help you improve your code.

Don't abuse using namespace std

Putting using namespace std at the top of every program is a bad habit that you'd do well to avoid. Know when to use it and when not to (as when writing include headers). I don't know for sure that you've done this in your code (since it's just a fragment and not a complete program) but it's an amazingly common thing for especially new C++ programmers to do.

Fix your program bugs

If this code compiled on your machine, your compiler is broken. The problem is that the definition of i in the first for loop goes out of scope when that loop ends. That means that the second for loop should start for (int i=0; ... or it isn't really valid C++. Also, with your \$X_0\$ term being a negative integer, the index for the mas array when you calculate \$X_3\$ will also be negative, which will cause a memory access error (and probably a program crash) when the value of mas is updated. The initial value of x should be a positive integer.

Use more whitespace for readability

The second for loop line is extremely dense and hard to read. To make it easier to read, put things on separate lines and use whitespace to make things easier to read and understand:

for (int i = 0; i < 10; i++) {
    std::cout << "[" << (float)i / 10 << ";" << (float)(i + 1) / 10 << "]" 
        << " | " << mas[i] << "\n-----------------" << std::endl;
}

Think carefully about the mathematics

The code that is being used to decide which "bin" the psuedo random number goes into is faulty. It currently uses ceil(u*10) but the problem is that this will incorrectly classify numbers into mas[10] which is out of range. Instead, the code should use the simpler version:

int r = u * 10;
mas[r]++;  

Note also the use of the more idiomatic ++ operator rather than the form that is currently in the code.

Omit the return for a void function

The return at the end of void function metod1 is not needed. Omit it to make the code cleaner and easier to read.

Pass parameters instead of using global variables

The mas parameter is neither defined within the function nor passed as a parameter, so it must be a global variable. It's almost always better to explicitly pass the variables instead of using global variables. The advantage is that the coupling and dependencies of the function are explicit and easily read and understood.