Calculating entropy

I was reading something and it mentioned in passing that you can convert from base 10 to base 2 by simply dividing by the base to convert to, and then collecting the remainder digits. So for base 10 to base 2 conversion you simply keep dividing by two and collecting the remainders. I'd never heard of that before, so I had to try it out in code immediately, as it seemed like magic. I spent a few minutes coming up with some code to test it out and yes, it works! I then went off on a bit of a tangent...

It seems like the sort of thing that should be doable in 3 lines or so, but my version is a bit long-winded. It also seems like it should be amenable to recursion too. Anyway, here's some noddy code:

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

// size hardcoded at 8 bits

void to_binary (int *bin_array, unsigned int num)
{
    unsigned int base = 2;
    unsigned int res, rem;

    int i=7;
    while (num > 0)
    {
        res = num / base;
        rem = num % base;

        bin_array[i] = rem;
        i--;
        num = res;
    }

}

void clear_array (int *array)
{
    for (int i = 0; i < 8; i++)
    {
        array[i] = 0;
    }

}

void print_array (int *array)
{
    for (int i = 0; i < 8; i++)
    {
        printf("%d", array[i]);
    }
    printf("\n");
}

int main (int argc, char **argv)
{
    int bin_array[8];

    clear_array(bin_array);
    to_binary(bin_array, 19);
    print_array(bin_array);

    return 0;
}

It's then possible to take this silliness a step further and add a little tweak to tell us how many bits are required to code a number. This is the entropy of a number:

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

#define BITS 8

void to_binary (int *bin_array, unsigned int num)
{
    unsigned int base = 2;
    unsigned int res, rem;

    int i=BITS-1;
    int entropy_bits = 0;
    while (num > 0)
    {
        res = num / base;
        rem = num % base;

        bin_array[i] = rem;
        i--;
        num = res;
        entropy_bits++;
    }
    printf("Entropy Bits: %d\n", entropy_bits);
}

void clear_array (int *array)
{
    for (int i = 0; i < BITS; i++)
    {
        array[i] = 0;
    }

}

void print_array (int *array)
{
    for (int i = 0; i < BITS; i++)
    {
        printf("%d", array[i]);
    }
    printf("\n");
}

int main (int argc, char **argv)
{
    int bin_array[BITS];

    if (argc == 1)
    {
        printf("Example usage: to_binary 123\n");
        exit(-1);
    }

    clear_array(bin_array);
    to_binary(bin_array, atoi(argv[1]));
    print_array(bin_array);

    return 0;
}

A few runs of the program are shown here:

bash-3.2$ ./a.out 63
Entropy Bits: 6
00111111
bash-3.2$ ./a.out 244
Entropy Bits: 8
11110100
bash-3.2$ ./a.out 19
Entropy Bits: 5
00010011
bash-3.2$

There is a mathematical formula for calculating entropy. The following code shows this formula in action:

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

int main (int argc, char **argv)
{

    if (argc == 1)
    {
        printf("Example usage: entropy 123\n");
        exit(-1);
    }


    double x = atof(argv[1]);;

    double log2x = log10(x)/log10(2);

    printf ("entropy: %f\n", log2x);

    return 0;
}

You can then compare the output between the two programs:

bash-3.2$ ./to_binary 123
Entropy Bits: 7
bash-3.2$ ./entropy 123
entropy: 6.942515
bash-3.2$

You can see there is a slight mathematical 'glitch'. This can be fixed with the ceil() function, which basically rounds up to the nearest integer:

double log2x = ceil(log10(x)/log10(2));

Ah, but hang on, it looks like the formula might be wrong:

bash-3.2$ ./to_binary 4
Entropy Bits: 3
00000100
bash-3.2$ ./entropy 4
entropy: 2.000000
bash-3.2$

We'll need to look into that a bit more ...

But it can be fixed easily enough like this:

double log2x = ceil(log10(x+1)/log10(2));

So, as per Shannon's law, the entropy of x is log2(x), and you use the formula to work that out.