This is the first article in a series of “interesting things I’ve found that I haven’t seen used elsewhere”. This will discuss a technique I used a couple of times in college when writing contrived software for CS and EE assignments.
One of the assignments I had required formatting numbers for output. For the algorithm I was using, it was important to know how many digits were in an integer number before I output it. This would make the formatting significantly easier than not knowing ahead of time. In thinking about how to do this, I realized there were several ways to do this. The first was to find modulo 10 and divide by 10 until the number was 0. This figured out the length, and found the individual parts of the number nicely, but it started from the least significant digit and worked up. I wanted something that would go the other direction.
I remembered my algebra class, and the log (base 10) function. I remembered that if log x = n, 10^n = x. In thinking about this, I realized that the ceiling of log x is the number of digits in x. In other words, since log 12345 =4.something, 12345 has 5 digits. This meant I could code something like the following:
int GetLength(int num) {
return ceil(log(num));
}
And could print out the digits of the number like this:
for(int j=GetLength(num); j>0; j--) {
cout < num / 10^j;
num \= 10^j;
}
So for base 10, it worked really well. The epiphany occurred when I needed to do the same thing with binary (base 2), octal (base 8), and hexadecimal (base 16) numbers. It turns out that this algorithm is extensible to arbitrary bases. To get that, we just have to make a couple of minor changes:
int GetLength(int num, int base) {
return ceil(log(num)/log(base));
}
int num = 12345;
int base = 2;
for(int j=GetLength(num, base); j>0; j--) {
cout < num / base^j;
num \= base^j;
}
There are a couple of special cases that you have to take care of when using this. Specifically:
- Negative numbers – you need to make sure to pass positive numbers into the digit counter. Logs of negative numbers aren’t real, and most math libraries don’t handle them well.
- Fractional numbers – for numbers with decimal places, this technique doesn’t work right. To make them work, you’d have to decide on how may decimal places you want, multiply by that number to start, then put the decimal point in the “right” place when emitting the value.
- Digit representation – for bases greater than 10, you’d need a mapping to handle the digits to output. In the example given above (with no digit mapping), the cout will emit a “13” instead of a “D” as expected for a hexadecimal conversion. Some kind of simple digit mapping scheme would have to be added to take care of this case.
