Binary Logarithm
Relationship with computers
13 May 2017
View Comments
#binary
#logarithm
#computer
#algorithm
 |
In a regular daily life, the log of something refers to log base of 10 because we normally use Decimal system. There is a good controversy of using Dozenal System (Base 12) which might be covered in the future blog, but not for this post. For this post, I want to cover why binary logarithm is very important in computing science world. Logarithm itself is a very interesting.
Fundamentals
It is very important (especially with large data set) to plan how we are going to write algorithm for a specific problem. Binary Logarithm algorithm basically divides the problem by 2 each time it compares data and eventually arrive to a solution. For example, let’s consider single-game elimination tournament in sports. Binary Logarithm of total number of games will get us number of rounds needed to become a winner. Let’s say there are 32 teams total then we need to win log2(32) = 5 rounds in a row to become a winner.
Logarithm Law
There are multiple laws for computing logarithms such as product, quotient, power, and root. Out of these, I would pick “power” to be the most important one. It is probably most related to how we measure our algorithm in computer science. For example, let’s say you have total elements of 1024 items. When you have binary logarithm algorithm, your algorithm speed is measured at 10 because 2 to the power of 10 = 1024. Well then what is 1024 in Logarithm of base 4? 4 to the 5 is 1024. So it is 5. When we say in Big O notation of binary search as Log of n, it really means Log “base 2” of n since binary search is basically dividing with 2 options algorithm each time search value is being compared with data.
Power of 2 table
We peeked into how logarithm’s work in terms of “power” law. But wait a minute.. This just means if we remember the first basics of power of 2 table, it will be easy to measure the complexity of the computer algorithm in general. So if we remember, 2 to the 10 is 1024, it’s easy to calculate that we need 10 comparisons to achieve something for total of 1024 elements. If we think about looking at data sequentially, in the worst case scenario, it will need to look into every items which is 1024 comparisons. However, with binary logarithmic algorithm, with the worst case scenario, we need 10 comparisons for 1024 items.
 |
| Value in power of 2 | Approximation |
|---|---|
| \({2^1{^0}}\) | one thousand |
| \({2^2{^0}}\) | one million |
| \({2^3{^0}}\) | one billion |
| \({2^4{^0}}\) | one trillion |
| \({2^5{^0}}\) | one quadrillion |
| \({2^6{^0}}\) | one quintillion |
\({2^4{^0}}\) is even a huge number (~1 trillion). You probably heard of that if you were to fold a piece of paper in half 42 times, it would reach the moon. If you have standard paper which is about 0.1 mm thick folding it 42 times meaning, 0.1 mm * \({2^4{^2}}\) (fold half 42 times) = 439,804,651,110 mm which is like 439,804 km which goes beyond the average distance to the moon from earth which is about 384,400km. I actually remember arguing with a colleague on this. My colleague kept telling me it is always possible to reach moon when paper is folded 42 times. I told him it has to be a certain thickness. Well thickness of a paper obvious matters but he is correct saying that we would reach to the moon at the standard paper thickness. Just to be clear, if the thickness of the paper is half of the standard paper, say 0.05mm instead, then 0.05 * \({2^4{^2}}\) = 219,902,325,555 mm = 219,902 km which is shorter distance compare to 384,400km. So we won’t reach the moon!
