Code Refactoring – C/C++ Unnecessary Loop Replaced with Math Expression

I am starting a series of code refactoring examples as I see them a lot from time to time. Today, I read the following piece of code in our C#.NET codebase (and translated to equivalent C/C++ code for educational purposes).

1
2
3
4
5
6
7
8
9
10
11
12

double getRes(double height, double res) {
        int num = 3;
        double next = height / num;
 
        // increase number of cubes if the next resolution is not worse
        // than the preferable res
        while (next >= res) {
                num ++;
                next = height / num;
        }
        return next;
}

double getRes(double height, double res) {
        int num = 3;
        double next = height / num;

        // increase number of cubes if the next resolution is not worse
        // than the preferable res
        while (next >= res) {
                num ++;
                next = height / num;
        }
        return next;
}

The while loop does not make it more readable but the comment is the key here: the target of this function is to return a value by attempting height / (num ++) until this value is smaller than the res.

refactoring

A first thought would be: if res is passed in as negative values, the while loop will certainly become a dead endless loop. So the first improvement will be adding a check (you could throw the exception if res is negative) or put an ASSERT (which is to be eliminated in production code).

This implementation is O(height/res), however, it can be simplified by using one line of math expression:

1
2
3

double getRes2(double height, double res) {
        return height / (int)max(3.0, ceil(height / res));
}

double getRes2(double height, double res) {
        return height / (int)max(3.0, ceil(height / res));
}

The ceil is declared at cmath and what it does is to return the smallest integer that is bigger than the input. With no doubt, this implementation is concise and with O(1) constant running time.

How to Prove it Right?

Depending on the context, both implementations may not be correct in some corner cases. However, in order to create a pull request and have this piece of code fixed, you kinda have to pass the relevant unit tests. And, it is also helpful to write a ‘proof test‘ that says: Hey, my implementation is better and it does not change your behavior!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void test(double height, double res) {
        double answer1 = getRes(height, res);
        double answer2 = getRes2(height, res);
        if (abs(answer1 - answer2) > 1e-8) {
                throw; // if different values
        }
}
 
int main() {
        const int N = 1000;
        const double H_MAX = 10000;
        const double R_MAX = 100;
        srand (time(NULL));
        for (int i = 0; i < N; ++i) {
                double height = ((double)rand() / RAND_MAX) * H_MAX;
                double res = ((double)rand() / RAND_MAX) * R_MAX + 0.01; // avoid zero
                test(height, res);
        }
        return 0;
}

void test(double height, double res) {
        double answer1 = getRes(height, res);
        double answer2 = getRes2(height, res);
        if (abs(answer1 - answer2) > 1e-8) {
                throw; // if different values
        }
}

int main() {
        const int N = 1000;
        const double H_MAX = 10000;
        const double R_MAX = 100;
        srand (time(NULL));
        for (int i = 0; i < N; ++i) {
                double height = ((double)rand() / RAND_MAX) * H_MAX;
                double res = ((double)rand() / RAND_MAX) * R_MAX + 0.01; // avoid zero
                test(height, res);
        }
        return 0;
}

We often hear people say: it works at the moment, so we don’t want to change it because it is too risky. This is an example that it may seem working (keep touching the wood), however, when something goes wrong (like the input here is negative), the outcome is a disaster (endless loop).

Make sure the function does what it does under all circumstances (throw (catch rarely, throw often) an exception if negative numbers are not considered, which prevents undefined/untested behaviors).

The purpose of code refactoring is two-fold: Make the code correct, and Improve the code performance.

–EOF (The Ultimate Computing & Technology Blog) —