A Close Look at a Simple Problem

Recently, one of us (Andy) went to a short workshop on guitar technique in which the instructor gave a particularly interesting exercise: Pick a random spot on the fretboard and play, by ear, a tune that you know well, starting at that spot. The kicker was that, although you could play as slowly as you liked, you had to play the tune perfectly on the first try — one mistake and you had failed. This exercise is harder than it looks: Several friends, whom we consider to be excellent musicians, either failed or declined to try.

Consider an analogous exercise in the programming domain: Pick a simple problem and solve it, with the stipulation that the solution must work correctly the first time. How many of us can confidently say that we can solve even a nearly trivial problem correctly without testing? The best we can do is to write our programs in such a way that it is difficult for them to fail.

The Problem

To illustrate how to go about writing a program that we are confident will work, here is a problem: How many decimal digits are in a given unsigned integer? In other words, we are to write a function:

<b>unsigned ndigits(long unsigned n)
{
   // the function body
}</b>

that will tell us how many digits are in the decimal representation of n. We shall assume that 0 has one digit, noting that we could assume equally well that 0 has no digits — an assumption that would yield a different program.

For the purpose of this problem, we are not allowed to use any library functions — particularly library functions that convert integers to strings — because then we would be using someone else's solution to the problem instead of solving it ourselves. Moreover, we must not use any floating-point arithmetic, because of the intrinsic difficulty in understanding the rounding problems that might come up.

If we were to set out to solve this problem naively, we would probably start by writing something like this:

<b>// Naive solution — can it be made to work?
unsigned ndigits(long unsigned n)
{
     unsigned count = 0;
     while (<i>condition</i>) {
          ++count;
          n /= 10;
     }
     return count;
}</b>

and then go looking for an appropriate condition to make the code work.

An obvious choice for a condition for such a loop is to compare n to 0. It should be clear that n >= 0 and n < 0 will not do as choices: Because n is unsigned, the first condition is always true and the second is always false. Similarly, n == 0 and n <= 0 are useless because unless n is zero, the loop won't be executed at all, thereby yielding the same number of digits for all numbers greater than zero.

Therefore, if zero is involved in the condition, it must be n != 0 or, equivalently, n > 0. However, this condition also doesn't work, because it will inevitably claim that 0 and 1 have a different number of digits — a claim that contradicts the requirements of our problem.

This line of reasoning should convince you that comparing n to zero cannot yield a correct program. Rather than trying other conditions until we find one that works, we intend to approach the problem from the other end, starting with two observations:

1. An unsigned integer less than 10 has one digit.

2. If n10, then n has at least two digits, and n/10 (truncated to the next lower integer, as C++ unsigned integer division does) is one digit shorter than n.

In effect, these observations define the meaning of "decimal digits." For a program we write to be correct, it will have to be consistent with these observations.

In the rest of this column, we start from these observations and use them to develop three different solutions to our problem. Because these solutions grow directly out of the observations, we expect that we shall be more confident in their correctness than if we just used our intuition to write them.

Direct Recursion

The simplest way to translate our two observations into code is to write a piece of code that directly implements each observation. The resulting program is recursive:

<b>unsigned ndigits(long unsigned n)
{
     if (n < 10)
          return 1;
     return ndigits(n/10) + 1;
}</b>

The if statement implements Observation 1: If n is less than 10, the result of the function is 1. The return statement implements Observation 2: If n is not less than 10 (which we know, because otherwise we wouldn't be here), we determine the number of digits in n/10 and return one more than that value.

It is hard to imagine a more direct solution to our problem, and equally hard to imagine that the solution might not be correct. There is only one difficulty: The program is recursive, and some people find recursion hard to understand. Well, that's not the only problem with recursion: Another problem, which is important in contexts such as embedded systems, is that recursive functions consume an amount of memory that is proportional to the number of instances of the function that are active at one time. Some kinds of embedded systems have fixed memory requirements to guarantee that no matter what happens, the system will not run out of memory.

For these reasons, and to broaden the exercise, we would like to solve the problem without recursion. We shall do so in two different ways: first, by constructing an iterative program directly, and then by transforming the recursive program that we just wrote into an iterative program.

Direct Iteration

An important way of thinking about iterative programs is in terms of loop invariants. For those of you who have not read the discussion of invariants in Accelerated C++, here's a summary.

A loop invariant is a claim about the state of the program that is always true each time through a particular loop. Before the loop begins, the program must ensure that the invariant is true. In the body of the loop, the program can assume that the invariant is true at the beginning, in exchange for which it must ensure that the invariant is true again at the end of the loop body.

If the program takes care to maintain the invariant in this way, the invariant will still be true after the loop terminates. Moreover, the condition that controls termination will also be true. If we can arrange the condition and invariant so that their simultaneous truth solves our problem, we are done.

This discussion is awfully abstract. To make it more concrete, let's apply it to our problem. We said earlier that a naive solution would include a loop such as:

<b>while (<i>condition</i>) {
   ++count;
   n /= 10;</b>

If a loop of this form can be made to work, we should be able to find an appropriate invariant. That invariant dictates the condition that we need, and the condition and invariant together will let us write the rest of the program.

Each trip through the loop increases count and reduces the number of digits in n by one. This fact suggests that the invariant might say something about the sum of count and the number of digits in n.

Suppose we define x as the number of digits in the original value of n; that is, the value that we wish ultimately to compute. For convenience, let's also use #(n) to refer to the number of digits in the current value of n, even though we won't always know what that value is. Then a plausible loop invariant is x=count+#(n), where "=" represents mathematical equality, not C++ assignment. To see why, look again at our naive loop:

<b>// Assume that x=count+#(n) is true here
while (condition) {
     ++count;
     n /= 10;
}</b>

As already noted, the body of the loop increases count by one and decreases #(n) by one. Therefore, if x=count+#(n) is true at the beginning of the loop body, it will again be true at the end.

What about the condition? When the loop finishes, we know that x=count+#(n) is still true. To choose the condition, then, it suffices to find one that makes the value of #(n) known. By Observation 1, that condition is n >= 10; when that condition is false, we know that #(n) is 1.

Once we have reduced n to a value less than 10, thereby making #(n) equal to 1, we know from the invariant that x is count + 1. Accordingly, we can return count + 1 from the program. To be confident that our program is correct, all that remains is to give count an initial value that makes the invariant true.

We know that before the loop starts, #(n) is equal to x, even though we don't know the value of #(n) or x. Accordingly, we can make the invariant true by setting count to zero.

The result is this program:

<b>unsigned ndigits(long unsigned n)
{
     unsigned count = 0;
     <i>// Invariant: x=count+#(n)</i>
     while (n >= 10) {
          ++count;
          n /= 10;
     }
     <i>// At this point, #(n) must be 1</i>
     return count + 1;
}</b>

Suppose that we would like to return count instead of count + 1. We know now that when our loop ends, #(n) is 1. If we wish it also to be true that count=x, then we must change our invariant. How about changing it to count+#(n)=x+1? Then when we have reduced #(n) to 1, count will have the value of x.

If we are going to change our invariant, we shall have to change the initial value of count to 1. The rest of the program can remain unchanged:

<b>unsigned ndigits(long unsigned n)
{
     unsigned count = 1;
     <i>// Invariant: x+1=count+#(n)</i>
     while (n >= 10) {
          ++count;
          n /= 10;
     }
     <i>// At this point, #(n) must be 1</i>
     return count;
}

Indirect Iteration

There is another way to solve this problem without recursion: Take the recursive solution and rewrite it into iterative form.

One way to approach such a rewrite is to begin by changing the program so that each recursive call is a tail call — a call that is the very last thing that happens in the function. The call

</b><b>return ndigits(n/10) + 1;</p>

is not a tail call because after the recursive call, we add 1 to the result.

It is not always easy to turn recursive calls into tail calls because not all recursion is easy to eliminate. When it is possible, it is often possible by generalizing the problem to be solved. For example, the trick to removing the recursion from this specific function is to change it so that instead of returning the number of digits in n, the function returns a secondary value k added to the number of digits in n.

Because we're changing what the function does, we shall change its name: ndigitsk(n, k) will return k plus the number of digits in n. It is useful to change what our function does, because doing so will let us change

<b>return ndigits(n/10) + 1;

to

</b><b>return ndigitsk(n/10, k + 1);</p>

which is a tail call:

</b><b>unsigned ndigitsk(long unsigned n, unsigned k)
{
     if (n < 10)
          return k + 1;
     return ndigitsk(n/10, k + 1);
}</b>

We can rewrite our original ndigits function into one that calls ndigitsk appropriately:

<b>unsigned ndigits(long unsigned n)
{
     return ndigitsk(n, 0);
}</b>

We can now eliminate the tail call in ndigitsk by putting a label at the beginning of the function body and turning the tail call into two assignments and a goto:

<b>unsigned ndigitsk(long unsigned n, unsigned k)
{
loop:
     if (n < 10)
          return k + 1;
     ++k;
     n /= 10;
     goto loop;
}</b>

Now that we've seen the resulting structure, it should be easy to see that we can turn the goto loop back into a while:

<b>unsigned ndigitsk(long unsigned n, unsigned k)
{
     while (n >= 10) {
          ++k;
          n /= 10;
     }
     return k + 1;
}</b>

Finally, we can merge ndigitsk back into ndigits by copying the body of ndigitsk into ndigits after initializing k appropriately:

<b>unsigned ndigits(long unsigned n)
{
     unsigned k = 0;
     while (n >= 10) {
          ++k;
          n /= 10;
     }
     return k + 1;
}</b>

To our delight, this version of ndigits is identical to the first one that we constructed using loop invariants, except that the variable count changed its name to k.

Discussion

It may seem silly to spend this much time looking at such a simple piece of code. However, experience shows that a surprising number of programmers wind up making mistakes even in simple programs. Such mistakes often take the form of off-by-one errors, which are notoriously hard to trace and tend to cause security vulnerabilities.

One way to learn to avoid such errors in large programs is first to learn to avoid them in small programs. You would think that it would be trivial to write a program that correctly counts the number of digits in an integer — but you would also think that it would be trivial to pick out a simple tune on a guitar without making a mistake. In both cases, the task requires a certain way of thinking, and in both cases, you can learn to think that way by practicing small problems before going on to larger ones.

The fact is that writing programs that work is just plain hard, and one important way of making it easier is to think rigorously about what the programs are doing.

Exercise

In case you're still not convinced that tiny programs can be tricky, you might try writing a version of this program that deals with signed long integers rather than unsigned ones. To do so, you must decide whether the number of digits in a negative number is the number of digits in its absolute value, or whether it is the number of characters the number would occupy if printed.

Once you have made that decision, you still face an implementation problem: If n is negative, there is no guarantee of being able to evaluate -n because in 2's-complement arithmetic, there will always be one negative value with no corresponding positive value. Moreover, for negative n, the implementation is permitted to truncate the value of n/10 either up or down. Accordingly, the value of (-99)/10 might be either -9 or -10, which means that dividing a negative integer by 10 does not necessarily decrease the number of digits.

The next time you try to solve a complicated problem, remember how hard it was to solve this simple one.