Integers to English words in C

Question

As a beginner in C programming, I decided to write a function words that, given an unsigned integer n, puts the English representation in words of n into the character array dest.

This code is quite difficult to follow due to its complexity. If I hadn't written this code, it would take me a good while to understand it fully. What can I do to improve readability and reduce the unnecessary complexity?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const char *digits[] = { "one ", "two ", "three ", "four ", "five ", "six ", "seven ", "eight ", "nine " };
const char *tens[] = { "ten ", "twenty ", "thirty ", "forty ", "fifty ", "sixty ", "seventy ", "eighty ", "ninety " };
const char *teens[] = { "eleven ", "twelve ", "thirteen ", "fourteen ", "fifteen ", "sixteen ", "seventeen ", "eighteen ", "nineteen " };
const char *hundreds[] = { "thousand ", "million ", "billion " };

char *strprep(const char *prefix, char *dest)
{
    char *temp = strdup(dest);
    sprintf(dest, "%s%s", prefix, temp);
    free(temp);
    return dest;
}

void words(unsigned int n, char *dest)
{
    unsigned int l, r, m, d = 0, t = 0;
    char d_cpy[16];

    while(n)
    {
        r = n % 10;
        n = (n - r) / 10;
        m = d % 3;

        if(d && !m)
        {
            if(r || n % 100)
            {
                strprep(hundreds[t], dest);
            }

            t++;
        }

        if(r)
        {
            switch(m)
            {
                case 0:
                    if(n % 10 != 1)
                    {
                        strprep(digits[r - 1], dest);
                    }
                    break;
                case 1:
                    if(l && r == 1)
                    {
                        strprep(teens[l - 1], dest);
                    }
                    else
                    {
                        strprep(tens[r - 1], dest);
                    }
                    break;
                case 2:
                    strcpy(d_cpy, digits[r - 1]);
                    strprep(strcat(d_cpy, "hundred "), dest);
            }
        }

        l = r;
        d++;
    }

    if(!strlen(dest))
    {
        strcpy(dest, "zero");
    }
}

To provide some context, words() is called in main() (defined in the same file):

#include <limits.h>

int main(int argc, char *argv[])
{
    char *last;
    unsigned long int n;

    if(argc != 2)
    {
        puts("incorrect number of arguments!");
        printf("usage: %s [integer]\n", argv[0]);
        return -1;
    }

    n = strtoul(argv[1], &last, 10);

    if(*last || !(*argv[1]) || n > UINT_MAX)
    {
        puts("first argument must be a valid integer");
        return -1;
    }

    char buf[256];
    puts(words((unsigned int)n, buf));
}

Answer 1

Design

Your function fails to write a NUL terminator at the end of the output. That means that the caller must zero the entire buffer before calling the function (or else use a static buffer).

The output does have a superfluous space at the end, though.

As a rule, whenever you call a function to write to a string buffer, you must also pass the buffer's size. Otherwise, the function has no way of knowing when to stop before the buffer overflows. (That's why poorly designed functions such as gets(char *buf) and sprintf(char *s, const char *format, …) should be shunned, and you should use the safer alternatives fgets(char *s, int n, FILE *stream) and snprintf(char *s, size_t n, const char *format, …) instead.)

Therefore, I recommend that words() be designed similar to snprintf(): it should accept one more parameter for the buffer size, and it should return the length of the string that was written (or should have been written).

It's annoying that your string arrays are off "off by one", such that you have to write -1 in digits[r - 1], teens[l - 1], and tens[r - 1].

The hundreds array is altogether misnamed, as it has nothing to do with hundreds. I'd call it scales.

Algorithm and implementation

Your string manipulation is inefficient:

• Prepending any string (using strprep()) involves copying characters. It would be worthwhile to rework the algorithm such that it only needs to write its output sequentially and never needs to prepend anything.
• If you did have to prepend a string, it would be smarter to avoid allocating a temporary string using strdup(), then freeing it. Using memmove(), with no temporarily allocated memory, would be smarter.

By the way, the strprep() function, being a helper function, should be declared static.

The special case…

if(!strlen(dest))
{
    strcpy(dest, "zero");
}

… should be handled at the very beginning of words(), using if (n == 0), avoiding strlen(), which would have to traverse the output character by character to determine the length. (And remember, strlen() doesn't even work, since you don't ensure that the output is NUL-terminated.)

n = (n - r) / 10 can be simply written as n /= 10.

Nobody likes to read code with uncommented cryptic variable names like this:

unsigned int l, r, m, d = 0, t = 0;

After staring at your code for a very long time, I have figured out that…

• d is the exponent of 10 (and would probably be better named exponent).
• t is just d / 3 (and should therefore be eliminated).
• m is just d % 3 (and should therefore be eliminated).
• r is the rightmost digit currently being considered.
• l is the digit to the right of r.

Minimal rewrite

Here is a slightly revised version of your code, with the following goals:

• NUL terminator
• strprep() without a temporary string allocation
• character arrays without the off-by-one annoyance
• simpler special case for 0
• fewer variables, with more intuitive names

#include <stdlib.h>
#include <string.h>

const char *digits[] = { NULL, "one ", "two ", "three ", "four ", "five ", "six ", "seven ", "eight ", "nine " };
const char *tens[] = { NULL, "ten ", "twenty ", "thirty ", "forty ", "fifty ", "sixty ", "seventy ", "eighty ", "ninety " };
const char *teens[] = { "ten ", "eleven ", "twelve ", "thirteen ", "fourteen ", "fifteen ", "sixteen ", "seventeen ", "eighteen ", "nineteen " };
const char *scales[] = { "", "thousand ", "million ", "billion " };

static void strprep(const char *prefix, char *dest) {
    size_t prefix_len = strlen(prefix);
    memmove(dest + prefix_len, dest, strlen(dest) + 1);
    memcpy(dest, prefix, prefix_len);
}

void words(unsigned int n, char *dest) {
    if (n == 0) {
        strcpy(dest, "zero");
        return;
    }

    *dest = '\0';

    int prev_digit;
    for (int exponent = 0; n; exponent++) {
        int digit = n % 10,
            remaining_digits = n / 10;

        if ((exponent % 3 == 0) && (n % 1000)) {
            strprep(scales[exponent / 3], dest);
        }

        if (digit) {
            switch (exponent % 3) {
              case 0:
                if (remaining_digits % 10 != 1) {
                    strprep(digits[digit], dest);
                }
                break;
              case 1:
                if (digit == 1) {
                    strprep(teens[prev_digit], dest);
                } else {
                    strprep(tens[digit], dest);
                }
                break;
              case 2:
                strprep("hundred ", dest);
                strprep(digits[digit], dest);
                break;
            }
        }

        prev_digit = digit;
        n = remaining_digits;
    }
}

Suggested solution

I recommend using a completely different algorithm, because:

• For efficiency, the algorithm needs to always append, never prepend.
• You need to keep track of the number of bytes written, so as to avoid buffer overflow.

• Your algorithm is hard to understand. When considering the ones digit, it needs to look ahead to see whether the tens digit is 1, in which case it should temporarily output nothing. When considering the tens digit, if it's 1, then it needs to consult the previously saved ones digit (which is the only place where l is used).

  I recommend considering groups of three digits at a time, so that you have a variable which represents the hundreds, the tens, and the ones digit.

This ends up being a lot of snprintf() calls, keeping track of the number of characters written.

#include <assert.h>
#include <stdio.h>

static const char *digits[] = {
    "", "one", "two", "three", "four", "five",
    "six", "seven", "eight", "nine"
};
static const char *teens[] = {
    "ten", "eleven", "twelve", "thirteen", "fourteen",
    "fifteen", "sixteen", "seventeen", "eighteen", "nineteen"
};
static const char *tens[] = {
    "", "ten", "twenty", "thirty", "forty",
    "fifty", "sixty", "seventy", "eighty", "ninety"
};
static const char *scales[] = { "", "thousand", "million", "billion" };

/**
 * Given 0 <= n < 1000, writes n as English words to buf, followed by a NUL
 * terminator.  If n == 0, then just a NUL terminator is written.
 *
 * Returns the length of the output written, excluding the NUL terminator
 * (or the length of the string that should have been written, if the return
 * value is greater than or equal to the buffer size).
 */
static int words1k(int n, char *buf, size_t size) {
    assert(0 <= n && n < 1000);
    int h = n / 100,
        t = (n % 100) / 10,
        o = (n % 10);
    switch (t) {
      case 0:
        return snprintf(buf, size, "%s%s%s%s",
            digits[h], (h ? " hundred" : ""),
            (h && o ? " " : ""), digits[o]);
      case 1:
        return snprintf(buf, size, "%s%s%s",
            digits[h], (h ? " hundred " : ""), teens[o]);
      default:
        return snprintf(buf, size, "%s%s%s%s%s",
            digits[h], (h ? " hundred " : ""),
            tens[t], (t && o ? "-" : ""), digits[o]);
    }
}

/**
 * Writes n as English words to buf, followed by a NUL terminator.
 * (A buffer size of 120 is recommended.)
 *
 * Returns the length of the output written, excluding the NUL terminator
 * (or the length of the string that should have been written, if the return
 * value is greater than or equal to the buffer size).
 */
int words(unsigned int n, char *buf, size_t size) {
    size_t len = 0;
    if (n == 0) {
        return snprintf(buf, size, "zero");
    } /* else if (n < 0) {
        int nlen = snprintf(buf, size, "negative ");
        len = words(-n, buf + nlen, (size > nlen ? size - nlen : 0));
        return nlen + len;
    } */
    for (int s = 3, scale = 1000000000; s >= 0; s--, scale /= 1000) {
        // If there was any previous output, leave room for a space after it
        int start_pos = len ? len + 1 : 0;
        int klen = words1k(n / scale, buf + start_pos, (size > start_pos ? size - start_pos : 0));
        // If there was previous output and recent output, then write the space
        if (len && klen) {
            if (len < size) buf[len] = ' ';
            len++;
        }
        len += klen;
        if (klen && s) {
            len += snprintf(buf + len, (size > len ? size - len : 0), " %s", scales[s]);
        }
        n %= scale;
    }
    return len;
}

Answer 2

1. Keep your line-length under control. Horizontal scrolling is death on readability.

2. strprep() is extremely inefficient, and even assuming the destination is big enough, you don't check whether allocation of your needless temporary buffer succeeds. Better to fix that:

   char *strprep(const char *prefix, char *dest) {
       size_t prefix_len = strlen(prefix);
       memmove(dest + prefix_len, dest, strlen(dest) + 1);
       memcpy(dest, prefix, prefix_len);
       return dest;
   }
   

3. Assuming a user-supplied Buffer contains an empty string for no reason is certainly an interesting decision. It violates the principle of least surprise though, and leads to Undefined Behavior if the assumption proves unfounded.

4. I won't try to decipher what your cryptic single-character variables in words() are for. Do everyone (especially yourself) a favor and invest some more into finding good names.

5. Using strlen() to decide whether a string is empty? That's an \$O(n)\$ call where a primitive direct check is sufficient:

   if (!*dest) // dest is empty
   

   Most optimizing compilers in hosted mode will succeed in lowering it to the above, but why write that much more and rely on it?

6. Actually, check for zero beforehand instead. No need to do so after failing to put it into words some other way.

7. Either your example code violates the contract of words(), or words is buggy. I suggest fixing words() to not assume the buffer is pre-filled with an empty string.

8. Consider merging multiple outputs into one request. Don't worry, due to adjacent string-literals being concatenated by the compiler, that need not result in one humungous string-literal.

Answer 3

Consider what

char buf[256];
puts(words(0, buf));

with words() below.

strlen(dest) would be undefined behavior as buf[] was never initialized and so a null character may not be found with strlen(dest) before searching outside buf bounds.

while(n)
  ...
if(!strlen(dest))
{
    strcpy(dest, "zero");
}