Covering All Our Bases

The solution to this problem is to use a different number base to represent our numbers. While our day-to-day number system uses base 10, if we want our hash function to cover 26 letters, we need to switch to base 26. This will ensure that each character’s hash code will be contained within one digit place.

If the previous paragraph made perfect sense to you, you can skip the rest of this section. But if you’re a little fuzzy on the details of number base systems, read on.

Take the number “ten.” Note how I spelled out this number using alphabetical characters. If I wanted to express this same number using numerical digits, I’d write “10.” However, this isn’t the only way to express the number “ten” using numerical digits. Before I move on to the alternatives, though, let me expound a bit on the “normal” system.

Base 10: The “Normal” System

The way we write numbers day to day is known as the decimal system, and is also called base 10. The idea behind base 10 is that we have 10 different numerical characters available to us, namely, the character set 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. No matter how large a number we want to express, we’re only able to use characters from this set.

So, to express the numbers zero through nine, I can do so using the 10 different numerical characters available to me. But how do I express the number “ten” itself? If I wanted to do this using one digit, I’d need an eleventh type of character. I could use fancy characters such as § or £, or alphabet letters, or even emojis if I so desired, but I’d need some sort of additional character beyond the digits 0 through 9.

But those characters don’t exist in the base 10 system. So we’re forced to express the number “ten” by using multiple digits, putting various digits in different places.

When we express the number “ten” as 10, we’re saying that there’s 1 ten, and 0 ones. The number 25 means that there are 2 tens and 5 ones.

The same goes for representing the number one hundred. We can express the number 99 using two digits, but when we want to express a larger number, we’ve simply run out of ways in which we can use only two digits. So, we move on to the hundreds place, and write out 100.

That’s how the base 10 system works. However, there can be a base system using any number, such as base 8, or base 26, or base 457. While we don’t generally use these other bases in day-to-day life, some alternative bases are used in specific applications, especially in the world of computers.

Base 2: The Binary System

One of the most well-known bases outside of base 10 is base 2. Indeed, base 2, also known as the binary system, or just binary, is the number system that computers understand best. Just as base 10 has ten different numerical characters, base 2 has two numerical characters. These characters are 0 and 1.

With this system, like most other systems, “zero” is written out as 0, and “one” is written out as 1. However, expressing the number “two” presents a hurdle, as we only have the characters 0 and 1 available to us. And so, we need to start using two digits. However, whereas with base 10, the second place from the right is the tens place, in base 2, the second place is the twos place. So here’s how we write out “two” in binary:

This means that there’s one “two” and zero “ones.” In other words, this is the number two.

To express the number three in binary, we’d write: 11. That is, there is one “two” and one “one.” When you have a two and you have a one, that makes three.

To express the number four, though, we have to introduce a third digit place, since the greatest number we can express using two digits is the number three. Now, this third place expresses how many fours there are. In other words, it’s the fours place. So, “four” is expressed as 100. Weird! In base 2, then, 100 is not “one hundred,” but “four.”

Here are a few more binary examples:

As mentioned, computers run primarily on base 2 since most computers store data in binary format. Whether it’s words, images, videos, or songs, under the hood, they’re all stored as binary numbers.

True story: I once bumped into an old friend, and when I told him that I’d become a software engineer, he asked me in all honesty whether I write code in zeroes and ones. I explained to him that—yes, of course—in fact, the keyboard I use has only two keys! He was quite impressed.

Base 16: The Hexadecimal System

Let’s move on to another system, namely, base 16, which is also known as the hexadecimal system. The funny thing about the hexadecimal system is that 16 is greater than 10. This means that we have sixteen different numerical characters available to us.

Now, that may seem daunting, given that in real life we don’t have numerical digits beyond 9. But here’s how we pull this off.

In hexadecimal notation, we have the following “numerical” characters available to us: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f. That is, a represents “ten,” and b represents “eleven,” and so on. The final character, f, represents “fifteen.” That’s right; in base 16, the letters a through f are numbers.

Of course, even base 16 has its limitations. When we want to express the number “sixteen,” we’ve run out of single characters to use. And so, we move on to the next place over, which is the sixteens place. In hexadecimal, 10 is “sixteen.” That is, there’s one sixteen, and zero ones.

The greatest number we can express with two digits is ff, which is fifteen in the sixteens place, and another fifteen in the ones place. This comes out to two hundred fifty-five, as (15 * 16) + 15 = 255.

To express two hundred fifty-six, though, we need to move over to the next place, which is the two-hundred fifty-sixes place. And so, in hexadecimal, 100 is what in decimal we call 256.

It can be a little hard to wrap one’s mind around this, but the hexadecimal number a2e6 is forty-one thousand, seven-hundred two. This is because:

You may have encountered hexadecimal numbers before. Very often, computer colors are expressed as hexadecimal numbers, otherwise known as hex codes. For example, #2ECC71 is a lovely shade of green.

As I said, you can make a base out of any number. However, some of the most commonly used ones beyond the decimal system, especially in computing, are base 2 (binary), base 8 (octal), and base 16 (hexadecimal).

Before concluding this section, I want to point out something that holds true for all base systems. No matter the base system, we use the following scheme to determine what number each digit place represents. In the following visual, the b is a variable that represents the base number. So for base 2, the b is 2, and for base 10, the b is 10:

That is, the right-most digit place in all base systems is b⁰. Now, any number raised to the power of zero is 1, so the right-most digit place is always the ones place. But as we move leftward, each place is raised to the next power. The table shows you how this plays out for bases 2, 10, and 16, but this pattern holds true for every base system.

Okay! We’ve covered the basics of base systems. Now, let’s see why this matters for the Rabin-Karp algorithm.