Converting from base-10 to word

Question

The following code is used to convert a base-10 number to a base-N number, where N is a length of a given alphabet that contains characters of which a base-N number can consist.

The number to convert is always increasing, like from 1 to 45789, not from 536 to 13. The resulting number may not contain zero as first digit, so I need to carry the one.

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

typedef unsigned long long ull;

void conv(ull num, const char *alpha, char *word, int base){
    while (num) {
       *(word++)=alpha[(num-1)%base];
       num=(num-1)/base;
    }
}

int main(){
   ull nu;
   const char alpha[]="abcdefghijklmnopqrstuvwxyzOSR34"; 

   /* "OSR43" was added to show that the letters of alpha
      are NOT in alphabetical order */

   char *word=calloc(30,sizeof(char));
   // word always contains null-terminator
   int base=(int)strlen(alpha);
   for (nu=1;nu<=1e8;++nu) {
       conv(nu,alpha,word,base);
       printf("%s\n",word);
   }
   return 0;
}

This code's working fine but I need to speed it up as much as possible. How do I do it?

Answer 1

Improving conv

To convert a base-10 number to base-N, I don't think it gets faster than the conv function your wrote. I would write it a bit differently though:

void toBaseN(ull num, const char *alpha, int base, char *word) {
    while (num) {
       *(word++) = alpha[(num - 1) % base];
       num = (num - 1) / base;
    }
}

What I changed:

• Renamed the function: conv doesn't describe what it does
• Rearranged the parameters: base is tightly related to alpha (the length), and I think it's good to have out-parameters as last
• Add spaces around the operators to improve readability

For the record, this function doesn't return what I would expect. It returns the digits in reverse order, which is a bit odd. For example with the given alphabet, it returns ba for 33 and ca for 34, when I would expect ab and ac, respectively.

The function has a number expectations with regards to the input:

• word is expected to be big enough to contain the digits
• word is expected to be filled with nulls
• base is expected to be the length of alpha

The first one is reasonable and quite natural, the others are not, and should be documented in a comment above the function.

Improving main

const char alpha[]="abcdefghijklmnopqrstuvwxyzOSR34"; 
char *word=calloc(30,sizeof(char));
// word always contains null-terminator
int base=(int)strlen(alpha);
for (nu=1;nu<=1e8;++nu) {

There are a couple of things I don't like about this bit:

• Too packed code: add more spaces around operators like I did in the previous point
• The comment // word always contains null-terminator seems misplaced. It seems you intended it for the line above it. It's more intuitive and readable to have comments above the line they refer to. The make it even more clear, it would be good to leave a blank line before the comment, and perhaps even after the statement
• What is magic number 30? It would be better to make this a global constant
• base is derived from alpha, it's tightly related, so I'd move these closer to each other

I suggest this writing style:

const char alpha[] = "abcdefghijklmnopqrstuvwxyzOSR34";
int base = (int) strlen(alpha);

// word always contains null-terminator
char *word = calloc(30, sizeof(char));

for (nu = 1; nu <= 1e8; ++nu) {

Improving speed

As I mentioned above, the general functionality of conv without a context is as fast as it can be. (And incorrect: normally I'd expect digits to be reversed.)

In the context of printing base-N numbers within the range [start : end], you can do better. You could convert start and end to base-N, to do the counting in base-N. This will be significantly faster than counting in base-10 and converting in every step.

Answer 2

Typedef

I like to avoid typedefs without semantic meaning. In other words, ull is just a shortcut for unsigned long long, not a meaningful type.

I'm assuming you care you about the maximum value more than you care that the type is specifically an unsigned long long, so I would use uint64_t from stdint.h instead of your typedef.

If you are going to use a typedef, try to give it a more meaningful name (which is pretty difficult in this situation without resorting to a pretty vague name like number or something).

---

while vs for

This is more of a personal style thing, but I tend to use for loops over while loops whenever reasonable:

for (; num > 0; num = (num - 1) / base) {
    *(word++) = alpha[(num - 1) % base];
}

Depending on how much you want to cram into the for loop (it can definitely go too far), you could even take it a step farther so that the for handles all of the iteration type stuff:

for (; num > 0; num = (num - 1) / base, ++word) {
    *word = alpha[(num - 1) % base];
}

---

Variable declaration

It looks like you're using C99 or newer, so nu doesn't need to be declared at the top of main. Instead, declare it in the tightest scope at the closest place to initial usage possible. In other words, nu should be declared in the for loop in which its used (for (ull nu = 0; ...; ...)).

---

Comments

These are both super minor:

/* "OSR43" was added to show that the letters of alpha
  are NOT in alphabetical order */

alpha has OSR34 in it not OSR43.

// word always contains null-terminator

I would put this inside of the loop instead of under calloc since I'm assuming the meaning is something like "Since word never decreases in length, it's always null terminated." Seeing it under calloc made my first thought "well of course a calloc allocated string is null terminated!" before realizing what you really meant.

---

sizeof

It's kind of iffy in situations this simple, but I like to use sizeof on the thing it's involved with instead of a type. In other words, I would have done char *word = calloc(30, sizeof(*word));. It looks a bit stupid in the simple case, but in complex code, it can be quite nice since it's impossible to change the type of the variable and forget to change the sizeof. It's kind of a DRY manifestation of sorts.

---

Performance

This code's working fine but I need to speed it up as much as possible. How do I do it?

I'm not much an optimization expert, so perhaps someone will come along with some magic, but as far as I can tell, conv isn't going to get meaningfully faster than it already is.

There is, fortunately a trivial 'optimization' is available with the output. In particular, puts, though simpler (puts(s) is equivalent to printf("%s\n", s)), is much faster than printf. Changing from printf to puts cuts the time the program takes to run on my computer from 8 seconds to 2.75 seconds.