Binary Logarithm

Relationship with computers


13 May 2017 View Comments
#binary #logarithm #computer #algorithm

Image Source: Wikimedia Commons
Image Source: Wikimedia Commons

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.

First few power of 2
First few power of 2
Value in power of 2 Approximation
one thousand
one million
one billion
one trillion
one quadrillion
one quintillion

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 * (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 * = 219,902,325,555 mm = 219,902 km which is shorter distance compare to 384,400km. So we won’t reach the moon!

Share this post

Me

I am a passionate programmer working in Vancouver. I strongly believe in art of algorithms and together with it to write clean and efficient software to build awesome products. If you would like to connect with me, choose one from below options :) You can also send me an email at