Logarithm shmogarithm

What is a logarithm?

In high school, I had this spiffy Texas Instruments calculator (as did all of my classmates) and in its plethora of buttons was one labeled ‘log’. I can almost say with 100% certainty that I never touched this button.

Logarithm and algorithm sound a lot alike — are they the same thing? Not quite. An algorithm is a set of instructions, or procedure, used to solve a mathematical problem. A logarithm tells us the exponent to which a number (the base) must be raised in order to produce a certain value. So, they aren’t the same, but are closely related.

We are all familiar with exponential functions like the one below:

2³ = 8  
// "two to the power of three is eight"
// or 2 * 2 * 2

Let’s reverse the logic for a second and ask, “ 2 to what power equals 8?” The answer is 3. We can think of a logarithm as the inverse of an exponential function — as a quantity representing the power to which a fixed number (the base) must be raised to produce a given number. An exponential equation isolates the power whereas a logarithm isolates the exponent. The same equation, expressed logarithmically:

log2(8) = 3
// "log base two of eight is three"
logx(y) = z      is the same as...       x^z = y
// x is the base
// y is the power
// z is the exponent

There are a few bases that are of particular importance: base 2, base e and base 10.

Base 2 is known as the binary logarithm. This base occurs when we use things like binary search (repeated halving) or doubling.

Base e where e refers to the mathematical constant 2.71828…Logarithms to the base e are called natural logarithms and are written as:

ln x     or...   loge(x)
// log ex to base e

The inverse of ln x is exp(x) = e ^x also known as the exponential function on that Texas instruments.

Base 10, or common logarithm, was used heavily in pre-Texas Instrument days and represents the numbering of our decimal system. Each digit in a number based on its position can have a place value that is one of 10 possibilities. These place values are based on powers of 10: hundredths, tenths, tens, hundreds, thousands.

Why is this important? Well, for me, it wasn’t…until about six months ago when I decided to be a web developer. Now, algorithms are everywhere and where there’s an algorithm there’s sure to be a logarithm. Logarithms are of particular importance to the programming world with respect to the algorithms we choose when writing larger scale applications.

Exponential functions grow at an obscenely fast rate, which makes them highly inefficient as well as an unlikely candidate when dealing with very large numbers. Logarithmic functions like binary search trees bode well in such situations by repeatedly cutting the data set in halves.

Hopefully, this provided a nice introduction to logarithms and their possible applications. Stay tuned for coding examples as I dive deeper into the world of algorithms. Cheers.