CodingHighway     Archive     Books     Resume     About

Formatting your mind for base b

There are 10 types of people in this world, those who understand binary and those who don't


I want to refresh everybody's memory and talk a little bit about base-10 to base-b conversion.

Most people will be familiar with conversion to binary, but sometimes it starts to get really messy when fractional numbers come into play.

For the record: I will not be covering how to convert base-10 integers to base-2, or any other base. I'm going to focus in fractional numbers.

How would you implement a function that receives a fractional number in the interval [0..1[ in base-10 and converts it to a char array representing it in base-b?

It may sound complicated at first, but it's not. Remember this algorithm?

  • Multiply by 2
  • If there's an integer part, it's a 1-bit
  • Otherwise, it's a 0-bit
  • Subtract the integer part
  • If 0, stop. Otherwise, go back to 1

This is the basic way to convert a base-10 fractional number in [0..1[ into its base-2 variant.

Let's see a few examples.

Example 1

In this example, let's take the value \(0.125\).

In each row, we multiply the previous row's fractional part by 2. The first row corresponds to \(0.125 \times 2 = 0.25\).

Fractional part Integer part
0.25 0
0.5 0
0 1

The algorithm stops when the fractional part is \(0\). The fractional representation of \(0.125\) is then obtained by concatenating the integer parts (2nd column). So, \(0.125\) in binary is \(0.001\).

Example 2

Let's try a different value: \(0.2\)

Fractional part Integer part
0.4 0
0.8 0
0.6 1
0.2 1
0.4 0

Wooohha! We got a loop! Cool! This is an infinite fraction in binary. \(0.2\) in binary is \(0.00110011...\)

This drives us into fun fact number 1 about base-b:

Some fractions can be finite in one base and infinite in another

Pretty cool, huh?

The jump to base-b

If instead of base-2 we wanted to convert to base-b, all we have to do is multiply by b in each step instead of multiplying by 2. Of course, if you're working on base-b, then digits on that base go from 0 to b-1.

But the question comes: Why does this work? Where does this algorithm come from?

It's simple maths. When using base b, any fractional part N of a number is represented as:

$$ N = a_1b^{-1} + a_2b^{-2} + a_3b^{-3} + a_4b^{-4} + \dots + a_Xb^{-X} $$

The representation of N in base b is the sequence of coefficients \(a_i\). In the first example, because \(N = 0.125 = \frac{1}{8} = 2^{-3}\), we get \(001\) for the fractional part: \(0*2^{-1} + 0*2^{-2} + 1*2^{-3}\).

So, you want to find out the values of \(a_1\), \(a_2\), \(a_3\), etc.

What happens if we multiply the base b representation of N by b? We get:

$$ bN = a_1 + a_2b^{-1} + a_3b^{-2} + a_4b^{-3} + \dots $$

This is beautiful, genial and extremely simple. By doing this, we get an integer \(a_1\), which is some number between \(0\) and \(b-1\), and the rest of the coefficients make up the fractional part.

In other words, the integer part of \(b \times N\) is the next coefficient. And we just keep doing this until there is no fractional part anymore, or up to the point where we can see a loop.

The code

Here's teh codez:

char get_numberChar(int base, int n) {
  int a = n + '0';
  if (a >= '0' && a <= '9')
    return a;
  return 'a'+n-10;
}

void to_baseb(int b, float number, char converted[], int lim, int index) {
  int ipart;
  if (index == lim-1 || number == 0) {
    converted[index] = '\0';
    return;
  }
  number *= b;
  ipart = (int) number;
  number -= ipart;
  converted[index] = get_numberChar(b, ipart);
  to_baseb(b, number, converted, lim, index+1);
}

void base_b_converter(int b, float number, char converted[], int lim) {
  if (b > 26 || b <= 0) {
    printf("Invalid base!\n");
    return;
  }
  if (number == 0) {
    converted[0] = '0';
    converted[1] = '\0';
    return;
  }
  to_baseb(b, number, converted, lim, 0);
}

And that's how it's done.

Example usage:

int main() {
  char c[100];
  float f = 0.465897654154515;
  base_b_converter(20, f, c, 10);
  printf("%s\n", c);
  return 0;
}

This will print 9673c9j09, which, according to my calculator, is \(0.4658976555\).

Unfortunately, we cannot explore this down to the level of pure maths, because of the computer precision problems. Things like \(\frac{1}{3} = 0.33333333\dots\) in base-10, which is \(0.0101010101\dots\) in base-2, do not yield a loop. The problem is that the more we multiply by 2 and the more integer parts we remove, the smaller the number gets, and even though theoretically it never reaches 0, in a finite bits representation inside a computer, it eventually reaches 0, because it is so small that the computer can't represent it anymore, so we don't get a loop. Still, it's a good exercise. I tried this with \(0.47\) as well. \(0.47\) is also an infinite fraction in base-2; it is represented as:

$$ 0.0111100001010001111010111(0111100001010001111010111) $$

But, even with lim = 100 in my implementation, the best I can get is this:

$$ 0111100001010001111010111 $$

Which, for the record, is pretty good. According to my calculator, this is \(0.4699999988\).

By the way, for the sake of simplicity, the code assumes that b is less than \(36\), so that each character in the alphabet directly maps to the range [10..35].

And remember, there's no reason to be scared of numbers in other bases.