Logarithms is a mathematical concept that is used a lot in computer-science. In this post, let’s understand this concept and its applications in computer-science and beyond. We’ll talk about how logarithms help us in:
- Handling big numbers
- Applications in computer science algorithms which involve recursive division of input
- Denoting very small (miniscule) and very large numbers on a scale
- Compressing data
To introduce, if you know exponentials, then you know logarithms too. Because logarithms are nothing but the inverse of exponentials. For example, 2^4 = 16 and log2 (16) = 4. Logarithm of 16 with base 2 is actually 4 because log2 (16) = log2 (2^4) = 4 x log2 (2)= 4.
Simply put, logarithms are a way to write very big numbers. And, since logarithm helps reduce big numbers to small numbers, it helps us to do mathematics of big numbers in a simple way as below.
Handling large numbers
Suppose you want to multiply many numbers. Won’t you feel happy if there is a magical way to convert the Multiplication into Addition? If you want to do long divisions, the same magic converts Division into simple Subtraction. That magic is called Logarithm.
Logarithm converts exponentiation into simple multiplication. In the absence of a calculator, logarithm (and antilogarithm) is the most easiest method to do multiplication, division and exponentiation of large numbers.
Let us take an example. Suppose we have to multiply 387*523.
A logarithm table helps in writing 387 as 10^2.5877 and 523 as 10^2.7185.
387*523=10^2.5877 * 10^2.7185
The multiplication of two powers of 10 is just to add the exponents.
So the product is 10^(2.5877+2.7185)=10^5.3062.
An antilogarithm table tells us that 10^5.3062 = 202401.
Common Application in Computer-Science
Logarithms are taught in school mathematics because of its extensive applications in multiple fields. In computer-science, we usually use divide and conquer such as dividing the input of arrays, lists, trees, etc. We first sort the input and then divide the input repetitively until a desired goal is reached. This recursive division strategy is used in many popular algorithms like binary search, merge sort, quick sort, etc. In general, you have to do this “divide the input and start again” iterative process log(n) times, where ‘n’ is the number of entries in the list, and the logarithm is taken to the base 2. Most of the algorithms that involve dividing the input will have a complexity of O(log(n)). This is probably the most important and common application of logarithms in computer-science.
Denotion in Logarithmic Scale and Data Compression
Logarithms help us numerical data which is of a very wide range in a simpler manner. Let’s assume your data has very small values and then very big values, then showing such data in a regular rational number scale becomes very difficult as you will be able to see only one end of the data.
Lets look at what Logarithm does:
- Take any number and apply log to the base 10.
- Any number in the range 1 to 10 after applying log10 (1 to 10) is compressed to a value between 0 to 1.
- Any number between 10 to 100 is compressed to a value between 1 to 2.
If you follow the pattern you must have realised that this function comes in handy for compressing a range of numbers or reducing the scale and representing a range of numbers. Also, if you want to send large numbers, then it is advantageous to send the log of that large number as it reduces the bandwidth. For example, we know that any number can be expressed as a sum of the power of 2^N, and hence, instead of storing large numbers, we can just store the log of that number and achieve data compression in one way. These algorithms are logarithmic compression algorithms in computer-science and are usually used in music file compression and other applications.
Hope this is useful, thank you.