>

   
APPENDIX: A Tutorial On Logarithms

Understanding the Log Function. In the mathematical operation of addition we take two numbers and join them to create a third:

1 + 1 = 2. (21)

We can repeat this operation:

1 + 1 + 1 = 3. (22)

Multiplication is the mathematical operation that extends this:

$$3 \times 1 = 3.$$ (23)

In the same way, we can repeat multiplication:

$$2 \times 2 = 4.$$ (24)

and

$$2 \times 2 \times 2 = 8.$$ (25)

The extension of multiplication is exponentiation:

$$2 \times 2 = 2^2 = 4.$$ (26)

and

$$2 \times 2 \times 2 = 2^3 = 8.$$ (27)

This is read ``two raised to the third is eight''. Because exponentiation simply counts the number of multiplications, the exponents add:

$$2^2 \times 2^3 = 2^{2+3} = 2^5.$$ (28)

The number `2' is called the base of the exponentiation. If we raise an exponent to another exponent, the values multiply:

$$\left( 2^2 \right) ^3 = 2^2 \times 2^2 \times 2^2 = 2^{2 + 2 + 2} = 2^{2 \times 3} = 2^6.$$ (29)

The exponential function y = 2^x is shown in this graph⁴:

Now consider that we have a number and we want to know how many 2's must be multiplied together to get that number. For example, given that we are using `2' as the base, how many 2's must be multiplied together to get 32? That is, we want to solve this equation:

2^B = 32. (30)

Of course, 2⁵ = 32, so B = 5. To be able to get a hold of this, mathematicians made up a new function called the logarithm:

$$\log_{2}32 = 5.$$ (31)

We pronounce this as ``the logarithm to the base 2 of 32 is 5''. It is the ``inverse function'' for exponentiation:

$$2^{\log_{2}a} = a$$ (32)

and

$$\log_2(2^a) = a.$$ (33)

The logarithmic function $y = \log_2 x$ is shown in this graph⁵:

This graph was created by switching the x and y of the exponential graph, which is the same as flipping the curve over on a 45 ${}^{\circ}$ line. Notice in particular that $\log_2(1)=0$and $\log_2(0)=-\infty$.

The Addition Law. Consider this equation:

$$\fbox{ $2^{a + b} = 2^a \times 2^b$ }$$ (34)

which is just a generalization of equation (28). Take the logarithm of both sides:

$$\log_2{2^{a + b}} = \log_2 \left( {2^a \times 2^b} \right)$$ (35)

Exponentiation and the logarithm are inverse operations, so we can collapse the left side:

$$a + b = \log_2 \left( {2^a \times 2^b} \right)$$ (36)

Now let's be tricky and substitute: $\log_2 x = a$and $\log_2 y = b$:

$$\log_2 x + \log_2 y = \log_2 \left( {2^{\log_2 x} \times 2^{\log_2 y}} \right)$$ (37)

Again, exponentiation and the logarithm are inverse operations, so we can collapse the two cases on the right side:

$$\fbox{ $\log_2 x + \log_2 y = \log_2 \left( x \times y \right)$ }$$ (38)

This is the additive property that Shannon was interested in.

The ``Pull Forward'' Rule. From equation (32):

$$a = 2^{\log_{2}a}.$$ (39)

Raise both sides to the u:

$$a^u = \left(2^{\log_{2}a}\right)^u.$$ (40)

Now, we can combine the exponents by multiplying, as in (29):

$$a^u = 2^{u\log_{2}a}.$$ (41)

Finally, take the log base 2 of both sides and collapse the right side:

$$\fbox{ $\log_2 a^u = u\log_{2}a$ }$$ (42)

This can be remembered as a rule that allows one to ``pull'' the exponent forward from inside the logarithm.

How to Convert Between Different Bases. Calculators and computers generally don't calculate the logarithm to the base 2, but we can use a trick to make this easy. Start by letting:

$$x = \log_{z} a / \log_{z} b$$ (43)

Rearrange it as:

$$\log_{z} a = x \log_{z} b.$$ (44)

Now use a ``reverse pull forward'' (!):

$$\log_{z} a = \log_{z} b^x$$ (45)

and drop the logs:

a = b^x. (46)

Now take the log base b:

$$\log_b a = \log_b b^x.$$ (47)

This simplifies to:

$$\log_b a = x.$$ (48)

But we know what x is from equation (43):

$$\log_b a = \log_{z} a / \log_{z} b$$ (49)

The conversion rule to get logarithms base 2 from any base z is:

$$\fbox{ $\log_2(a) = \log_z(a)/\log_z(2)$ }$$ (50)

Notice that since the z does not appear on the left hand side it doesn't matter what kind of logarithm you have available, because you can always get to another base using this equation! Try this example on your calculator:

$$\log_2(32) = \frac{\log_{ \mbox{\scriptsize whatever!} }(32)} {\log_{ \mbox{\scriptsize whatever!} }(2)}.$$ (51)

You should get `5'.

Tricks With Powers of 2. In calculus we learn about the natural logarithm with base $e = 2.718281828459045 \ldots$⁶ Calculations with this base can easily be done by a computer or calculator, but they are difficult for most people to do in their head.

In contrast, the powers of 2 are easy to memorize and remember:

choices	bits
M	B
1	0
2	1
4	2
8	3
16	4
32	5
64	6
128	7
256	8
512	9
1024	10

where 2^B = M and $\log_2 M = B$.

We can use this table and a trick to make quick estimates of the logs of higher numbers. Notice that

$$2^{10} = 1024 \approx 1000 = 10^3.$$ (52)

So to take the log base 2 of $4 \times 10^6$, we think:

$$\log_2 (4 \times 10^6) \log_2(4) + \log_2(10^6)$$ = (53)

$$2 + \log_2(10^3 \times 10^3)$$ = (54)

$$2 + \log_2(10^3) + \log_2(10^3)$$ = (55)

$$\approx 2 + \log_2(2^{10}) + \log_2(2^{10})$$ (56)

$$\approx$$ 2 + 10 + 10 (57)

$$\approx$$ 22 (58)

The actual value is 21.93.