TIL - Horner's method: An algorithm for reading a number written in any positional numeral system.

There is a universal algorithm for evaluating numbers written in any positional numeral system. Once you know the base and can convert each symbol into its corresponding digit, the algorithm is simply:

result = result * base + digit;

Suppose you are reading a number in base 10 say 1234:

Let's decompose in exponentials from left to right:

1234 = 1*10³ + 2*10² + 3*10¹ + 4*10⁰

Now we factor 10:

10(1*10² +2*10¹+3)+4

And again:

10(10(1*10+2)+3)+4

Finally:

10(10(10(1) +2)+3+4

Alternatively:

((1×10+2)×10+3)×10+4

This works for any positional numeral system. Changing 2 to 10 parses decimal numbers, changing it to 16 parses hexadecimal numbers (after converting A–F to 10–15) and so on.

SAMPLE: A C version to turn a binary into decimal using Horner's method:

#define TEST "11011"

#define MAXWORDLENGTH 5

uint32_t bin2dec(const char *word)

{

    uint32_t result = 0;

    for (size_t i = 0; i < MAXWORDLENGTH; i++)

    {

        result = result * 2 + (word[i] - '0');

    }

    return result;

}

- Note that we subtract the ASCII value 48 to 0 so that 0 becomes 0 and 1 becomes 1.