Monday, December 10, 2007

log base 2

It turns out that the number 1 reason people visit this blog is to calculate log base 2 of an integer. So here is log2 of 1 through 10, to 16 digits precision:

log2(1) = 0
log2(2) = 1
log2(3) = 1.584962500721156
log2(4) = 2
log2(5) = 2.321928094887362
log2(6) = 2.584962500721156
log2(7) = 2.807354922057604
log2(8) = 3
log2(9) = 3.169925001442312
log2(10) = 3.321928094887362

Note that log2(x) is defined for any x greater than zero. If you have a calculator than computes the natural logarithm (often denoted ln), then you can calculate log2(x) = ln(x)/ln(2). The same thing works with log base 10, i.e. log2(x) = log10(x)/log10(2).

But what does it mean?
log2(x) means the power you have to raise 2 in order to get x. For example, 22 = 4, so log2(4) is 2. Similarly, 23 = 8, so log2(8) = 3. It turns out that 21.58496 is very nearly 3, so log2(3) is roughly 1.58496.

Some cases deserve special mention. log2(2) = 1 because 21 is 2. log2(1) = 0 because by mathematical convention 20 = 1 (this holds not just for 2, but for any base). Finally, note that log2(0) is undefined, although some software will return -Infinity (which is the limit of log2(x) as x approaches zero).

What is it used for?

The logarithm is useful for a variety of purposes. One of the more common is when describing exponential growth or decay. For example, the time for a radioactive substance to decay to half its mass is called the half life. Similarly we can describe accelerating growth in terms of the doubling time. I previously applied this to the number of blogs tracked by Technorati.

In computing, log2 is often used. One reason is that the number of bits needed to represent an integer n is given by rounding down log2(n) and then adding 1. For example log2(100) is about 6.643856. Rounding this down and then adding 1, we see that we need 7 bits to represent 100. Similarly, in order to have 100 leaves, a binary tree needs log2(100) levels. In the game where you have to guess a number between 1 and 100 based on whether it's higher or lower than your current guess, the average number of guesses required is log2(100) if you use a halving strategy to bracket the answer.

Two much of nothing

Although I can't provide additional help to people with logarrhythmias, I hope this note is of some assistance.

Labels: , , , , , ,

7 Comments:

Blogger Zeno said...

Another good use of log 2 is related to those "intelligent design" advocates who like to prattle about "complex specified information" and "information theory". When an IDiot is in full spate about how information theory disproves evolution and provides evidence for an intelligent designer, sweetly ask him (it's usually a him), "So what's log 2 all about in that context?"

Then continue to smile during the subsequent arm-waving and ducking and weaving. I hypothesize that 19 times out of 20, the IDiot will be at a loss. (Now for some field work!)

6:59 PM, December 10, 2007  
Blogger Nick Barrowman said...

Yep. I think it's a case of seeing the splinter in someone else's eye, but not the log in one's own.

7:30 PM, December 10, 2007  
Blogger yeye said...

I am stuck with a log 2 equation, so any help is appreciated :

How to get x value for :

x - 8 lg(x) = 0

Thanx

6:10 PM, December 29, 2007  
Blogger Nick Barrowman said...

Well, by trial and error it's about 1.1, but to solve it properly you need to use an iterative algorithm like Newton's method. You can do it in Excel using Solver.

12:08 PM, December 30, 2007  
Blogger Piotr said...

yeye, be careful: there are two solutions, one ca. 1.12, and one ca. 35.

Once you know the ``ballpark figure'', a small 2 line program can do the rest.

8:19 PM, March 29, 2008  
Anonymous John said...

Interesting problem using natural logs. The equation ax = ln x has two solutions if a is sufficiently small, zero if too large, and one solution at the boundary. What is that boundary?

At the boundary, the slopes of both sides of the equation have to be equal -- otherwise, ln x would cross ax up and then cross back down. So at the boundary, a = 1/x.

That means, ln x = ax = a/a = 1, or x = e, and a=1/e.

10:08 PM, March 29, 2008  
Blogger Nick Barrowman said...

Thanks Piotr and John!

12:10 AM, March 30, 2008  

Post a Comment

Links to this post:

Create a Link

<< Home