Have you ever thought about why you can’t see stars during the day? Do they somehow know when to dim themselves? How about why car headlights are so much brighter at night? Or why you can only hear a pin drop in a silent room? Does the pin make less noise just because somebody is talking? All of our body senses are like this. The brighter, or heavier, or louder, or sweeter, or smellier something is, then the more difficult it becomes to distinguish small changes. When a room is very quiet, then we can pick out the small sound that the pin makes. But a loud room needs a louder pin or we just won’t hear it. Our body is logarithmic.
This episode will prepare you for the next several episodes where we’re going to start talking about how to store information and which approach to take. Logarithms will help you understand how fast certain operations can be.
This is not a math lesson even though you might remember logarithms from a high school math course. I’m not going to make you memorize a bunch of formulas. Just one simple concept. It’s a concept so simple that it matches every one of our body senses. If you can understand that headlights are brighter at night, then you can understand this concept.
What’s the one concept you need to know? The logarithm of a number increases much slower than the number itself as the number gets bigger. That’s it. The audio goes into more details about this and gives you some examples. There’s a little multiplication involved but it’s trivial. You can listen to the full episode or read the full transcript below.
Transcript
Maybe you remember logarithms from high school math classes but that doesn’t matter. We’re not going to study math here. This episode will explain the basic concepts of what logarithms are and how you can use them.
The simple answer is that logarithms count multiplications. What does that mean? Well, two times two times two is eight so the logarithm base two of eight is how many times two must be multiplied by itself in order to get eight. This is three.
The important point for this discussion is that 3 is less than 8. In general, the logarithm of a number is usually much less than the number itself. You can see this if we take it further. Try multiplying 2 by itself 8 times and you’ll get 256. So the log base two of 256 is only 8. If we continue this and multiply by 2 another 2 more times, we get 512 and then 1024. So while the number that we’re calculating the log of went from 256 all the way to 1024, the log itself only went from 8 to 10.
This is the concept that you need to understand. The log of a number grows much slower than the number as that number increases. The reason this is important is because there are usually multiple approaches you can take when programming a solution to a problem. These different approaches are designed to work best under specific circumstances and knowing when to use one design vs. another could mean the difference between your program taking 10 seconds vs. taking 1024 seconds.
If your solution takes one second for each item that it needs to process and you’re looking for just one item out of 1024 items, then it’s going to take up to 1024 seconds. Sure you might be able to speed this up a bit with a faster computer. Maybe you can get it down to just 900 seconds.
But knowing this concept of logarithms might give you the clue you need to take a different approach that only needs the log of 1024 in seconds to complete. This solution will then only need 10 seconds. That’s a huge difference that completely leaves even the faster computer far behind.
How is it possible that one solution can be so much better than another? Let’s take a simple example of looking up a word in a dictionary. You want to find the word kangaroo. How would you begin? Well you could start on page one and scan through all the words and then go to page two, then three, etc. If your words are already in alphabetical order, then you might get to the b words maybe around page 200. Do you have to go through all the words in the book? Probably not. There should be a lot more words after kangaroo. But that doesn’t matter because maybe the next time, you’ll be looking for zoo. This is called a linear algorithm because you visit each word in order until you find the one you’re looking for.
If you have a small book that only has 10 words in it, then it may not matter. But how often do you think that will happen? Or maybe your program starts out with just a few items and then grows in popularity until the number of items slows your program to a crawl. If you only ever tested your program with 10 items, then you might miss this problem until it’s too late.
Before looking at a better solution, let’s take a moment to hear from our sponsor.
( Message from Sponsor )
Okay, we’re back and here’s a better solution that runs in time equivalent to the logarithm of the number of items. This is called a binary search. Again, if your items are already sorted and you also have the ability to navigate directly to specific items, then there’s no need to start at the beginning. Just think about how you would look up the word kangaroo in the dictionary. You don’t start on page one. You open the book somewhere near the middle. In other words, you just divided the number of words you need to look through in half. Once you know if the word is in the first half or the second half, you flip forward or backward so that you divide the remaining words in half again. You keep doing this and skipping over many words at a time as you get closer to the word you’re looking for.
Because you’re dividing the work need to complete your task in half each time, what you’re doing is walking back along that series of multiplications that I explained at the beginning. You can cut 1024 words into two sets of 512 words and then focus on just one of those. Then you cut the remaining 512 words into two sets of 256 words, etc. This process is just undoing the multiplications and how many times you can divide your problem is equal to the log of your original problem size. This is how you can search 1024 items with just 10 attempts. And anytime you can perform just 10 operations that span 1024 items, you’ll have a much faster program than visiting each one of the 1024 items individually.
I started this episode describing how our bodies are logarithmic. This whole topic is so natural for us that it’s amazing to me how complicated so many teachers make it seem. Let’s take our hearing for example. Our ears are designed to not just let us hear but to let us hear across a huge range of volume for very quiet to roaring crowds. Our ears manage this by expecting loud sounds when we’re surrounded by other loud sounds. This is a protection mechanism. If there’s a bunch of loud sounds, then chances are, there’s going to be other loud sounds. Our ears are protected somewhat from these loud sounds because we’re expecting them. This protection makes it harder to hear soft sounds though. Our ears are most susceptible to damage when everything is quiet and then there’s a sudden loud sound. The sudden sound arrives when our ears haven’t had time to adapt and aren’t expecting it and can cause loss of hearing. Our ears are logarithmic because they adapt to louder volumes at a rate that matches multiplication. And those bright headlights at night? That’s just like hearing a loud sound in a quiet room.