[See your text, page 56.]

By definition, the logarithm function is the inverse of the exponential function, so that

One says: ``y is the logarithm of x to base b,'' or ``y is the log base b of x.''   Stated another way, log_bx (also known as y) is the exponent you raise b to in order to get x.   Thus

Logs base 2 are the favorite of computer scientists, because binary numbers are used so often and because many algorithms involve dividing things in two. Of course, the official notation for log base 2 is: log₂ x. Your book uses lg x, but this is not standard notation. The only standard notation of this sort is to write ln x for log_e x (In fact, Wikipedia says:

log₂ n is frequently written ld n, or lg n, although the ISO specification is that it should be lb (n), lg (n) being reserved for log₁₀ n.

ld, lg, and lb are all a muddle of non-standard notations, in spite of the ISO specs.)

So y = log₂ x means the same as 2^y = x. Another way to say this is that a logarithm base 2 of x is an exponent, namely it is the exponent you raise 2 to in order to get x. In symbols: if y = log₂ x, then x = 2^y = 2^log₂ x.   In particular 2¹⁰ = 1024 means the same as log₂ 1024 = 10. Notice that 2^y > 0 for all y and inversely log₂ x is not defined for x <= 0.

If you start with a positive integer n and repeatedly divide it by 2 (truncated integer division), then after roughly log₂ n divisions, you get to 1 and then to 0. This fact often comes up in computer algorithms since we often divide the size of the problem by 2.

Here are two tables of logs, base 2 and base 10:

Here are a few other formulas involving logarithms:

Equation (5) above is used to calculate a^b when only functions base e are available. (I used "exp(x)" above instead of "e^x" to keep the notation simpler.)

Similarly, equation (6) above allows one to find the value of log_b(a). Here are further examples of the use of (6), including your text's nasty expression on page 176 and in Figure 7.4: log_10/9(n):

(Oops! At the right end of the second line above, it should be log_e instead of log₂.)

Some calculators, as well as languages like Java, do not directly support logs base 2. Java does not even support logs base 10, but only logs base e, the ``natural'' log. However, a log base 2 is just a fixed constant times a natural log, so they are easy to calculate if you know the ``magic'' constant. The formulas are:

Here is the magic constant: log_e(2) = 0.69314 71805 59945 30941 72321, or 1 / log_e(2) = 1.44269 50408 88963 40735 99246. (Similarly, log₂ x = log₁₀(x) / log₁₀(2), and log₁₀(2) = 0.30102 99956 63981.)

Thus log₂10000 = 13.28771238, so it takes 14 bits to represent 10000 in binary. (In fact, 10000₁₀ = 10011100010000₂.) Exact powers of 2 are a special case: log₂1024 = 10, but it takes 11 bits to represent 1024 in binary, as 10000000000.

Similarly, log₁₀(x) gives how many decimal digits are needed to represent x.