Powers, Roots and Logarithms

Powers

Multiplication is repeated addition (3 × 4 is 4 + 4 + 4). A power is repeated multiplication:

The number being multiplied, 2, is the base. The small raised number, 5, is the exponent: it says how many times the base appears. Read 2^5 as "2 to the power 5" or "2 to the fifth". Two powers have their own names: x^2 is "x squared" (the area of a square with side x) and x^3 is "x cubed" (the volume of a cube).

Powers of 2 are the heartbeat of computing, because each extra bit doubles the number of patterns: 1 bit gives 2 patterns, 2 bits give 4, and n bits give 2^n. A few are worth recognizing on sight:

The exponent rules

All rules for powers follow from "count the factors". Worked example: what is 2^3 \cdot 2^4?

1. Write it out: (2 \cdot 2 \cdot 2) \cdot (2 \cdot 2 \cdot 2 \cdot 2).
2. Count the 2s: 3 + 4 = 7.
3. So 2^3 \cdot 2^4 = 2^7 = 128: when you multiply powers of the same base, you add the exponents.

The same counting gives the other rules, for any base a:

An IT use: a 2²⁰-byte buffer (1 MiB) holds 2^{20} / 2^{12} = 2^8 = 256 memory pages of 2¹² bytes (4 KiB) each. Subtracting exponents is faster than dividing 1,048,576 by 4,096.

Zero and negative exponents

What could 2^0 or 2^{-1} mean, if you cannot multiply 2 by itself zero or minus one times? Follow the pattern. Each step down in the exponent divides by 2:

So, for any base a that is not 0:

Negative powers of 10 are the small units: 10^{-3} = 1/1000 is milli, 10^{-6} is micro and 10^{-9} is nano. A latency of 2.5 ms is 2.5 \times 10^{-3} seconds, as in scientific notation.

print(2 ** 10, 2 ** 16, 2 ** 32)
print(2 ** 3 * 2 ** 4, 2 ** 7)      # same exponent rule, both 128
print((2 ** 3) ** 2, 2 ** 6)         # power of a power
print(2 ** 0, 2 ** -1, 10 ** -3)
print(0 ** 0)

1024 65536 4294967296
128 128
64 64
1 0.5 0.001
1

0^0 has no single agreed value in mathematics; Python, like most programming languages, defines it as 1, which is the convenient choice for counting and for formulas such as sums of powers.

Roots

A root undoes a power. The square root of x, written \sqrt{x}, is the non-negative number that gives x when you square it: \sqrt{144} = 12 because 12^2 = 144. Geometrically, it is the side of a square with area x.

Worked example: a Kestrel dashboard must show 400 meter tiles in a square grid. How many tiles per row?

1. A square grid with k tiles per row holds k × k = k² tiles.
2. So you need the number whose square is 400.
3. \sqrt{400} = 20: 20 rows of 20 tiles.

Other roots work the same way. The cube root \sqrt[3]{8} = 2 because 2^3 = 8, and in general \sqrt[n]{x} is the number whose n-th power is x. Roots can also be written as fractional exponents, which is how you compute them in code:

This fits the exponent rules: (x^{1/2})^2 = x^{1/2 \cdot 2} = x^1 = x.

Most square roots are irrational: \sqrt{2} = 1.41421\dots never ends (see irrational numbers). A negative number has no real square root, because every real number squared is zero or positive.

import math

print(math.sqrt(2))
print(math.sqrt(144), 144 ** 0.5)
print(math.isqrt(1000))
print(8 ** (1 / 3))
print(-8 ** (1 / 3))
print((-8) ** (1 / 3))

1.4142135623730951
12.0 12.0
31
2.0
-2.0
(1.0000000000000002+1.7320508075688772j)

1. math.sqrt and ** 0.5 both return a float, even when the root is a whole number.
2. math.isqrt(1000) is the integer square root: the largest whole number whose square is at most 1000. It is exact for integers of any size.
3. -8 ** (1 / 3) is −2.0 only because of the order of operations: Python computes -(8 ** (1 / 3)).
4. (-8) ** (1 / 3) gives a complex number: a negative number raised to a non-integer power gives a complex result in Python, even when a real cube root exists. Also, 1/3 cannot be stored exactly, so float roots are approximations.

Logarithms

A power asks "what is 2 to the 10th?" (1,024). A logarithm asks the reverse: "2 to the what is 1,024?" The answer, 10, is the logarithm of 1,024 in base 2:

Read \log_2 1024 as "log base 2 of 1024". So a logarithm is an exponent: the one you have to put on the base to get the number. Worked examples:

1. \log_2 8: 2 to the what is 8? 2 × 2 × 2 = 8, so \log_2 8 = 3.
2. \log_{10} 1000: 10 × 10 × 10 = 1000, so \log_{10} 1000 = 3: the number of zeros.
3. \log_2 1 = 0, because 2^0 = 1, and \log_2 \tfrac{1}{2} = -1, because 2^{-1} = \tfrac12.
4. \log_2 1000 lies between 9 and 10, because 1000 lies between 2^9 = 512 and 2^{10} = 1024. (It is about 9.97.)

A power with a positive base is always positive, so the logarithm of 0 or of a negative number does not exist. Python raises an error:

import math

print(math.log(1))
print(math.log(0))

0.0
ValueError: math domain error

Because logarithms undo powers, the graph of y = \log_2 x is the graph of y = 2^x mirrored in the diagonal line y = x: every point (a, b) on one curve becomes (b, a) on the other.

The logarithm rules

Since logarithms are exponents, the exponent rules turn into logarithm rules. Multiplying numbers adds their exponents, so it adds their logarithms:

These rules are why logarithms were invented (in the early 1600s): they turn multiplication into addition. You still meet that idea in the decibel scale, below.

Base 2: the logarithm of computing

The binary logarithm, \log_2 n, counts how many times you can halve n before you reach 1. For 1,024: 512, 256, 128, 64, 32, 16, 8, 4, 2, 1, which is ten halvings, and \log_2 1024 = 10. Halving and doubling are everywhere in computing, so this logarithm is too.

How many bits do you need?

With b bits you can number 2^b things. The reverse question, "how many bits do I need for n things?", is a logarithm, rounded up with the ceiling function:

Worked example: Tomasz needs host numbers for 500 devices in one subnet.

1. 2^8 = 256 is too small; 2^9 = 512 is enough.
2. So \log_2 500 lies between 8 and 9 (about 8.97), and rounding up gives 9 bits.
3. In subnetting, two of the 512 addresses are reserved, leaving 510 hosts: still enough. 9 host bits means a prefix of 32 − 9 = /23 (see subnetting).

In Python, an integer's bit_length() gives the same answer exactly, without floating-point rounding: the numbers 0 to n − 1 need (n - 1).bit_length() bits.

# Bits needed to number n things (0 .. n-1)
for n in (2, 8, 500, 1000, 65536):
    print(n, (n - 1).bit_length())

2 1
8 3
500 9
1000 10
65536 16

Halving: search and trees

Binary search looks up a value in a sorted list by checking the middle and throwing away the half that cannot contain it. Each step halves what is left, so a sorted list of a million customer numbers needs at most 20 comparisons, because 2^{20} is just over a million:

import math

print(math.log2(1024))
print(math.log10(1_000_000))
print(math.log(math.e))
print(math.log(8, 2))
print(math.log2(1_000_000))
print(math.ceil(math.log2(1_000_000)))

10.0
6.0
1.0
3.0
19.931568569324174
20

A list a thousand times longer, a billion items, needs only about 30 steps. That slow growth is what O(\log n) means in Big O notation, and it is why database indexes, which are B-trees, find a row among millions in a handful of steps. Password strength is also measured with a binary logarithm: a password of 12 characters chosen at random from 62 letters and digits has 12 \cdot \log_2 62 \approx 71 bits of entropy (see passphrases and entropy).

Other bases: 10 and e

Two other bases are common enough to have their own notation:

• Base 10, \log_{10} x: the "common logarithm". It counts powers of ten, so it tells you roughly how many digits a number has, and it is the base behind decibels.
• Base e, \ln x: the natural logarithm, with base e \approx 2.71828. It appears wherever growth is continuous (interest, population, radioactive decay) and in calculus, where it has the simplest rules; you will meet it on the derivatives page and in machine learning loss functions.

All logarithms are related by a constant factor. To compute a logarithm in any base b from one you do have, use the change of base rule:

Because \log_2 n and \log_{10} n differ only by a constant factor (about 3.32), Big O notation writes just O(\log n): the base does not change how the cost grows. Everywhere else, the base matters, and this site always writes it (see "log" without a base).

import math

# log base matters: Python's math.log is the natural logarithm
print(math.log(1000), math.log10(1000), math.log2(1024), math.log(1024, 2))
# change of base: log base 2 of 3 = ln 3 / ln 2
print(round(math.log(3) / math.log(2), 6), round(math.log2(3), 6))

6.907755278982137 3.0 10.0 10.0
1.584963 1.584963

Orders of magnitude

An order of magnitude is a factor of ten. Two quantities "differ by three orders of magnitude" when one is roughly a thousand times the other. Thinking this way helps you spot impossible numbers quickly: if a report says a customer used 40,000 kWh in a month, while a typical household uses a few hundred, the value is off by two orders of magnitude, and you should look for a unit or decimal-point error.

The order of magnitude of a number is the largest power of 10 that is at most the number: \lfloor \log_{10} x \rfloor. For 0.0025 it is −3 (because 0.0025 = 2.5 × 10⁻³); for 400,000 it is 5.

import math

# Order of magnitude: the power of 10 just below the value
values = [("response time in s", 0.0025), ("tariff in EUR/kWh", 0.27),
          ("smart meters", 400_000), ("readings per day", 96 * 400_000)]
for name, value in values:
    print(f"{name:20} {value:>12,} 10^{math.floor(math.log10(value))}")
# decibels: +3 dB is about double the power, +20 dB is 100 times
print(round(10 * math.log10(2), 2), round(10 ** (20 / 10)))

response time in s         0.0025 10^-3
tariff in EUR/kWh            0.27 10^-1
smart meters              400,000 10^5
readings per day       38,400,000 10^7
3.01 100

Logarithmic scales

When values range over many orders of magnitude, a normal axis squeezes the small ones into a line at the bottom. A logarithmic scale spaces 1, 10, 100 and 1,000 equally, so a response time of 5 ms and one of 5 seconds are both visible on the same monitoring graph. Many dashboard tools offer a "log" option on the y-axis for exactly this reason.

The decibel (dB) is a logarithmic unit for ratios of power: 10 \cdot \log_{10}(P_2 / P_1). Doubling the power adds about 3 dB, and a factor of 100 adds 20 dB, as the last line of the example shows. Wi-Fi signal strength in dBm uses this scale, which is why a signal of −70 dBm is far weaker than one of −50 dBm (see signal and interference).