Thread: Programme Efficiency

Hi everyone,
I've been writing programmes in C for about a year now (with some big gaps in between), and I'm never comfortable with anything I write. It seems that no matter what method I choose to solve the problem, there's always a better method that I miss. My programmes almost always work but I always write huge programmes for simple tasks and the phrase "programme efficiency" can in no way be related to any of my programmes. Today, I wrote an itoa function that uses recursion. Once again, it works, but I'm sure there's a better way of doing it. I thought maybe if I post the programme, you guys would be good enough to point out some issues, so here's the code:

Code:

char* itoa(int num)
{
        static int cnt = 0;
        static char s[10];
        static int i = 0;
        char ch;
                                                                                                                
        if(num < 0)
        {
                s[cnt++] = '-';
                num = -num;
                i = cnt;
        }
        if(num / 10)
        {
                cnt++;
                itoa(num / 10);
        }
        ch = (char)(num % 10 + '0');
        s[cnt-(cnt-i)] = ch;
        if (cnt == i)
                return s;
        else
        {
                i++;
                return NULL;
        }
}

I appreciate some advice.

P.S.: Generally, when the number of variables I use gets big, I know there's something wrong.

>char* itoa(int num)
I don't really like how you return a string. Unless the caller passes in an appropriately sized block of memory, you have no choice but to either return dynamically allocated memory, or memory with static duration. Both of those solutions pose problems that make them impractical for such a general function. It would be better to have the caller pass in memory that itoa works with:

Code:

char *itoa(int num, char *dst);

Like many toy implementations of itoa, yours fails to handle the most negative value of a two's complement machine, INT_MIN in <limits.h> can be used to test this. A quick fix is the following:

Code:

if(num < 0)
{
  s[cnt++] = '-';
  num = -num;
  i = cnt;
}

Rather than try to remove the sign, leave it and use cnt to ensure that this test will only be performed once:

Code:

if(cnt == 0 && num < 0)
{
  s[cnt++] = '-';
  i = cnt;
}

This way you retain the negative value. The reason it wouldn't work before is because negating INT_MIN doesn't give you INT_MAX because on a two's complement machine, INT_MIN is one greater than INT_MAX toward the negative, 32767 and -32768 with 16 bit integers, for example.

Now you'll find that

Code:

ch = (char)(num % 10 + '0');

Doesn't work right because num is negative. The solution to this is to include <stdlib.h> and use abs() to force the num % 10 into the positive range, giving us the following function with the correct behavior:

Code:

char* itoa(int num)
{
  static int cnt = 0;
  static char s[10];
  static int i = 0;
  char ch;

  if(cnt == 0 && num < 0)
  {
    s[cnt++] = '-';
    num = -num;
    i = cnt;
  }
  if(num / 10)
  {
    cnt++;
    itoa(num / 10);
  }
  ch = (char)(abs(num % 10) + '0');
  s[cnt-(cnt-i)] = ch;
  if (cnt == i)
    return s;
  else
  {
    i++;
    return NULL;
  }
}

>static char s[10];
Be wary of hardcoded sizes like this, what if the system allows for 64 bit integers? A good, safe way to calculate such a size is with a calculation like this (conveniently placed in a macro for your...um...convenience. ):

Code:

#include <limits.h>
#define INT_DIGITS ((sizeof(int) * CHAR_BIT + 2) / 3 + 2)

Then you can change your declaration to:

Code:

static char s[INT_DIGITS];

And be reasonably sure that it will work properly regardless of the system you compile on.

Now, call your itoa more than once and you'll begin to see the problem of using local static variables. They retain their values between calls, so you'll be in somewhat of a pickle if you don't reset them somehow.

>is pretty much the same as the itoa() you've written.
I doubt sprintf is recursive though, and certainly not as much fun.