Volume 1: Foundations to Precalculus · Part I: Foundations

Chapter 3. Exponents, Roots, and Scientific Notation

Chapter map: an exponent is shorthand for repeated multiplication, and from that one idea everything else in this chapter is derived rather than memorised: the laws of exponents, why \(a^0 = 1\), why a negative exponent means a reciprocal, why a fractional exponent means a root. We then put powers to work — simplifying surds, writing very large and very small numbers in scientific notation, reasoning in orders of magnitude, and living in the powers-of-two world of computer memory. We finish with a first look at exponential growth and its inverse, the logarithm, and with one of the most elegant algorithms in computing: exponentiation by squaring.

Why it matters: powers are the language of scale. Compound interest, half-lives of medicines, the inverse-square law of light and gravity, the size of a pizza, how many passwords an attacker must try, how much memory a 64-bit pointer can address, and why some algorithms finish in a blink while others never finish at all are all questions about exponents.

Where this chapter sits

Prerequisites: Chapter 1 (arithmetic laws, negative numbers, binary) and Chapter 2 (fractions, reciprocals, decimals).

This chapter unlocks: algebraic expressions and polynomials (Chapter 4, Chapter 7), the quadratic formula’s square root (Chapter 8), exponential functions and logarithms (Chapter 12), and the power rule of calculus (Chapter 17). Fast exponentiation reappears in number theory and cryptography (Chapter 23).

Fast path: if the mastery check is quick, move on — but skim Section 3.3 (why the rules are what they are) and Section 3.9 (the algorithm).

3.1. Exponents as repeated multiplication

3.1.1. The problem

Take a sheet of paper 0.1 mm thick and fold it in half. It is now 0.2 mm thick. Fold again: 0.4 mm. How many folds until the stack would reach the Moon, 384,000 km away? Most people guess thousands, or millions. The answer is 42. Repeated doubling grows so violently that ordinary intuition, trained on repeated adding, fails completely. We need notation for repeated multiplication, and then we need to learn to think with it.

3.1.2. Notation and vocabulary

Just as multiplication abbreviates repeated addition (\(3 \times 4 = 4 + 4 + 4\)), an exponent abbreviates repeated multiplication:

\[a^n = \underbrace{a \times a \times \cdots \times a}_{n \text{ factors}} .\]

The underbrace says "count the factors underneath: there are \(n\) of them". So \(2^5 = 2 \times 2 \times 2 \times 2 \times 2 = 32\), and after \(n\) folds the paper is \(0.1 \times 2^n\) mm thick.

Base, exponent, power

In \(a^n\), \(a\) is the base and \(n\) is the exponent (also called the index — plural indices — or power). The whole expression \(a^n\) is "a power of \(a\)" and is read "\(a\) to the \(n\)", "\(a\) to the power \(n\)", or "\(a\) raised to the \(n\)th". \(a^1 = a\). In code it is written a**n (Python), a^n (spreadsheets, math software), or pow(a, n) in C; in C and Java ^ means XOR.
Squared, cubed

\(a^2\) is read "\(a\) squared" because it is the area of a square with side \(a\); \(a^3\) is "\(a\) cubed", the volume of a cube with edge \(a\). A perfect square is the square of an integer (1, 4, 9, 16, 25, …); a perfect cube is the cube of one (1, 8, 27, 64, …).

Back to the paper. After 42 folds the thickness is \(0.1 \times 2^{42}\) mm. We will see in Section 3.7 that \(2^{10} \approx 1000\), so \(2^{40} = (2^{10})^4 \approx 10^{12}\) and \(2^{42} \approx 4 \times 10^{12}\). That makes \(0.1 \times 4 \times 10^{12} = 4 \times 10^{11}\) mm \(= 4 \times 10^5\) km: about 400,000 km, beyond the Moon. (Physically you cannot fold paper more than about 7 times — the point is the arithmetic.)

3.1.3. Failure modes

Exponent mistakes worth avoiding from day one

  • \(2^3 = 8\), not \(2 \times 3 = 6\). The exponent counts factors; it does not multiply the base.

  • \(-3^2 = -9\) but \((-3)^2 = 9\): the exponent binds tighter than the leading minus (Section 1.6). An exponent applies only to what is immediately beneath it: \(2x^2\) means \(2 \cdot x^2\), not \((2x)^2\).

  • An even power of a negative number is positive; an odd power is negative: \((-2)^4 = 16\), \((-2)^5 = -32\) (count the negative factors, Section 1.5).
US curriculum

Whole-number exponents, especially powers of 10, appear in grade 5–6 (5.NBT.2, 6.EE.1). Integer exponents and their properties are grade 8 (8.EE.1). Rational exponents and radicals are Algebra I / Algebra II (N-RN.1–2).

3.2. The laws of exponents, derived

3.2.1. The problem

Simplify \(\dfrac{x^7 \cdot (x^2)^3}{x^4}\). You might remember rules like "add the exponents" and "multiply the exponents", but which applies when? If the rules are derived rather than memorised, you never need to remember them: you can re-derive any of them in ten seconds by counting factors.

3.2.2. Why they work: counting factors

Product law. \(a^m \cdot a^n\): write out the factors.

\[a^m \cdot a^n = \underbrace{a \cdots a}_{m} \cdot \underbrace{a \cdots a}_{n} = \underbrace{a \cdots a}_{m + n} = a^{m+n}.\]

Example: \(2^3 \cdot 2^2 = (2 \cdot 2 \cdot 2)(2 \cdot 2) = 2^5\). The exponents add because the factors are just pooled (associative law).

Quotient law. \(\dfrac{a^m}{a^n}\) with \(m > n\) and \(a \neq 0\): each of the \(n\) factors downstairs cancels one of the \(m\) factors upstairs.

\[\frac{a^m}{a^n} = \frac{\overbrace{a \cdots a}^{m}}{\underbrace{a \cdots a}_{n}} = \underbrace{a \cdots a}_{m - n} = a^{m-n}.\]

Example: \(\dfrac{5^6}{5^2} = \dfrac{5 \cdot 5 \cdot 5 \cdot 5 \cdot (5 \cdot 5)}{(5 \cdot 5)} = 5^4\).

Power of a power. \((a^m)^n\) is \(n\) copies of \(a^m\) multiplied together, and each copy contains \(m\) factors of \(a\):

\[(a^m)^n = \underbrace{a^m \cdot a^m \cdots a^m}_{n \text{ copies}} = a^{\overbrace{m + m + \cdots + m}^{n}} = a^{mn}.\]

Example: \((2^3)^2 = 2^3 \cdot 2^3 = 2^6\).

Power of a product and power of a quotient. Rearranging factors (commutative and associative laws):

\[(ab)^n = \underbrace{(ab)(ab)\cdots(ab)}_{n} = \underbrace{a \cdots a}_{n}\,\underbrace{b \cdots b}_{n} = a^n b^n, \qquad \left(\frac{a}{b}\right)^n = \frac{a^n}{b^n}.\]

Collected:

\[\begin{array}{ll} a^m \cdot a^n = a^{m+n} & \text{(same base, multiply} \to \text{add exponents)} \\[2pt] \dfrac{a^m}{a^n} = a^{m-n} & \text{(same base, divide} \to \text{subtract exponents)} \\[6pt] (a^m)^n = a^{mn} & \text{(power of a power} \to \text{multiply exponents)} \\[2pt] (ab)^n = a^n b^n & \text{(power distributes over a product)} \\[2pt] \left(\dfrac{a}{b}\right)^n = \dfrac{a^n}{b^n} & \text{(power distributes over a quotient)} \end{array}\]
Laws of exponents

For non-zero bases and integer exponents: \(a^m a^n = a^{m+n}\), \(a^m / a^n = a^{m-n}\), \((a^m)^n = a^{mn}\), \((ab)^n = a^n b^n\), \((a/b)^n = a^n / b^n\), \(a^0 = 1\), \(a^{-n} = 1/a^n\). They extend to fractional exponents for positive bases. Each can be re-derived by writing out the factors.

3.2.3. The method

Example 17. Procedure — simplify an expression with exponents

Input: a product/quotient of powers.

Steps:

  1. Expand any power of a product or quotient: \((ab)^n \to a^n b^n\).

  2. Apply power-of-a-power: \((a^m)^n \to a^{mn}\).

  3. For each base, combine everything into a single power: add exponents of factors on top, subtract exponents of factors on the bottom.

  4. Rewrite any negative exponents as reciprocals if the answer should have positive exponents (Section 3.3).

  5. Evaluate numerical powers if small.

Output: a product of powers of distinct bases.

3.2.4. Worked examples

Example 1. The opening problem.

\[\begin{aligned} \frac{x^7 \cdot (x^2)^3}{x^4} &= \frac{x^7 \cdot x^6}{x^4} && \text{(power of a power: } 2 \times 3 = 6\text{)} \\ &= \frac{x^{13}}{x^4} && \text{(product law: } 7 + 6 = 13\text{)} \\ &= x^{9}. && \text{(quotient law: } 13 - 4 = 9\text{)} \end{aligned}\]

Example 2. Several bases.

\[\begin{aligned} \frac{(2a^3b)^2 \cdot 3ab^4}{6a^5b^2} &= \frac{2^2 a^6 b^2 \cdot 3ab^4}{6a^5b^2} && \text{(power of a product, then power of a power)} \\ &= \frac{12\, a^{7} b^{6}}{6\, a^5 b^2} && (4 \times 3 = 12;\; a^6 a^1 = a^7;\; b^2 b^4 = b^6) \\ &= 2 a^{2} b^{4}. && (12 / 6;\; 7 - 5;\; 6 - 2) \end{aligned}\]

Example 3. Different bases that are secretly the same: \(8^3 \cdot 4^2\).

\[8^3 \cdot 4^2 = (2^3)^3 \cdot (2^2)^2 = 2^9 \cdot 2^4 = 2^{13} = 8192.\]

Rewriting numbers as powers of a common base is the standard trick for exponential equations in Chapter 12.

3.2.5. Failure modes

Things the laws do not say

  • No law for sums. \(a^m + a^n\) does not simplify to a single power: \(2^3 + 2^2 = 12\), which is not a power of 2. The laws are about products.

  • Powers do not distribute over addition. \((a + b)^2 \neq a^2 + b^2\). Test: \((1 + 1)^2 = 4\) but \(1^2 + 1^2 = 2\). The correct expansion, \(a^2 + 2ab + b^2\), comes from the distributive law (Chapter 7).

  • Different bases do not combine by adding exponents. \(2^3 \cdot 3^2 \neq 6^5\). (But equal exponents do combine: \(2^3 \cdot 3^3 = 6^3\), by the power-of-a-product law read backwards.)

  • \((a^m)^n\) is not \(a^{m^n}\): \((2^3)^2 = 2^6 = 64\) while \(2^{3^2} = 2^9 = 512\) (stacked exponents group from the top, Section 1.6).

3.2.6. Where you’d use this

  • Area and volume scale as powers. A 16-inch pizza versus a 12-inch one: the area ratio is \((16/12)^2 = (4/3)^2 = 16/9 \approx 1.78\), so the larger pizza is almost 80% more food, not 33% more. Double every edge of a box and its volume grows by \(2^3 = 8\). This is the square–cube law: a giant ant scaled up 10 times would weigh \(10^3 = 1000\) times as much but have legs only \(10^2 = 100\) times as strong in cross-section, which is why large animals have thick legs.

  • Unit conversions with powers. \(1 \text{ km}^2 = (10^3 \text{ m})^2 = 10^6 \text{ m}^2\) (power of a product, then power of a power). Forgetting to square the conversion factor is one of the commonest errors in physics homework and in real engineering.

  • Counting in computing. A pixel with 8 bits each for red, green, and blue can be one of \(2^8 \cdot 2^8 \cdot 2^8 = 2^{24} = 16\,777\,216\) colours (product law). A 4-digit PIN has \(10^4\) possibilities; a 6-digit one, \(10^6\), which is 100 times harder to guess.

Exponent rule checker

Enter an exponent "rule" — true or false — such as \((a + b)^n = a^n + b^n\) or \(a^m a^n = a^{mn}\). The app tests it on random numbers and shows a counterexample if one exists, or a factor-counting picture (rows of coloured tiles for each factor) if it holds.

3.2.7. Exercises

  1. Simplify: (a) \(x^4 \cdot x^5\); (b) \(\dfrac{y^{10}}{y^3}\); (c) \((z^3)^4\); (d) \((3p^2q)^3\).

  2. Simplify \(\dfrac{(4m^2n^3)^2}{8m^3n^5}\).

  3. Write \(27^2 \cdot 9^3 / 3^5\) as a single power of 3.

  4. Is \(2^{10} + 2^{10} = 2^{11}\) or \(2^{20}\)? Explain.

Answers

  1. (a) \(x^9\). (b) \(y^7\). (c) \(z^{12}\). (d) \(27p^6q^3\).

  2. Numerator \(16m^4n^6\); divide: \(\tfrac{16}{8} m^{4-3} n^{6-5} = 2mn\).

  3. \((3^3)^2 \cdot (3^2)^3 / 3^5 = 3^6 \cdot 3^6 / 3^5 = 3^{7}\).

  4. \(2^{10} + 2^{10} = 2 \cdot 2^{10} = 2^1 \cdot 2^{10} = 2^{11}\). Adding two equal things doubles; it does not multiply the exponents.

3.3. Zero and negative exponents

3.3.1. The problem

"\(a^n\) means \(n\) factors of \(a\)" makes sense for \(n = 1, 2, 3, \ldots\). But what could \(2^0\) mean — zero factors of 2? Or \(2^{-3}\), negative three factors? These are not questions about the definition (which has nothing to say) but about how to extend it. We want an extension that keeps the laws of exponents working. It turns out there is exactly one.

3.3.2. Intuition: follow the pattern

Read the powers of 2 from right to left: each step to the left divides by 2.

Bar chart of 2 to the n for n from -3 to 4 with values 1/8 to 16
Figure 19. Powers of 2. Moving one step left always divides by 2; continuing the pattern past \(2^1\) gives \(2^0 = 1\), then halves.
\[\begin{aligned} 2^3 &= 8 \\ 2^2 &= 4 && (\div 2) \\ 2^1 &= 2 && (\div 2) \\ 2^0 &= 1 && (\div 2) \\ 2^{-1} &= \tfrac{1}{2} && (\div 2) \\ 2^{-2} &= \tfrac{1}{4} && (\div 2) \\ 2^{-3} &= \tfrac{1}{8}. && (\div 2) \end{aligned}\]

If the pattern is to continue — and there is no reason to put a break in it — then \(2^0\) must be 1 and \(2^{-n}\) must be \(\tfrac{1}{2^n}\).

3.3.3. Why it works: the laws force it

Insist that the quotient law \(\tfrac{a^m}{a^n} = a^{m-n}\) keeps working when \(m = n\). The left side is something divided by itself:

\[1 = \frac{a^n}{a^n} = a^{n-n} = a^0 .\]

So \(a^0 = 1\) for every \(a \neq 0\). Now insist that the product law keeps working for a negative exponent:

\[a^{-n} \cdot a^{n} = a^{-n + n} = a^0 = 1 .\]

So \(a^{-n}\) is the number which, multiplied by \(a^n\), gives 1 — the reciprocal of \(a^n\):

\[a^{-n} = \frac{1}{a^n}, \qquad a^0 = 1 \qquad (a \neq 0).\]

This is a recurring pattern in mathematics: a definition is first made where it obviously makes sense, then extended in the unique way that preserves the rules. You will see it again with fractional exponents (next section), with \(0! = 1\) (Chapter 24), and with complex exponents (Chapter 15).

Zero and negative exponents

For any \(a \neq 0\): \(a^0 = 1\) (the empty product), and \(a^{-n} = \dfrac{1}{a^n}\). A negative exponent means "reciprocal", not "negative": \(2^{-3} = \tfrac{1}{8}\), which is positive. A negative exponent on a fraction flips it: \(\left(\tfrac{a}{b}\right)^{-n} = \left(\tfrac{b}{a}\right)^n\).

3.3.4. Worked examples

\[\begin{aligned} 5^{-2} &= \frac{1}{5^2} = \frac{1}{25} = 0.04 \\ \left(\tfrac{2}{3}\right)^{-3} &= \left(\tfrac{3}{2}\right)^{3} = \frac{27}{8} \\ \frac{x^3}{x^8} &= x^{3-8} = x^{-5} = \frac{1}{x^5} \\ \frac{6a^{-2}b^3}{2a^{3}b^{-1}} &= 3\,a^{-2-3}\,b^{3-(-1)} = 3a^{-5}b^{4} = \frac{3b^4}{a^5}. \end{aligned}\]

In the last line, note \(b^{3 - (-1)} = b^4\): subtracting a negative exponent is adding (Section 1.5). An equivalent shortcut is "a factor with a negative exponent may move across the fraction bar and change the sign of its exponent".

The empty product and \(0^0\)

\(a^0 = 1\) for the same reason an empty sum is 0: 1 is what you start with before multiplying anything in (it is the multiplicative identity, Section 1.4). In code, product = 1 before a loop that runs zero times. What about \(0^0\)? The pattern \(0^1, 0^2, \ldots = 0\) suggests 0, while \(a^0 = 1\) suggests 1. In algebra, combinatorics, and computing the convention \(0^0 = 1\) is almost universal (Python’s 0**0 is 1), because it makes formulas like the binomial theorem work. In calculus, "\(0^0\)" is an indeterminate form (Chapter 16): a limit of that shape can come out to anything.
\(0^{-1}\)

\(0^{-n}\) for \(n > 0\) would be \(\tfrac{1}{0^n} = \tfrac{1}{0}\), which is undefined (Section 1.4). Python raises ZeroDivisionError for 0**-1. The laws of this section all assume a non-zero base.

3.3.5. Where you’d use this

  • Medicine. Caffeine has a half-life of roughly 5 hours. After \(n\) half-lives a fraction \(2^{-n}\) remains: 200 mg drunk at 2 p.m. leaves about \(200 \times 2^{-2} = 50\) mg in your system at midnight. Drug dosing schedules are designed with exactly this calculation.

  • Physics: inverse-square laws. Light intensity, gravity, and radio signal strength fall off as \(r^{-2}\). Move three times further from a lamp (or a Wi-Fi router) and you receive \(3^{-2} = \tfrac{1}{9}\) of the power. Units use negative exponents too: acceleration in \(\text{m}\,\text{s}^{-2}\), density in \(\text{kg}\,\text{m}^{-3}\).

  • Computing. Binary place values to the right of the point are \(2^{-1}, 2^{-2}, 2^{-3}, \ldots\) (Section 2.8). Machine-learning learning rates, tolerances, and probabilities are routinely written as \(10^{-3}\) or 1e-3.

3.3.6. Exercises

  1. Evaluate: \(10^{-3}\), \(4^{-1}\), \((-3)^{-2}\), \(\left(\tfrac{1}{2}\right)^{-4}\), \(7^0\), \((-7)^0\), \(-7^0\).

  2. Simplify, giving the answer with positive exponents: \(\dfrac{x^{-2}y^5}{x^4y^{-3}}\).

  3. Use the product law to explain why \(10^{-3} \times 10^{5} = 100\).

Answers

  1. \(0.001\); \(\tfrac{1}{4}\); \(\tfrac{1}{9}\) (even power: positive); \(2^4 = 16\); \(1\); \(1\); \(-1\) (the minus is outside the power).

  2. \(x^{-2-4} y^{5-(-3)} = x^{-6} y^{8} = \dfrac{y^8}{x^6}\).

  3. \(10^{-3} \times 10^5 = 10^{-3+5} = 10^2 = 100\). In words: dividing by 1000 then multiplying by 100,000 is a net multiplication by 100.

3.4. Roots and fractional exponents

3.4.1. The problem

A square room has area 20 square metres. How long is each wall? We need to undo squaring. More generally, if we know \(x^n\) and want \(x\), we need an inverse of raising to a power. Root notation does this; fractional exponents turn out to be the same idea in a form that obeys the exponent laws.

3.4.2. Intuition and vocabulary

Square root, cube root, nth root

A square root of \(a\) is a number whose square is \(a\). Every positive number has two (\(3\) and \(-3\) are both square roots of 9). The symbol \(\sqrt{a}\) — the radical sign over the radicand \(a\) — means the principal (non-negative) square root: \(\sqrt{9} = 3\). A cube root \(\sqrt[3]{a}\) satisfies \((\sqrt[3]{a})^3 = a\); every real number has exactly one real cube root (\(\sqrt[3]{-8} = -2\)). In general \(\sqrt[n]{a}\) is the nth root; the small \(n\) is the index of the root.

Negative numbers have no real square root, because any real number squared is non-negative (positive × positive and negative × negative are both positive). That gap is the one the complex numbers fill (Chapter 15).

Geometrically, \(\sqrt{a}\) is the side of a square of area \(a\). The picture below constructs a square of area exactly 2 on a unit grid, so its side has length exactly \(\sqrt{2}\) — a length you can draw perfectly but (Section 1.1) never write as a fraction.

A square tilted at 45 degrees on a 2 by 2 grid with area 2
Figure 20. A square of area 2: it covers four half-squares. Its side is \(\sqrt{2}\).

3.4.3. Why it works: fractional exponents

What should \(9^{1/2}\) mean? Once again, demand that the laws keep working. Power-of-a-power says

\[\left(9^{1/2}\right)^2 = 9^{\frac{1}{2} \cdot 2} = 9^1 = 9 .\]

So \(9^{1/2}\) is a number whose square is 9: a square root of 9. We choose the positive one. In general, for \(a > 0\),

\[a^{1/n} = \sqrt[n]{a}, \qquad a^{m/n} = \left(\sqrt[n]{a}\right)^m = \sqrt[n]{a^m}.\]

The second formula follows from \(a^{m/n} = (a^{1/n})^m = (a^m)^{1/n}\), both of which are power-of-a-power. The denominator of the exponent is the root; the numerator is the power.

Rational exponents

For \(a > 0\) and integers \(m\), \(n\) with \(n > 0\): \(a^{1/n} = \sqrt[n]{a}\) and \(a^{m/n} = (\sqrt[n]{a})^m\). All the laws of exponents continue to hold. So \(\sqrt{x} = x^{1/2}\), \(\dfrac{1}{\sqrt{x}} = x^{-1/2}\), \(\sqrt[3]{x^2} = x^{2/3}\). Converting roots to fractional exponents is how calculus handles them (Chapter 17).

Squaring and square-rooting undo each other (for non-negative numbers), so their graphs are mirror images in the line \(y = x\): a point \((a, b)\) on one corresponds to \((b, a)\) on the other. This mirror relationship between a function and its inverse is a central idea of Chapter 11.

Graphs of y = x squared and y = square root of x reflected in the line y = x
Figure 21. Squaring and square-rooting are inverse operations for \(x \ge 0\): their graphs are reflections in \(y = x\).

3.4.4. The method

Example 18. Procedure — evaluate \(a^{m/n}\) by hand

Input: a positive base \(a\) and a fraction \(m/n\) (in lowest terms, \(n > 0\)).

Steps:

  1. If \(m < 0\), compute \(a^{|m|/n}\) and take the reciprocal at the end.

  2. Take the \(n\)th root first (it keeps numbers small): \(r = \sqrt[n]{a}\).

  3. Raise to the \(m\)th power: \(r^m\).

Output: \(a^{m/n}\).

3.4.5. Worked examples

\[\begin{aligned} 8^{2/3} &= \left(\sqrt[3]{8}\right)^2 = 2^2 = 4 \\ 16^{3/4} &= \left(\sqrt[4]{16}\right)^3 = 2^3 = 8 \\ 27^{-1/3} &= \frac{1}{27^{1/3}} = \frac{1}{3} \\ \left(\tfrac{4}{9}\right)^{3/2} &= \left(\sqrt{\tfrac{4}{9}}\right)^3 = \left(\tfrac{2}{3}\right)^3 = \frac{8}{27}. \end{aligned}\]

Root first versus power first: \(16^{3/4}\) as \(\sqrt[4]{16^3} = \sqrt[4]{4096}\) gives the same 8, but finding the fourth root of 4096 by hand is far harder. Root first is the right choice whenever the root comes out exactly.

3.4.6. Alternative approach: computing a root numerically

When the root is not exact (\(\sqrt{20}\)), you can estimate it. \(\sqrt{20}\) lies between \(\sqrt{16} = 4\) and \(\sqrt{25} = 5\), closer to 4. A classical algorithm, the Babylonian method, improves any guess \(g\) by averaging it with \(20 / g\): if \(g\) is too big then \(20/g\) is too small, and the average is better than either.

\[\begin{aligned} g_0 &= 4.5 \\ g_1 &= \tfrac{1}{2}\left(4.5 + \tfrac{20}{4.5}\right) = \tfrac{1}{2}(4.5 + 4.4444) = 4.47222 \\ g_2 &= \tfrac{1}{2}\left(4.47222 + \tfrac{20}{4.47222}\right) = \tfrac{1}{2}(4.47222 + 4.47205) = 4.47214 \end{aligned}\]

Two steps already give \(\sqrt{20} \approx 4.47214\) (true value \(4.472135955\ldots\)). The number of correct digits roughly doubles each step. This is Newton’s method in disguise; Chapter 18 and Chapter 32 explain why it converges so fast.

3.4.7. Failure modes

Roots: the classic errors

  • \(\sqrt{a + b} \neq \sqrt{a} + \sqrt{b}\). Test: \(\sqrt{9 + 16} = 5\), but \(3 + 4 = 7\). (A root is a power, and powers do not distribute over sums.)

  • \(\sqrt{x^2} = |x|\), not \(x\). If \(x = -3\), \(\sqrt{(-3)^2} = \sqrt{9} = 3\). The principal root is never negative (Section 1.7).

  • "\(x^2 = 9\) so \(x = 3\)" loses a solution: \(x = \pm 3\) (read \(\pm\) as "plus or minus"). Solving with a square root needs the \(\pm\); the symbol \(\sqrt{9}\) alone does not have it.

  • Fractional powers of negative numbers are treacherous. \((-8)^{1/3}\) "should" be \(-2\), but \((-8)^{2/6}\) would then be \(\sqrt[6]{64} = 2\). The laws only hold for positive bases. Python’s (-8)**(1/3) returns a complex number, (1.0000000000000002+1.7320508075688772j); use -(8**(1/3)) or math.cbrt (Python 3.11+) for the real cube root.

3.4.8. Where you’d use this

  • Everyday. The square room with area 20 m² has walls of \(\sqrt{20} \approx 4.47\) m. A TV’s diagonal comes from Pythagoras (Chapter 9): a screen 30 by 40 inches is \(\sqrt{30^2 + 40^2} = \sqrt{2500} = 50\) inches across.

  • Music. Equal temperament splits an octave (a doubling of frequency) into 12 equal ratios, so each semitone multiplies the frequency by \(2^{1/12} \approx 1.0595\). Concert A is 440 Hz; the next note up, A♯, is \(440 \times 2^{1/12} \approx 466.2\) Hz.

  • Physics. An object dropped from height \(h\) (ignoring air resistance) hits the ground after \(t = \sqrt{2h/g}\): from 20 m, \(\sqrt{40/9.81} \approx 2.0\) s. A pendulum of length 1 m has period \(2\pi\sqrt{L/g} \approx 2.0\) s, which is why old clocks had metre-long pendulums.

  • Finance. Fractional exponents turn total growth into a yearly rate. An investment that doubles in 10 years grew by a factor \(2^{1/10} \approx 1.072\) each year: about 7.2% a year.

  • Computing. The distance between two points in a game or a map is \(\sqrt{\Delta x^2 + \Delta y^2}\). Code that only needs to know which of two objects is closer compares the squared distances instead, skipping the square root entirely. Root-mean-square error, the standard measure of a regression model’s accuracy, is a square root of an average of squares (Chapter 31).

Computer-science connection: roots in code

math.sqrt(x) is a single hardware instruction on modern CPUs and is correctly rounded (the closest double to the true root). x ** 0.5 usually gives the same result but goes through a general power routine. For integers, math.isqrt(n) returns \(\lfloor \sqrt{n} \rfloor\) exactly (the brackets \(\lfloor\,\rfloor\) mean "round down"), with no floating-point error — exactly what trial division (Section 1.8) needs. The famous "fast inverse square root" from Quake III computed \(x^{-1/2}\) — needed to normalise vectors for lighting — with a bit-level hack on the float’s exponent followed by one Newton step.

Where the radical sign came from

"Radical" comes from Latin radix, "root" (as in radish). The symbol √ is thought to derive from a stylised lowercase r, first printed in Christoff Rudolff’s Coss of 1525. The bar over the radicand (the vinculum) was added by Descartes in 1637 to show how far the root extends — the same bar that became the fraction bar.
Root finder

Drag a square’s side until its area matches a target (say 20) and watch the side length converge; then switch to the Babylonian method and step it, showing each guess and its partner \(20/g\) closing in from opposite sides of the true root.

Try it: Babylonian square-root stepper

3.4.9. Exercises

  1. Evaluate: \(\sqrt{144}\), \(\sqrt[3]{-125}\), \(32^{1/5}\), \(32^{3/5}\), \(9^{-3/2}\).

  2. Write as a power of \(x\): \(\sqrt{x}\), \(\dfrac{1}{x\sqrt{x}}\), \(\sqrt[4]{x^3}\).

  3. Solve \(x^2 = 50\) exactly and approximately (two Babylonian steps from \(g_0 = 7\)). Try it: Step √50 from 7.

Answers

  1. \(12\); \(-5\); \(2\); \(2^3 = 8\); \(\tfrac{1}{(\sqrt{9})^3} = \tfrac{1}{27}\).

  2. \(x^{1/2}\); \(x^{-1} \cdot x^{-1/2} = x^{-3/2}\); \(x^{3/4}\).

  3. \(x = \pm\sqrt{50} = \pm 5\sqrt{2}\) (see Section 3.5). \(g_1 = \tfrac12(7 + \tfrac{50}{7}) = \tfrac12(7 + 7.142857) = 7.071429\); \(g_2 = \tfrac12(7.071429 + 7.070707) = 7.071068\). So \(x \approx \pm 7.0711\).

3.5. Surds: simplifying radicals and rationalising denominators

3.5.1. The problem

Your calculator says \(\sqrt{50} = 7.0710678\ldots\) and \(\tfrac{1}{\sqrt 2} = 0.7071067\ldots\). Notice anything? The digits are the same. Exact forms make such relationships visible — \(\sqrt{50} = 5\sqrt{2}\) and \(\tfrac{1}{\sqrt{2}} = \tfrac{\sqrt{2}}{2}\) — while decimals hide them. In geometry, trigonometry, and the quadratic formula, exact answers involving roots appear constantly, and you need to be able to put them in a standard simplest form.

Surd, radical form

A surd (UK usage) or radical (US usage) is an irrational root such as \(\sqrt{2}\) or \(\sqrt[3]{5}\), left in exact form rather than as a decimal. Simplest radical form means: no perfect-square factor under a square root, no root in a denominator, and no fraction under a root. Like surds have the same radicand (\(3\sqrt{2}\) and \(5\sqrt{2}\)) and can be added like like terms.

3.5.2. Why it works

For \(a, b \ge 0\), the power-of-a-product law with exponent \(\tfrac{1}{2}\) gives

\[\sqrt{ab} = (ab)^{1/2} = a^{1/2}\, b^{1/2} = \sqrt{a}\,\sqrt{b}, \qquad \sqrt{\frac{a}{b}} = \frac{\sqrt{a}}{\sqrt{b}} \quad (b > 0).\]

So we can split a radicand into a perfect square times something else and pull the perfect square out.

3.5.3. The method

Example 19. Procedure — simplify a square root of a positive integer

Input: \(\sqrt{n}\) for a positive integer \(n\).

Steps:

  1. Find the prime factorisation of \(n\) (Section 1.8).

  2. Pair up equal primes. Each pair \(p \cdot p = p^2\) comes out of the root as a single \(p\).

  3. Multiply the extracted primes together (outside) and the unpaired primes together (inside).

Output: \(k\sqrt{m}\) where \(m\) has no square factor greater than 1.

Example 20. Procedure — rationalise a denominator

Input: a fraction with a square root in the denominator.

Steps:

  1. If the denominator is \(c\sqrt{b}\): multiply top and bottom by \(\sqrt{b}\), using \(\sqrt{b}\sqrt{b} = b\).

  2. If the denominator is \(a + \sqrt{b}\) (or \(a - \sqrt{b}\)): multiply top and bottom by the conjugate \(a - \sqrt{b}\) (or \(a + \sqrt{b}\)), using \((a + \sqrt{b})(a - \sqrt{b}) = a^2 - b\).

  3. Simplify.

Output: an equivalent fraction with a rational denominator.

The conjugate trick works because of the difference of two squares, \((x + y)(x - y) = x^2 - y^2\), which you can check with the distributive law: \(x^2 - xy + yx - y^2 = x^2 - y^2\). The cross terms cancel, and squaring kills the root.

3.5.4. Worked examples

Simplify \(\sqrt{72}\).

\[\begin{aligned} \sqrt{72} &= \sqrt{2 \cdot 2 \cdot 2 \cdot 3 \cdot 3} && \text{(factorise: } 72 = 2^3 \cdot 3^2\text{)} \\ &= \sqrt{(2 \cdot 2)(3 \cdot 3) \cdot 2} && \text{(pair up)} \\ &= 2 \cdot 3 \cdot \sqrt{2} = 6\sqrt{2}. \end{aligned}\]

The shortcut, when you can spot it, is to find the largest perfect-square factor: \(72 = 36 \times 2\), so \(\sqrt{72} = \sqrt{36}\sqrt{2} = 6\sqrt{2}\).

Add surds: \(\sqrt{50} + \sqrt{18} - \sqrt{8} = 5\sqrt{2} + 3\sqrt{2} - 2\sqrt{2} = 6\sqrt{2}\). Only after simplifying are they visibly like surds.

Rationalise: \(\dfrac{6}{\sqrt{3}}\).

\[\frac{6}{\sqrt{3}} = \frac{6}{\sqrt{3}} \cdot \frac{\sqrt{3}}{\sqrt{3}} = \frac{6\sqrt{3}}{3} = 2\sqrt{3}.\]

Rationalise with a conjugate: \(\dfrac{4}{3 - \sqrt{5}}\).

\[\begin{aligned} \frac{4}{3 - \sqrt{5}} &= \frac{4}{3 - \sqrt{5}} \cdot \frac{3 + \sqrt{5}}{3 + \sqrt{5}} && \text{(multiply by 1, in the form conjugate/conjugate)} \\ &= \frac{4(3 + \sqrt{5})}{3^2 - (\sqrt{5})^2} && \text{(difference of two squares)} \\ &= \frac{4(3 + \sqrt{5})}{9 - 5} = \frac{4(3 + \sqrt{5})}{4} \\ &= 3 + \sqrt{5}. \end{aligned}\]

3.5.5. Choosing a method, and why bother

  • For simplifying: if you can see a perfect-square factor (4, 9, 16, 25, 36, 49, 64, 81, 100, …), use it directly; otherwise factorise.

  • Rationalising was originally about hand computation: \(\tfrac{1}{\sqrt{2}} = \tfrac{1}{1.41421\ldots}\) is a horrible long division, while \(\tfrac{\sqrt{2}}{2} = \tfrac{1.41421\ldots}{2}\) is easy. Today the reason is mainly canonical form (Section 2.2): it makes equal answers look equal, so you can compare your answer with someone else’s. The conjugate technique itself remains important — the same trick evaluates limits in calculus (Chapter 16) and divides complex numbers (Chapter 15).

A surd you have handled today. A4 paper is 210 mm by 297 mm, and \(297 / 210 \approx 1.414 \approx \sqrt{2}\). The ISO paper sizes are designed so that folding a sheet in half gives the next size down with exactly the same shape: if the sides are \(1\) and \(r\), the half-sheet has sides \(\tfrac{r}{2}\) and \(1\), and keeping the ratio means \(r / 1 = 1 / (r/2)\), so \(r^2 = 2\) and \(r = \sqrt{2}\). That is why a photocopier can shrink A3 to A4 at "71%": \(\tfrac{1}{\sqrt{2}} = \tfrac{\sqrt{2}}{2} \approx 0.707\).

Surd mistakes

\(\sqrt{2} + \sqrt{3} \neq \sqrt{5}\) (unlike surds do not combine; \(1.414 + 1.732 = 3.146 \neq 2.236\)). \(2\sqrt{3}\) means \(2 \times \sqrt{3}\), not \(\sqrt[2]{3}\) or \(\sqrt{6}\). And \(\sqrt{ab} = \sqrt{a}\sqrt{b}\) needs \(a, b \ge 0\): "\(1 = \sqrt{1} = \sqrt{(-1)(-1)} = \sqrt{-1}\sqrt{-1} = -1\)" is a famous fake proof that breaks exactly there.

3.5.6. Exercises

  1. Simplify: \(\sqrt{48}\), \(\sqrt{200}\), \(3\sqrt{20} - \sqrt{45}\).

  2. Rationalise: \(\dfrac{10}{\sqrt{5}}\), \(\dfrac{1}{\sqrt{2} + 1}\).

  3. A square has diagonal 10 cm. Find its side in simplest radical form. (Diagonal of a square with side \(s\) is \(s\sqrt{2}\), by Pythagoras, Chapter 9.)

Answers

  1. \(\sqrt{16 \cdot 3} = 4\sqrt{3}\); \(\sqrt{100 \cdot 2} = 10\sqrt{2}\); \(3 \cdot 2\sqrt{5} - 3\sqrt{5} = 3\sqrt{5}\).

  2. \(\tfrac{10\sqrt{5}}{5} = 2\sqrt{5}\). \(\tfrac{1}{\sqrt{2} + 1} \cdot \tfrac{\sqrt{2} - 1}{\sqrt{2} - 1} = \tfrac{\sqrt{2} - 1}{2 - 1} = \sqrt{2} - 1\).

  3. \(s\sqrt{2} = 10\), so \(s = \tfrac{10}{\sqrt{2}} = \tfrac{10\sqrt{2}}{2} = 5\sqrt{2}\) cm (about 7.07 cm).

US curriculum

Square roots and cube roots of perfect squares and cubes, and the irrationality of \(\sqrt{2}\), are grade 8 (8.EE.2, 8.NS). Simplifying radicals and rationalising denominators are Algebra I (often) and Algebra II (always); rational exponents are Algebra II (N-RN.1–2). In the UK, "surds" is a GCSE Higher and A-level topic.

3.6. Scientific notation and significant figures

3.6.1. The problem

The mass of the Earth is 5,970,000,000,000,000,000,000,000 kg. The mass of an electron is 0.000 000 000 000 000 000 000 000 000 000 911 kg. Written out, these are unreadable, impossible to compare at a glance, and easy to miscount. Worse, they claim false precision: is the Earth’s mass really known to the last kilogram?

3.6.2. Intuition

Separate a number into how big (a power of ten) and which digits (a number between 1 and 10). The Earth is \(5.97 \times 10^{24}\) kg: "about 6, followed by 24 places". The electron is \(9.11 \times 10^{-31}\) kg. The exponent carries the size; the leading number carries the precision.

Scientific notation

A number is in scientific notation (UK: standard form) when written as \(m \times 10^k\) with \(1 \le |m| < 10\) and \(k\) an integer. \(m\) is the significand (or mantissa or coefficient). Programming languages and calculators write \(5.97 \times 10^{24}\) as 5.97e24 (E notation). Engineering notation restricts \(k\) to multiples of 3, matching the prefixes kilo, mega, milli, micro.

3.6.3. The method

Example 21. Procedure — convert to scientific notation

Input: a non-zero decimal number.

Steps:

  1. Move the decimal point so that exactly one non-zero digit is to its left. This is \(m\).

  2. Count how many places the point moved: \(k\). If you moved it left (the number was large), \(k\) is positive; if right (the number was small), \(k\) is negative.

  3. Write \(m \times 10^{k}\), keeping only the significant digits in \(m\).

Output: \(m \times 10^k\).

Examples. \(384\,400\) km: point moves 5 places left, \(3.844 \times 10^5\) km. \(0.000\,72\) s: point moves 4 places right, \(7.2 \times 10^{-4}\) s.

Arithmetic. Multiply and divide the significands, and combine the powers of ten with the exponent laws; then re-normalise.

\[\begin{aligned} (6 \times 10^4)(5 \times 10^6) &= (6 \times 5) \times 10^{4+6} = 30 \times 10^{10} = 3.0 \times 10^{11} \\ \frac{4.8 \times 10^{7}}{1.6 \times 10^{-2}} &= \frac{4.8}{1.6} \times 10^{7 - (-2)} = 3.0 \times 10^{9} \\ \frac{5.97 \times 10^{24}}{9.11 \times 10^{-31}} &= 0.655 \times 10^{55} = 6.55 \times 10^{54} . \end{aligned}\]

The last line says the Earth outweighs an electron by a factor of about \(6.6 \times 10^{54}\) — a comparison that would be hopeless in long form. Adding and subtracting require matching exponents first: \(3.2 \times 10^5 + 4 \times 10^3 = 3.2 \times 10^5 + 0.04 \times 10^5 = 3.24 \times 10^5\).

3.6.4. Significant figures

Significant figures

The significant figures (s.f., or significant digits) of a measured number are the digits that carry real information about its precision. Rules: non-zero digits are significant; zeros between non-zero digits are significant (\(4007\): 4 s.f.); leading zeros are not (\(0.0072\): 2 s.f.); trailing zeros after a decimal point are (\(2.50\): 3 s.f.); trailing zeros in a whole number are ambiguous (\(1500\): 2, 3, or 4?) — scientific notation removes the ambiguity: \(1.5 \times 10^3\) vs \(1.500 \times 10^3\).

The working rule for calculations: a product or quotient should be reported to the fewest significant figures of its inputs. If a car travels 125.0 km in 1.5 h, the speed is \(125.0 / 1.5 = 83.333\ldots\), reported as \(83\) km/h (2 s.f., limited by 1.5). For sums and differences, the limiting factor is instead the fewest decimal places. These are rules of thumb; proper error propagation is part of Chapter 31 and Chapter 32.

False precision

A calculator showing 83.33333333 has not measured the speed to ten digits. Reporting all of them misleads the reader about how well you know the answer. The converse also bites: dropping meaningful trailing zeros (writing 2.5 for a measurement known to be 2.50) throws away information.

3.6.5. Orders of magnitude

The exponent \(k\) in \(m \times 10^k\) (rounded according to whether \(m\) is nearer 1 or 10) is the order of magnitude. Two quantities "differ by three orders of magnitude" when one is about 1000 times the other. Thinking in orders of magnitude is how physicists and engineers make sense of scales from the subatomic to the cosmic — and how you do the Fermi estimates of Section 1.10.

A logarithmic scale of lengths from the Planck length to the observable universe
Figure 22. Lengths in the universe span over 60 orders of magnitude. On this scale, each tick is a factor of \(10^5\).

A scale like this, in which equal distances mean equal ratios rather than equal differences, is a logarithmic scale. You will meet it formally in Chapter 12; it is the natural scale for anything spanning many powers of ten (earthquakes, sound levels, pH, algorithm running times).

Computer-science connection: floats are scientific notation in binary

A double is stored as \(\pm m \times 2^e\) with \(1 \le m < 2\) — scientific notation in base 2 (Section 2.8). The 52 stored bits of \(m\) give about 15–16 significant decimal digits; the 11-bit exponent allows \(e\) from about \(-1022\) to \(1023\), so doubles range from about \(2.2 \times 10^{-308}\) to \(1.8 \times 10^{308}\). The consequences follow directly: adding numbers of very different magnitude loses the smaller one entirely (1e16 + 1 == 1e16), because the significand cannot hold digits 16 orders of magnitude apart. This is significant-figure reasoning, enforced by hardware.

Powers of Ten

Charles and Ray Eames’s 1977 short film Powers of Ten starts with a picnic in Chicago and zooms out by a factor of 10 every ten seconds to \(10^{24}\) m, then zooms in to a proton. It remains one of the best nine minutes ever made on scale. The SI prefixes recently had to be extended for the same reason: in 2022 ronna (\(10^{27}\)) and quetta (\(10^{30}\)) were added, partly because global data storage is heading toward those scales.
Scale zoomer

An infinite zoom from \(10^{-35}\) m to \(10^{27}\) m, with landmarks appearing as you pass their order of magnitude. A side panel shows the current scale in scientific notation, E notation, and the matching SI prefix, and lets you pin two objects to compare their ratio.

3.6.6. Exercises

  1. Write in scientific notation: 93,000,000; 0.000 040 5; 6.02 billion.

  2. Compute, giving answers in scientific notation: \((2.5 \times 10^{-3})(4 \times 10^{8})\); \(\dfrac{9 \times 10^{5}}{3 \times 10^{-4}}\); \(7.1 \times 10^{4} - 9 \times 10^{3}\).

  3. How many significant figures: \(0.00306\), \(3.060\), \(3.06 \times 10^{-3}\)?

  4. Light travels at \(3.00 \times 10^8\) m/s. The Sun is \(1.50 \times 10^{11}\) m away. How long does sunlight take to reach us?

Answers

  1. \(9.3 \times 10^7\); \(4.05 \times 10^{-5}\); \(6.02 \times 10^{9}\).

  2. \(10 \times 10^{5} = 1.0 \times 10^{6}\); \(3 \times 10^{9}\); \(7.1 \times 10^4 - 0.9 \times 10^4 = 6.2 \times 10^4\).

  3. 3; 4; 3.

  4. \(\tfrac{1.50 \times 10^{11}}{3.00 \times 10^{8}} = 0.500 \times 10^{3} = 5.00 \times 10^2\) s, which is 500 s, or about 8.3 minutes.

US curriculum

Scientific notation, including operations with it: grade 8 (8.EE.3–4). Significant figures are taught mainly in high-school chemistry and physics. Logarithmic scales appear in Algebra II with logarithms.

3.7. Powers of two: the computer’s native scale

3.7.1. The problem

Why is a "32-bit" program limited to 4 GB of memory? Why does a "2 TB" drive show up as 1.82 TB on your computer? Why are buffer sizes, hash table capacities, and texture dimensions so often 256, 1024, 4096? All of it follows from one fact: with \(n\) bits you can write exactly \(2^n\) different patterns.

3.7.2. Why it works

Each bit has 2 possible values. Two bits give \(2 \times 2 = 4\) patterns (00, 01, 10, 11); three bits give \(2 \times 2 \times 2 = 8\); \(n\) bits give \(2^n\). (This "multiply the number of choices" rule is the multiplication principle of Chapter 24.) So:

\[\begin{array}{rll} n & 2^n & \text{significance} \\ \hline 8 & 256 & \text{values in a byte} \\ 10 & 1024 & \approx 10^3 \text{ (kibi)} \\ 16 & 65\,536 & \text{port numbers; old 16-bit address spaces} \\ 20 & 1\,048\,576 & \approx 10^6 \text{ (mebi)} \\ 30 & 1\,073\,741\,824 & \approx 10^9 \text{ (gibi)} \\ 32 & 4\,294\,967\,296 & \text{IPv4 addresses; 32-bit address space (4 GiB)} \\ 63 & \approx 9.22 \times 10^{18} & \text{largest signed 64-bit integer} + 1 \\ 64 & \approx 1.84 \times 10^{19} & \text{64-bit patterns} \\ 128 & \approx 3.40 \times 10^{38} & \text{IPv6 addresses; UUIDs} \end{array}\]

A 32-bit pointer can name \(2^{32}\) different bytes, which is \(2^{32} = 2^2 \cdot 2^{30} = 4\) GiB: the 4 GB limit. An \(n\)-bit signed integer ranges from \(-2^{n-1}\) to \(2^{n-1} - 1\) (Section 1.9). Try it: What 32 bits can address.

3.7.3. The approximation that makes it all mental

\(2^{10} = 1024 \approx 10^3\). With the power-of-a-power law, every power of 2 can be estimated in your head:

\[2^{n} = 2^{10q + r} = (2^{10})^q \cdot 2^r \approx 10^{3q} \cdot 2^r\]

where \(q\) and \(r\) are the quotient and remainder of \(n \div 10\). So \(2^{32} = (2^{10})^3 \cdot 2^2 \approx 10^9 \times 4 = 4\) billion (true: 4.29 billion), and \(2^{64} = (2^{10})^6 \cdot 2^4 \approx 10^{18} \times 16 = 1.6 \times 10^{19}\) (true: \(1.84 \times 10^{19}\)). The error grows with each factor of \(2^{10}\), since each contributes 2.4%.

3.7.4. KB versus KiB

That 2.4% is the source of a long-running confusion. Should a "kilobyte" be 1000 bytes (as "kilo" means everywhere else) or 1024 bytes (a convenient power of 2)? Both usages were common, so in 1998 the IEC introduced separate binary prefixes:

Decimal (SI) and binary (IEC) prefixes

SI (decimal): kilo (k) \(= 10^3\), mega (M) \(= 10^6\), giga (G) \(= 10^9\), tera (T) \(= 10^{12}\), peta (P) \(= 10^{15}\). IEC (binary): kibi (Ki) \(= 2^{10}\), mebi (Mi) \(= 2^{20}\), gibi (Gi) \(= 2^{30}\), tebi (Ti) \(= 2^{40}\), pebi (Pi) \(= 2^{50}\). So 1 KB \(= 1000\) bytes and 1 KiB \(= 1024\) bytes. Lower-case b means bits, upper-case B bytes: 1 Gbit/s is 125 MB/s.

Storage manufacturers use SI prefixes; Windows reports sizes in binary units but labels them "GB" and "TB"; macOS switched to SI units in 2009; RAM is always sold in binary sizes. The discrepancy grows with each prefix:

Bar chart: 2.4%, 4.9%, 7.4%, 10.0%, 12.6%, 15.3% for kilo through exa
Figure 23. How much larger each binary unit is than its decimal namesake. The gap compounds: \((1.024)^k - 1\).

Worked example: the "missing" space. A drive sold as 2 TB holds \(2 \times 10^{12}\) bytes. In TiB: Try it: Convert a 2 TB drive.

\[\frac{2 \times 10^{12} \text{ B}}{2^{40} \text{ B/TiB}} = \frac{2 \times 10^{12}}{1.0995 \times 10^{12}} \approx 1.82 \text{ TiB}.\]

Nothing is missing; the same quantity is being reported in a 10% larger unit.

def human_bytes(n, binary=True):
    """Format a byte count with SI (kB, MB, ...) or IEC (KiB, MiB, ...) prefixes."""
    base = 1024 if binary else 1000
    units = ["KiB", "MiB", "GiB", "TiB", "PiB"] if binary else ["kB", "MB", "GB", "TB", "PB"]
    if n < base:
        return f"{n} B"
    value, unit = float(n), "B"
    for u in units:
        if value < base:
            break
        value /= base
        unit = u
    return f"{value:.2f} {unit}"

disk = 2 * 10**12                       # a "2 TB" drive as sold
print(human_bytes(disk, binary=False))
print(human_bytes(disk, binary=True))
print(human_bytes(1536), human_bytes(1536, binary=False))
2.00 TB
1.82 TiB
1.50 KiB 1.54 kB
Computer-science connection: why powers of two everywhere

  • Addressing. Memory chips are addressed by binary numbers, so capacities come naturally in powers of 2.

  • Fast arithmetic. Multiplying or dividing by \(2^k\) is a shift by \(k\) bits (x << k, x >> k), and x % 2**k is a mask (x & (2**k - 1)). Hash tables with power-of-two capacity can compute a bucket index with a single AND instead of a division.

  • Doubling growth. Dynamic arrays (Python lists, std::vector, Java ArrayList) grow by a constant factor (often 1.5–2) when full. Because the sizes form a geometric sequence, the total copying cost over \(n\) appends is proportional to \(n\) — amortised constant time per append. Chapter 14 proves it with a geometric series.

  • Is it a power of two? n > 0 and n & (n - 1) == 0: subtracting 1 from a power of two flips its single 1 bit to 0 and all lower bits to 1, so the AND is zero.

Rice on a chessboard

A legend tells of a sage who asked a king for one grain of rice on the first square of a chessboard, two on the second, four on the third, doubling each time. The last square alone needs \(2^{63} \approx 9.2 \times 10^{18}\) grains; the whole board needs \(2^{64} - 1 \approx 1.8 \times 10^{19}\) — roughly a thousand years of current world rice production. Note that \(2^{64} - 1\) is also the largest unsigned 64-bit integer: the chessboard is a 64-bit register.

Try it: The 64-bit chessboard.

Bits and bytes calculator

A slider for bit width \(n\) from 1 to 128 that shows the number of patterns \(2^n\), the signed and unsigned ranges, the memory addressable with \(n\)-bit pointers, and a familiar real-world comparison ("more than the number of grains of sand on Earth"). A second panel converts any size among B, KB, KiB, MB, MiB, …, highlighting the percentage gap.

Try it: Open the Bits and bytes calculator

3.7.5. Exercises

  1. Without a calculator, estimate \(2^{24}\) and \(2^{50}\).

  2. How many bits are needed to give a unique ID to each of 10 billion devices?

  3. A 16 GiB RAM module holds how many bytes, exactly, as a power of 2? About how many in GB?

  4. Explain why x & 7 gives the same result as x % 8 for non-negative integers x.

Answers

  1. \(2^{24} = 2^{20} \cdot 2^4 \approx 10^6 \times 16 = 1.6 \times 10^7\) (true: 16,777,216 — the number of 24-bit colours). \(2^{50} = (2^{10})^5 \approx 10^{15}\) (true: \(1.13 \times 10^{15}\)).

  2. Need \(2^n \ge 10^{10}\). \(2^{30} \approx 10^9\) is too small; \(2^{33} \approx 8.6 \times 10^9\) is too small; \(2^{34} \approx 1.7 \times 10^{10}\) suffices: 34 bits.

  3. \(16 \times 2^{30} = 2^4 \cdot 2^{30} = 2^{34} = 17\,179\,869\,184\) bytes \(\approx 17.2\) GB.

  4. \(7 = 111_2\). The AND keeps the lowest three bits of x, which (by place value, Section 1.3) represent exactly the remainder of x on division by \(2^3 = 8\); all higher bits are multiples of 8.

3.8. A first look at exponential growth and logarithms

3.8.1. The problem

An algorithm that takes \(n^2\) steps on an input of size \(n\) and another that takes \(2^n\) steps both "get slower as \(n\) grows". Is the difference important? For \(n = 10\), \(n^2 = 100\) and \(2^{10} = 1024\) — not very different. For \(n = 100\), \(n^2 = 10\,000\) while \(2^{100} \approx 1.27 \times 10^{30}\). If each step took a nanosecond, the first finishes in 10 microseconds; the second would take about \(4 \times 10^{13}\) years, thousands of times the age of the universe.

3.8.2. Intuition

In \(n^2\) the variable is the base and the exponent is fixed: a power function (or polynomial). In \(2^n\) the variable is the exponent and the base is fixed: an exponential function. Exponential growth means a fixed percentage increase per step (here, 100% per step — doubling), and as we saw with compound interest (Section 2.5), repeated percentage increases snowball.

Graphs of 10n, n squared and 2 to the n for n from 0 to 12
Figure 24. Exponential growth eventually overtakes any power. Here \(2^n\) passes \(n^2\) for good at \(n = 5\) and leaves it far behind.
Exponential versus polynomial

An exponential expression has the variable in the exponent: \(2^n\), \(1.05^t\), \(10^x\). A polynomial (or power) expression has the variable in the base: \(n^2\), \(n^3\), \(x^{10}\). For any base \(b > 1\) and any power \(k\), \(b^n\) eventually exceeds \(n^k\) and the ratio grows without bound. Exponential growth with base \(b > 1\) has a doubling time; exponential decay (base between 0 and 1) has a half-life.

3.8.3. Running it backwards: the logarithm

Exponentiation answers "2 to the 10 is what?" (1024). The reverse question is "2 to the what is 1024?" The answer, 10, is the logarithm base 2 of 1024:

\[\log_2 1024 = 10 \quad\text{because}\quad 2^{10} = 1024 .\]

In general \(\log_b x\) is the exponent you must put on \(b\) to get \(x\). Logarithms turn multiplication into addition (since exponents add when powers multiply) and compress huge ranges into small ones. They deserve — and get — a full chapter, Chapter 12. Here are the two facts every programmer uses daily:

  • Bits needed. To give distinct codes to \(N\) things you need \(\lceil \log_2 N \rceil\) bits (\(\lceil\,\rceil\) means "round up"). For 10 billion devices: \(\log_2 10^{10} \approx 33.2\), so 34 bits — matching the exercise in Section 3.7.

  • Halving steps. Binary search on \(N\) sorted items halves the range each step, so it needs about \(\log_2 N\) steps: 20 steps for a million items, 30 for a billion. That \(\log_2 N\) grows so slowly is the mirror image of \(2^n\) growing so fast.

3.8.4. Where you’d use this

  • Savings and debt. £1000 at 5% a year, compounded for 30 years, becomes \(1000 \times 1.05^{30} \approx £4322\). The same arithmetic applied to an unpaid credit-card balance is why debt "suddenly" becomes unmanageable.

  • Biology. Under ideal conditions E. coli divides every 20 minutes. One cell becomes \(2^{30} \approx 1.07 \times 10^9\) cells after 30 doublings, i.e. just 10 hours. Food-safety rules about not leaving food at room temperature come from this calculation; the same doubling model is the starting point for epidemic forecasting.

  • Security. A password of 8 lowercase letters has \(26^8 \approx 2.1 \times 10^{11}\) possibilities. Each extra character multiplies the attacker’s work by 26, while each extra character only adds one to your typing. Cryptography is built on exactly this asymmetry: the defender’s cost grows linearly, the attacker’s exponentially.

Computer-science connection: big-O teaser

Algorithm analysis classifies running times by growth rate: \(O(\log n)\) (binary search), \(O(n)\) (a single pass), \(O(n \log n)\) (good sorting), \(O(n^2)\) (nested loops), \(O(2^n)\) (trying every subset). The notation \(O(\cdot)\), read "big-O", means "grows no faster than, up to a constant factor"; it is defined precisely in Chapter 16. The practical boundary is between polynomial and exponential: polynomial algorithms usually scale to large inputs; exponential ones hit a wall around \(n = 40\) to \(60\) no matter how fast the hardware. Doubling your computer’s speed lets an \(O(2^n)\) algorithm handle inputs just one larger.

Exponential intuition fails everyone

A lily pad patch doubles in size every day and covers the pond on day 30. On what day was it half covered? Day 29 — not day 15. Exponential processes look negligible for most of their history and then appear to explode. That is why early-stage epidemics, compound debts, and viral software growth are so routinely underestimated: on a linear chart, nearly all the change happens at the end.
Growth race

Choose growth functions (\(n\), \(n \log n\), \(n^2\), \(n^3\), \(2^n\), \(n!\)) and a "computer speed" in steps per second. A race shows the largest \(n\) each can handle in one second, one hour, and one year. Toggle the vertical axis between linear and logarithmic and watch the exponential curve become a straight line.

Try it: Growth curves on log axis · Growth race: one second · Growth race: one year

3.8.5. Exercises

  1. Compute \(\log_2 64\), \(\log_{10} 1000\), \(\log_3 81\), \(\log_2 \tfrac{1}{8}\).

  2. About how many steps does binary search need for \(10^{12}\) items?

  3. Which is larger for \(n = 30\): \(n^5\) or \(2^n\)? For \(n = 20\)?

Answers

  1. 6; 3; 4; \(-3\) (since \(2^{-3} = \tfrac18\)).

  2. \(10^{12} = (10^3)^4 \approx (2^{10})^4 = 2^{40}\): about 40 steps.

  3. \(n = 30\): \(30^5 = 24\,300\,000 \approx 2.4 \times 10^7\) and \(2^{30} \approx 1.07 \times 10^9\): the exponential is larger. \(n = 20\): \(20^5 = 3\,200\,000\) and \(2^{20} \approx 1\,048\,576\): the power is still larger. (They cross near \(n \approx 23\).)

3.9. Exponentiation by squaring

3.9.1. The problem

To compute \(3^{13}\) the obvious way, start with 3 and multiply by 3 twelve more times: 12 multiplications. To compute \(a^n\) that way takes \(n - 1\) multiplications. In cryptography (RSA, Diffie–Hellman) exponents have hundreds of digits — \(n \approx 2^{2048}\). At a billion multiplications per second the obvious method would not finish before the stars burn out. Yet your browser does it many times a second. How?

3.9.2. Intuition

Squaring doubles the exponent: \(3 \to 3^2 \to 3^4 \to 3^8 \to 3^{16}\) takes only four multiplications to reach the 16th power. Any exponent can be assembled from such powers, because any number is a sum of powers of two — that is exactly what its binary representation says (Section 1.3):

\[13 = 8 + 4 + 1 = 1101_2, \qquad\text{so}\qquad 3^{13} = 3^{8 + 4 + 1} = 3^8 \cdot 3^4 \cdot 3^1 .\]

The step from sum to product is the product law of exponents, read backwards. Compute the repeated squares \(3^1, 3^2, 3^4, 3^8\), and multiply together those whose bit is 1.

Chain 3, 9, 81, 6561 by squaring; 3, 81 and 6561 multiplied to give 3 to the 13th
Figure 25. Computing \(3^{13}\): square repeatedly, then multiply together the powers whose binary digit of 13 is 1.

3.9.3. The method

Example 22. Procedure — exponentiation by squaring (right-to-left binary method)

Input: a base \(a\) and an integer exponent \(n \ge 0\).

Steps:

  1. Set \(\text{result} = 1\) and \(\text{square} = a\).

  2. While \(n > 0\):

    1. If \(n\) is odd (its lowest binary digit is 1), set \(\text{result} = \text{result} \times \text{square}\).

    2. Set \(n = \lfloor n / 2 \rfloor\) (drop the lowest bit; \(\lfloor\,\rfloor\) means round down).

    3. If \(n > 0\), set \(\text{square} = \text{square} \times \text{square}\).

Output: \(\text{result} = a^n\).

Try it: 3¹³ by repeated squaring.

3.9.4. Worked example: \(3^{13}\)

Each row is one pass through the loop. "Bit" is the lowest binary digit of \(n\) at the start of the pass.

\(n\) bit square (\(= 3^{2^k}\)) result after this pass action

13

1

\(3\)

\(1 \times 3 = 3\)

multiply in, then square

6

0

\(9\)

\(3\)

skip, then square

3

1

\(81\)

\(3 \times 81 = 243\)

multiply in, then square

1

1

\(6561\)

\(243 \times 6561 = 1\,594\,323\)

multiply in; \(n\) becomes 0, stop

So \(3^{13} = 1\,594\,323\), using 3 squarings and 3 multiplications into the result: 6 instead of 12. (Counting the first "\(1 \times 3\)", which a careful implementation can skip.)

Why it is correct. At every stage, the invariant \(\text{result} \times \text{square}^{\,n} = a^{N}\) holds, where \(N\) is the original exponent. Initially it is \(1 \times a^N\). If \(n\) is even, squaring the square and halving \(n\) leaves \(\text{square}^n\) unchanged (power-of-a-power law: \((s^2)^{n/2} = s^n\)). If \(n\) is odd, we first move one factor of \(\text{square}\) into the result, making the remaining exponent even. When \(n\) reaches 0, \(\text{square}^0 = 1\) and the result is \(a^N\). (Loop invariants are a proof technique; Chapter 22 develops them.)

Cost. The loop runs once per binary digit of \(n\), about \(\log_2 n\) times, with at most two multiplications each: at most about \(2 \log_2 n\) multiplications instead of \(n - 1\). For a 2048-bit exponent, that is about 4096 multiplications instead of \(2^{2048}\).

3.9.5. Implementation

def fast_pow(a, n):
    """Compute a**n for an integer n >= 0 by repeated squaring.

    Returns (result, number_of_multiplications) so we can see the saving.
    """
    result, square, mults = 1, a, 0
    while n > 0:
        if n & 1:                 # lowest bit of n is 1: this power is needed
            result *= square
            mults += 1
        n >>= 1                   # move on to the next bit
        if n:                     # square only if more bits remain
            square *= square
            mults += 1
    return result, mults

print(fast_pow(3, 13))
print(fast_pow(2, 64)[0] == 2**64, fast_pow(2, 64)[1])
print(fast_pow(7, 0), fast_pow(1.0001, 10_000)[0])
(1594323, 6)
True 7
(1, 0) 2.718145926824356

(\(1.0001^{10\,000}\) being close to \(e = 2.71828\ldots\) is no coincidence; Chapter 12 explains it.)

In cryptography the numbers would become astronomically large, so every multiplication is followed by taking the remainder modulo some \(m\), which keeps all intermediate values below \(m\) (why this is legitimate is Chapter 23's business):

def mod_pow(a, n, m):
    """Compute a**n mod m by repeated squaring, keeping every number below m."""
    result, square = 1, a % m
    while n > 0:
        if n & 1:
            result = result * square % m
        square = square * square % m
        n >>= 1
    return result

print(mod_pow(3, 13, 1000), 3**13 % 1000)
print(mod_pow(2, 10**18, 10**9 + 7) == pow(2, 10**18, 10**9 + 7))
323 323
True

Python’s built-in three-argument pow(a, n, m) is exactly this algorithm. Note that mod_pow(2, 10**18, ...) takes about 60 loop iterations; the naive method would take \(10^{18}\).

3.9.6. Alternative approaches and choosing

  • Naive repeated multiplication: simplest, fine for small exponents (\(n\) up to a few dozen), and has the virtue of being obviously correct.

  • Recursive halving: \(a^n = (a^{n/2})^2\) if \(n\) is even, \(a \cdot a^{n-1}\) if odd. The same cost, and the clearest way to explain the idea; but recursion depth grows with \(\log_2 n\).

  • Left-to-right binary: scan the bits from the most significant end, squaring the result each step and multiplying by \(a\) when the bit is 1. Same count; preferred in hardware because it always multiplies by the same fixed \(a\).

  • Floating-point a ** n or math.pow: for real (non-integer) results, the library computes \(e^{n \ln a}\) using logarithms (Chapter 12), which is constant time but only approximately correct. For exact integer results, use integer exponentiation.

Choose integer squaring (or pow(a, n, m)) whenever exactness matters; choose floating-point power when you need real-valued results and can tolerate rounding.

Overflow and timing

In languages with fixed-width integers, square *= square overflows quickly — \(3^{40}\) does not fit in 64 bits — and silently wraps (Section 1.9). Reduce modulo \(m\) at every step, or use a big-integer type. In cryptographic code there is a subtler failure: because the method does extra work for each 1 bit, the running time leaks the number of 1 bits in a secret exponent. Real cryptographic libraries use constant-time variants (such as the Montgomery ladder) that do the same work for every bit.
Computer-science connection: squaring beyond numbers

The method works for any associative multiplication, not only numbers. Raising a \(2 \times 2\) matrix to the \(n\)th power by squaring computes the \(n\)th Fibonacci number in about \(\log_2 n\) matrix multiplications (Chapter 27). Squaring a graph’s adjacency matrix counts paths of doubling length (Chapter 25). Even string repetition s * n can be implemented by doubling. Associativity — the dull-looking law from Section 1.4 — is exactly what makes regrouping \(a \cdot a \cdots a\) into squares legitimate.

An ancient algorithm

The binary method of exponentiation appears in Pingala’s Chandaḥśāstra, an Indian text on poetic metre from around the 2nd century BCE, where it is used to count metrical patterns. The closely related "Russian peasant" or ancient Egyptian method of multiplication — doubling one number and halving the other — is the same idea with addition in place of multiplication: \(13 \times 3 = 3 \cdot 8 + 3 \cdot 4 + 3 \cdot 1\).
Square-and-multiply stepper

Enter a base and exponent. The exponent’s bits are shown as a row of switches; stepping through the loop lights up the current bit, shows the square and the result, and counts multiplications against the naive method. A slider pushes the exponent to thousands of bits (with a modulus) to show the naive count becoming astronomically large while the fast count grows by one or two per bit.

Try it: Open the square-and-multiply stepper · Huge powers mod m, instantly

3.9.7. Exercises

  1. Using the binary method, compute \(2^{21}\) by hand, showing the table of \(n\), bit, square, and result. Try it: Check 2²¹ step by step.

  2. How many multiplications does the method use (at most) for \(n = 1000\)? How many does the naive method use?

  3. Compute \(7^{10} \bmod 13\) with the binary method, reducing modulo 13 at every step. (\(\bmod\) means "remainder on division by".) Try it: Check 7¹⁰ mod 13.

Answers

  1. \(21 = 10101_2\).

    \(n\) bit square result

    21

    1

    2

    2

    10

    0

    4

    2

    5

    1

    16

    32

    2

    0

    256

    32

    1

    1

    65536

    \(32 \times 65536 = 2\,097\,152\)

    So \(2^{21} = 2\,097\,152\).

  2. \(1000 = 1111101000_2\) has 10 bits, six of them 1: 9 squarings and 6 multiplications into the result, 15 in all (or 14 if the first \(1 \times a\) is skipped), versus 999 naively.

  3. \(10 = 1010_2\). Squares mod 13: \(7\); \(7^2 = 49 \equiv 10\) (since \(49 = 3 \cdot 13 + 10\)); \(10^2 = 100 \equiv 9\); \(9^2 = 81 \equiv 3\). Bits (from the right) 0, 1, 0, 1 select the 2nd and 4th squares: \(10 \times 3 = 30 \equiv 4\). So \(7^{10} \bmod 13 = 4\). (The symbol \(\equiv\) means "leaves the same remainder"; see Chapter 23.)

US curriculum

Exponential growth and decay: Algebra I (F-LE). Logarithms: Algebra II and Precalculus. Exponentiation by squaring and big-O notation are not school mathematics; they belong to AP Computer Science (informally) and college algorithms and discrete mathematics courses.

3.10. Interactive tools

Browser tools on the companion website that go with this chapter. Each example link in the chapter opens one of them with that example already set up.

3.11. Mastery check

  1. Simplify, giving positive exponents: \(\dfrac{(2x^3y^{-1})^3}{4x^{-2}y^2}\).

  2. Explain, using the quotient law, why \(5^0 = 1\), and evaluate \(\left(\tfrac{3}{4}\right)^{-2}\).

  3. Evaluate \(64^{2/3}\) and \(81^{-3/4}\) without a calculator.

  4. Simplify \(\sqrt{75} + \sqrt{12}\) and rationalise \(\dfrac{2}{\sqrt{7} - \sqrt{5}}\).

  5. Compute \(\dfrac{(3.0 \times 10^{5})(8.0 \times 10^{-2})}{1.2 \times 10^{-4}}\) in scientific notation, to 2 significant figures.

  6. A cloud provider bills 500 GiB. How many GB is that, to 3 s.f.? How many bits does a 32-bit address bus address, and how many GiB is that in bytes?

  7. Which grows faster as \(n\) gets large, \(n^{10}\) or \(1.1^n\)? About how many steps does binary search take on 4 billion items?

  8. Compute \(5^{11}\) by exponentiation by squaring, showing the table, and say how many multiplications you used.

Decision rule: All correct without hesitation → you have finished the Foundations part; move on to Chapter 4. Stuck on 1–2 → reread the matching section (Section 3.2, Section 3.3, Section 3.4, Section 3.5, Section 3.6, Section 3.7, Section 3.8, Section 3.9). Stuck on more → work the section exercises first; exponent fluency is assumed constantly from here on.

Mastery check answers

  1. Numerator \(8x^9y^{-3}\). Divide: \(\tfrac{8}{4} x^{9-(-2)} y^{-3-2} = 2x^{11}y^{-5} = \dfrac{2x^{11}}{y^5}\).

  2. \(1 = \tfrac{5^n}{5^n} = 5^{n-n} = 5^0\). \(\left(\tfrac{3}{4}\right)^{-2} = \left(\tfrac{4}{3}\right)^2 = \tfrac{16}{9}\).

  3. \((\sqrt[3]{64})^2 = 4^2 = 16\). \(\tfrac{1}{(\sqrt[4]{81})^3} = \tfrac{1}{3^3} = \tfrac{1}{27}\).

  4. \(5\sqrt{3} + 2\sqrt{3} = 7\sqrt{3}\). \(\tfrac{2}{\sqrt7 - \sqrt5} \cdot \tfrac{\sqrt7 + \sqrt5}{\sqrt7 + \sqrt5} = \tfrac{2(\sqrt7 + \sqrt5)}{7 - 5} = \sqrt{7} + \sqrt{5}\).

  5. Numerator: \(24 \times 10^{3} = 2.4 \times 10^4\). Divide: \(\tfrac{2.4}{1.2} \times 10^{4 - (-4)} = 2.0 \times 10^{8}\).

  6. \(500 \times 2^{30} = 536\,870\,912\,000\) bytes \(\approx 537\) GB. A 32-bit bus addresses \(2^{32}\) locations; \(2^{32} \text{ bytes} = 4\) GiB.

  7. \(1.1^n\): every exponential with base above 1 eventually beats every power (though here only for quite large \(n\) — the crossover is in the hundreds). \(4 \times 10^9 \approx 2^{32}\), so about 32 steps.

  8. \(11 = 1011_2\). \(n = 11\), bit 1: result 5, square to 25. \(n = 5\), bit 1: result \(5 \times 25 = 125\), square to 625. \(n = 2\), bit 0: square to 390,625. \(n = 1\), bit 1: result \(125 \times 390\,625 = 48\,828\,125\). So \(5^{11} = 48\,828\,125\), with 3 squarings and 3 multiplications into the result (6 in all, 5 if the initial \(1 \times 5\) is not counted), versus 10 naively.