Maintainability - what the hell is this?

int sqfunc (int s)
{
int x, x0 = s;
do {
x = x0;
x0 = (x0 + (s / x0)) / 2;
} while (x0 != x);
return (x);
}
Figure 1. Some code which is, er, "difficult" to read

If you were given the job of hunting down a bug in some source code and you came across the snippet in figure 1, it's obvious what it does, isn't it? As soon as you saw this snippet you'd feel right at home and know exactly what to do, right?

Well, probably not.

The snippet has no comments. It's not obvious what it does. Just by looking at it, you can't easily tell what relationship the input s has to the returned value x. The name of the function doesn't give you a clue, and the names of the variables are no help either.

What can we work out about the code?

Let's see…

It's declared as returning an int and it takes a single int argument. This means that the range of values it takes and returns can be negative, positive or zero.

It loops around some number of times before returning. Well, that's not much help.

The fact that the function isn't declared static means that it might be used in other files apart from the in which we found it.

Yippee! We're no better off.

What do we do with this?

We're still no wiser. We still don't know what it does.

The big question is: If you don't know what it's supposed to do, how can you fix it? Indeed, how do you even know if this is what's broken.

In fact, it actually does have a subtle bug.

The purpose revealed

Drum roll…

The code in figure 1 is actually a function which calculates integer square roots.

You give it a number, like 4, and it'll return the square root, in this case 2. Obviously, it can't give you the exact square root of a number like 6 or 11, but it'll get close and return the square root +/- 1.

You may be wondering why anyone would want to write such a function when there's a perfectly good sqrt() function in the standard library which does the same thing. If you're writing software for a desktop computer or a server you probably wouldn't. One situation where you would though, might be when you're coding for an embedded system where you have very limited RAM or ROM space available. Every bit literally counts and you may not want the overhead of linking in a full maths library when all you want is sqrt(). So you write your own and save lots of space.

What does it do?

The code uses a successive approximation method to calculate the square root. The technique is called the Babylonian method. Over a number of loops, the code converges on the answer and then it stops and returns the result.

It's a pretty good technique and, as you can see, it doesn't need "interesting" maths like logarithms or exponentials. It's ideal for a limit environment such as you might find in an embedded system.

It's also very easy to implement.

The implementation in the figure though, has a couple of problems.

FIrstly, when you call it with s set to zero we get a divide-by-zero error straight away. Ooops.

Secondly, there's the subtle bug I mentioned.

If you test the function with a range of other numbers then there's a good chance it'll work OK. If you give it 16 it'll return 4. Give it 1000, 100, 64 or 98 and it'll give the right answer for the squares and a close answer for everything else. Give it very large numbers and it'll come back with the right answer. You might be inclined, after such testing, to think it's working perfectly.

Then you try 63 and you find that it never returns. It hangs.

Bummer! This can be fixed, though.

When you use integer arithmetic, the algorithm doesn't converge to a single answer when the input is a square minus 1 (e.g. 2 x 2 - 1 = 3, 10 x 10 - 1 = 99, etc.). The algorithm ends up cycling between two answers in these cases. You can find more of an explanation of this on the Wikipedia page about integer square root.

Making it work

static unsigned int isqrt (unsigned int s)
{
unsigned int x, x0;

if (s <= 1) return (1);

x = s;

while (1) {
x0 = (x + (s / x)) / 2;
x0 = (x0 + (s / x0)) / 2;
if (x == x0) return (x);
x = x0;
}
}

Figure 2. A first cut at tidying and fixing the code.

Let's start fixing up the code and, along the way, make it more maintainable. This is the first step towards making the code firstly work, and then be something which a future programmer will feel comfortable working on. See figure 2.

What I've done is:

  1. Changed the function name to something reminiscent of the sqrt() it replaces so someone seeing it immediately gets a clue about what it does.
  2. Changed all the int declarations to unsigned int. Pretty obviously this is a simple square root function - it's not intended for imaginary numbers. By declaring everything as unsigned int anyone who comes along later to look at the code will know it's deliberately not meant to work on negative numbers. Even the compiler can give a warning if someone tries to pass it an int.
  3. Added an if at the beginning to catch when the input is zero (or one because we have the if there anyway) and return an answer without hanging or crashing.
  4. Dealt with the problem of cycling between answers when the input is a square minus one by doing two approximations per loop. This also has the benefit of explicitly unrolling the loop a little.
  5. Shuffled the order of the code a little to save one execution of x = x0;.
  6. Declared the function static so it's obvious this function is not used in any other file (which, of course, you'd omit if it is).

Before we move on, reflect for a moment: Would you have known where to start with this code if I hadn't explained any of this?

Explaining what we're doing

I known that many (most?) programmers and developers don't like it, but adding comments can make it much easier for those who come after us to make sense of what we were trying to do.

In the case of this particular example, what we started with was particularly intractable. Explaining what we were intending, and any design decisions (such as trying to save space), can help when someone comes along later (even when it's ourselves) to maintain the code.

Let's look at the end result of our example (see figure 3).

/* isqrt() - calculate the square root of an */
/* integer using the "Babylonian method" (see */
/* Wikipedia). We don't use the sqrt() in the */
/* standard library to save space by avoiding */
/* linking in the whole maths library */

static unsigned int isqrt (unsigned int s)
{
unsigned int x, x0;

if (s <= 1) return (1); /* Force answer when*/
/* s's value can */
/* cause a divide */
/* by zero error */

x = s; /* Initial approx. */

while (1) { /* Loop till */
/* convergence */
x0 = (x + (s / x)) / 2; /* Next approx. */
x0 = (x0 + (s / x0)) / 2; /* Do it twice */
/* to catch */
/* period-two */
/* cycling */
if (x == x0) return (x); /* Return result*/
/* if no change */
/* since last */
/* iteration */
x = x0; /* Loop back for*/
/* the next */
/* approximation*/
}
}

Figure 3. The code: fixed and commented.

There's now a comment which explains the purpose of the function and gives a reference to the actual algorithm so the next programmer can look it up. No guesswork required.

Also, each step of the code is explained, including why there are two approximations per loop.

When we consider all this in terms of optimisation, from a maintainability point of view, this is a big win. It's now clear what the code is for and someone can come along and confidently make updates or changes (if needed).

And that's the point, isn't it?