Home > Articles > Programming > C/C++

  • Print
  • + Share This
From the author of Other Aspects of Efficient Algorithms

Other Aspects of Efficient Algorithms

So far I have scratched the surface of some of the attributes of the best algorithms: efficiency, brevity, best use of data, and above all not recalculating a value that has already been calculated. Entire books have been written on the subject.

But I will also mention one of my pet peeves. Wherever possible, an algorithm should be as streamline as possible—that is, as much as possible, you should try to treat every case the same way. You want to use special cases as little as possible.

Consider the following problem: suppose you want to write a function called pass_or_fail() that takes a single integer n and returns true n percent of the time. For example, pass_or_fail(55) should return true 55 percent of the time and false 45 percent of the time. The obvious solution is to get a random number in the range 1 to 100 and then see if that number is less than or equal to the test value:

bool pass_or_fail(int test_val) {
     int p = rand() % 100;      // p = 0 to 99
     if (p == 0)                // Special-case 0...
          p = 100;              //  This is stupid.
     return p <= test_val;
}

Assuming the only randomization function you have access to is the classic C/C++ rand() function, the most efficient way to get a random number from 0 to N-1 is use modular division (%) on N—in this case, 100. Alternatively, you could divide by RAND_MAX, the number of integers in the range returned by rand(), and then multiply by 100, but this is more work and therefore less efficient:

     int p = (rand() / (double) RAND_MAX) * 100:

The problem, in either case, is that you get a number from 0 to 99 instead of 1 to 100. The worst possible solution is to special-case zero and flip it over to 100, as done earlier. A better way is to just add 1:

bool pass_or_fail(int test_val) {
     int p = rand() % 100 + 1;    // p = 1 to 100
     return p <= test_val;
}

But even that’s a poor way of doing things. The question any good C or C++ programmer should ask is: Why do we need to use a greater-or-less-than comparison (<=) in the first place? By using a less-than comparison (<), this function becomes really simple indeed:

bool pass_or_fail(int test_val) {
     return rand() % 100 < test_val;
}

The moral of the story? Don’t use special cases unless you have to. And in general, don’t do make the program do unnecessary work.

  • + Share This
  • 🔖 Save To Your Account