Thursday, August 23, 2012

Application of Logorithm

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.

No comments: