Imperative Knowledge and Computation

There are two kinds of knowledge a mathematical text can record. Declarative knowledge is a statement of fact: the square root of a positive real $x$ is the positive $y$ with $y^2 = x$. Imperative knowledge is a recipe: a sequence of instructions which, followed to the letter, produces it. A machine can carry out imperative knowledge, but not declarative knowledge.

At its lowest level a computer does two things: it performs arithmetic, and it stores the results. It does billions of operations a second and can store a great deal.

Finite rules out an infinite list of instructions. Unambiguous rules out a step whose meaning depends on who is reading it. After finitely many steps rules out a recipe that never returns an answer; of the three conditions it is the hardest to check.

Writing an algorithm down needs a notation for assignment, which has no counterpart in an equation. We write

for the instruction “replace the current value of $g$ by the value of the expression $e$”. It is an instruction, not a statement about $g$. The instruction $g \defeq g + 1$ makes sense, while the equation $g = g + 1$ has no solutions.

Here is Heron of Alexandria’s method for the square root of a real $x > 0$.

1. Choose any guess $g > 0$.
2. If $g^2$ is close enough to $x$, stop and return $g$.
3. Otherwise perform $g \defeq \tfrac{1}{2}\bigl(g + x/g\bigr)$.
4. Go back to step 2.

The procedure has the two ingredients of every algorithm: a list of operations, and control flow, the rule deciding which operation comes next. Control flow depends on tests that answer yes or no, and it lets a fixed piece of text describe a computation whose length is not fixed.

Computability

Early machines were fixed-program computers, wired to solve one problem. The stored-program computer keeps the instructions and the data they act on in the same memory, so that a single interpreter can execute any legal instruction sequence handed to it. A program counter walks the interpreter through the instructions in order, deviating only where control flow says to jump. Since the output of a computation may itself be a sequence of instructions, a machine of this kind can write its own programs.

There is, however, no algorithm which, given an arbitrary program and its input, decides in finitely many steps whether that program eventually stops or runs forever. This is the halting problem. Because it is unsolvable, the clause “stops after finitely many steps” in the definition of an algorithm has to be proved for each algorithm separately; it cannot be checked mechanically.

Syntax and Semantics

A program is a piece of text, and like a mathematical formula it has a meaning only if it obeys three kinds of rule.

1. Primitives. The atoms of the language: numeric literals such as 3.2, strings of text, and operators such as + and *.
2. Syntax. The rules saying which arrangements of primitives are well formed. 3.2 + 3.2 is well formed; 3.2 3.2 is not. Violations are caught before a single instruction runs.
3. Static semantics. The rules saying which well-formed arrangements have a meaning. Adding a number to a piece of text has the right shape, operand-operator-operand, and still means nothing.

A program that obeys all three has a semantics: exactly one meaning, fixed by the language and not by the reader. An English sentence, by contrast, can have several.

So when a program misbehaves the machine has not misunderstood it: the error is in what was written. It shows up in one of three ways: the program stops with an error, it runs forever, or it finishes and returns the wrong answer. The third gives no sign that anything is wrong, which is why a program needs a proof of correctness and not only a run that looked right.

Problems, Words and Languages

To compare algorithms for a problem, the problem has to be stated in a fixed form. A machine reads and writes finite strings of characters, so problems are stated in terms of strings.

A set $S$ is finite if there is an injection $S \to \{1, \ldots, n\}$ for some $n \in \mathbb{N}$, and infinite otherwise; the number of elements of a finite set is written $|S|$. A set admitting an injection into $\mathbb{N}$ is countable, and the infinite ones among them are the countably infinite sets of the last lesson.

A decision problem is one whose answer is yes or no, and we state such a problem by naming its instances and asking the question.

Primality
Input:    n ∈ N.
Question: is n prime?

A machine works directly only on discrete problems. A numerical problem must have its instances and its answers written as finite strings, and no finite string names an arbitrary real; rounding error is the difference between a real number and the string used for it.

Pseudocode

An algorithm does not depend on a programming language, and is usually written in pseudocode: the control flow and the assignments written out, without the details a particular language would require. An algorithm in pseudocode names its input and its output, and uses $\defeq$ for assignment and output for the result.

The Square of an Integer
Input:  x ∈ N.
Output: the square of x.

    result ≝ x · x
    output result

We use pseudocode to describe an algorithm and Python to run it.

Objects and Types

A Python program is a sequence of definitions and commands, evaluated in order by an interpreter. A command is called a statement, and it instructs the interpreter to do something. A call to the built-in print writes to the screen: it takes any number of arguments, separates them by spaces, and follows them by a newline unless told otherwise.

print("Algorithm")
print("terminated.")

# several arguments, and a different ending
print("Algorithm", "terminated", end=".\n")

Writing an f before the opening quote of a string makes it an f-string, in which any expression placed in braces is evaluated and its value substituted:

n = 7
print(f"{n} squared is {n * n}")   # 7 squared is 49

In mathematics the legality of an operation depends on what it is applied to: addition is defined for numbers, composition for maps. In Python each value is an object, and every object has a type, which fixes the operations allowed on it. The interpreter uses types to enforce static semantics.

Types divide into scalar, meaning indivisible, and non-scalar, meaning having internal structure. Python has four primitive scalar types.

1. int, the integers, written as usual: 5, -12.
2. float, an approximation to the reals, written with a decimal point (3.0, -28.72) or in scientific notation (1.6e-19). Memory is finite and the reals are not, so a float holds one of finitely many values and float arithmetic is not the arithmetic of $\mathbb{R}$: the expression 0.1 + 0.2 == 0.3 evaluates to False.
3. bool, inhabited by exactly two values, True and False.
4. None, inhabited by one value, used for the absence of a result.

Expressions and Relational Operators

Objects combined with operators according to the syntax form an expression, and every expression evaluates to a single object of some type. The built-in type reports which type an object has:

type(5)     # int
type(5.0)   # float

Control flow needs tests that come out True or False, and these are built with the relational operators <, <=, >, >=, == and !=. Every one of them evaluates to a bool.

Python’s notation differs from the pseudocode here. Mathematical assignment $g \defeq e$ is written in Python with a single equals sign, g = e. Testing whether two expressions have the same value is ==, and testing that they do not is !=.

3.0 + 2.0   # the float 5.0
3 != 2      # the bool True

Arithmetic Operators

Addition, subtraction and multiplication are +, - and *, and exponentiation is **. Division splits into three operators, two of which are the floor and the remainder of the last lesson.

1. / always evaluates to a float: 5 / 3 gives 1.6666666666666667.
2. // is floor division, the largest integer not exceeding the quotient. So 5 // 3 is 1 and -4 // 3 is -2.
3. % is the remainder: 5 % 3 is 2. A modern processor carries out % and // in a few clock cycles, so we count each of them as a single elementary operation.

a == b * (a // b) + a % b

Compound expressions are read by precedence: ** binds most tightly, then *, /, // and %, then + and -.

print(2 + 3 * 4)   # 14, not 20
print(5 + 4 % 3)   # 6, not 0   (% binds as tightly as * and /)
print(2 ** 3 * 4)  # 32, not 4096

Operators of equal precedence are read by associativity. Most associate to the left; exponentiation associates to the right.

print(5 - 4 - 3)    # -2, not 4
print(4 ** 3 ** 2)  # 4 ** 9 = 262144, not 64 ** 2 = 4096
print((4 ** 3) ** 2)  # 4096

Logical Operators

The three logical connectives, negation, conjunction and disjunction, are implemented as the keywords not, and and or. They act on bool values and are fixed by these tables, in which T and F abbreviate True and False.

So a and b holds exactly when both do, a or b when at least one does, and not a reverses the value. All three are reserved words: they are part of the syntax and cannot be reassigned or used as names.

Both and and or stop as soon as the answer is settled: in a and b the expression b is never evaluated when a is False, and in a or b it is never evaluated when a is True.

(3 != 2) and (5 % 3 == 0)   # False, since 5 % 3 is 2

The Operators in One Place

The compound assignments abbreviate an update in place: total += x means total = total + x.

The bitwise operators (<<, >>, &, |, ^, ~, &=, |=, ^=), and with them <<= and >>=, are not used in this lesson.

Variables and State

An equation such as $y = x^2$ ties $y$ to $x$ permanently: change $x$ and $y$ changes with it. Assignment does not. It creates a binding, at one moment in time, between a name and one object in memory, and the binding stands until it is replaced.

pi = 3.14159
radius = 11.0
area = pi * (radius ** 2)
radius = 14.0

The third statement evaluates pi * (radius ** 2) to the single float 380.13239 and binds area to it. The fourth rebinds radius, and area is untouched: it is bound to a number, not to a formula. This lets Heron’s method overwrite its guess $g$ at every step while the input $x$ stays fixed.

Names and Comments

A program has to be checked by a reader, and a correct program with opaque names is hard to check. The # symbol begins a comment, which the interpreter ignores.

a = 3.14159
b = 11.2
c = a * (b ** 2)

pi = 3.14159
diameter = 11.2
area = pi * ((diameter / 2.0) ** 2)

The two blocks compute different numbers, and only the second makes it visible which one is the area of a circle: the first squares a diameter where it should square a radius, and its names hide the fact.

Multiple Assignment

Several names may be bound at once. Every expression on the right of the = is evaluated in full before any name on the left is rebound, so the two sides do not interfere.

x, y = 2, 3
x, y = y, x

print("x is", x)   # x is 3
print("y is", y)   # y is 2

Exchanging two values therefore needs no third name to hold one of them.

Numbers in Other Bases

The string $2812$ is a representation of a number rather than the number itself. Each digit occupies a position whose value is a power of ten:

The rightmost digit sits in the units place, $10^0 = 1$, and each position to its left is worth ten times the one before, so the leftmost $2$ of $2812$ stands for two thousand while the rightmost stands for two. This is a positional numeral system: what a digit means depends on where it sits.

Base ten comes from counting on fingers, not from mathematics. Ten is divisible by only four numbers, $1, 2, 5$ and $10$, which limits how easily fractions can be handled; twelve, divisible by $1, 2, 3, 4, 6$ and $12$, would serve better. A digital circuit holds two voltage levels, high and low, so machines work in base two, where arithmetic is carried out directly by sequences of logic gates.

That every natural number has exactly one representation of this shape in any base $b > 1$ is Theorem 2.21 of the last lesson, and the notation is fixed by its corollary. Read as a statement about digit strings, it says that the base-$b$ expansion of $n \in \mathbb{N}_0$ is the string $d_r d_{r-1} \cdots d_0$ satisfying three conditions:

1. $n = d_r b^r + d_{r-1}b^{r-1} + \cdots + d_0 b^0$;
2. every digit satisfies $0 \leqslant d_i < b$;
3. if $n > 0$ then the leading digit $d_r$ is not $0$, and the expansion of $0$ is the string $0$ in every base.

The first condition says that the digits record how many copies of each power of $b$ are wanted; in decimal the places from the right are units, tens, hundreds, and in binary they are $1, 2, 4, 8, 16, \ldots$. The second restricts the available digits to $0, 1, \ldots, b-1$, and without it uniqueness fails: if $\text{X}$ were a decimal digit standing for ten, then $\text{X}2$ and $102$ would both represent one hundred and two. The third bans leading zeros, without which $01423$ and $1423$ would be different strings for one number.

Following the corollary we write

for the number with this expansion, and a string carrying no subscript is decimal.

Python writes the three bases a machine uses with bin, oct and hex, each returning a string carrying a prefix that names the base:

n = 1023

bin(n)   # '0b1111111111'
oct(n)   # '0o1777'
hex(n)   # '0x3ff'

The same prefixes may be typed directly as literals, so the conversions can be checked against each other:

a = 0b1111111111
b = 0o1777
c = 0x3FF

a == b == c == 1023   # True

For any other base, int takes the base as a second argument and reads a string written in it:

int('1101220', 3)   # 1023
int('sf', 36)       # 1023

Branching

Everything written so far is a straight-line program: the statements run in the order they appear, each exactly once. Such a program is easy to reason about, and limited. If one atomic operation takes one unit of time, a straight-line program of $N$ lines takes at most $N$ units however large its input, because no line ever runs twice.

The first way to let a program do more is branching: a test is evaluated, and the block of statements that runs next depends on the answer.

Conditional Statements

The basic branching construct is if–else. It consists of a test evaluating to True or False, a block run when the test is True, and an optional else block run when it is False.

Python marks the extent of a block by indentation. Where other languages use braces or an end keyword, Python uses the whitespace itself, so the layout of a program shows its structure.

x = 14

if x % 2 == 0:
    print("The integer is even.")
else:
    print("The integer is odd.")

print("Branching complete.")

The test uses x % 2, the remainder on division by two, which is the last digit of the binary expansion of x. It is 0 for even x and 1 for odd. The final print is not indented, so it belongs to neither block and runs either way; indenting it by four spaces would make it part of the else and suppress it for even x.

Because indentation carries meaning, a long expression cannot be broken across lines anywhere. A backslash at the end of a line continues it explicitly, and a line inside unclosed brackets continues implicitly.

# explicit continuation
alpha = 1.61803398875 + \
        2.71828182845 + \
        3.14159265359

# implicit continuation, inside parentheses
beta = (1.61803398875 +
        2.71828182845 +
        3.14159265359)

Nested Conditionals

A block inside a branch may itself branch, which builds a decision tree.

Where the cases are mutually exclusive, a chain of else blocks each containing one if grows an extra level of indentation per case. The keyword elif collapses the chain: its test is evaluated exactly when every test above it has come out False.

n = 15

if n % 2 == 0:
    if n % 3 == 0:
        print("n is a multiple of 6.")
    else:
        print("n is even, but not divisible by 3.")
elif n % 3 == 0:
    print("n is odd and divisible by 3.")
else:
    print("n is not divisible by 2 or 3.")

Compound Tests and Updating State

Tests may be combined with and, or and not. How they are combined changes how much work the program does.

Take the problem of returning the largest positive number among $a$, $b$ and $c$, or, if none of them is positive, the smallest of the three. Each of the three is positive or not, so there are $2^3 = 8$ cases, and a program with one branch per case tests the same three comparisons over and over.

Binding a provisional answer and updating it only when a later value beats it replaces the eight cases by three independent tests:

a, b, c = -5, 12, 7

# if none is positive the answer is the smallest, so start there
target = min(a, b, c)

if a > 0:
    target = a
if b > 0 and b > target:
    target = b
if c > 0 and c > target:
    target = c

print(target)   # 12

The built-in min returns the smallest of its arguments, and max the largest. Each of the three variables has its sign examined once.

Conditional Expressions

For a choice between two values rather than between two blocks of work, Python supplies the conditional expression, which packs an if–else into a single expression:

expression_if_true if test else expression_if_false

A variable may therefore be bound according to a test without a multi-line block. The absolute value of Definition 1.65 is given by cases, so there are several ways to compute it. The most direct is a standard if block:

x = -10

if x < 0:
    x = -x

For a body consisting of a single short statement, Python permits writing the block on the same line as the if:

if x < 0: x = -x   # only for very short statements

Branching can also be avoided entirely by using the fact that True and False behave as $1$ and $0$ in arithmetic:

y = (x < 0) * (-x) + (x >= 0) * x   # works, but hard to read

This works, but it is hard to read, it evaluates both branches every time, and it hides the case split inside a multiplication. The conditional expression is clearer:

y = x if x >= 0 else -x

Python also provides the built-in abs for this purpose, so abs(-10) returns 10.

Constant Time

Branching does not remove the limit on straight-line programs. Each block is entered at most once on a run, so if one atomic operation takes one unit of time, a branching program of $N$ lines can never exceed $N$ units, and its maximum running time is hard-bounded by a constant $k \leqslant N$.

Every straight-line program runs in constant time, and so does every branching program, with $k$ the number of lines.

Iteration

Branching programs are bound by constant time: each instruction is executed at most once, so the whole computation is capped by the static length of the source. The base expansions of the first chapter show the limit. Every step applied the same pair of operations, // and %, to the current quotient, and with no way of repeating those operations automatically we performed each step by hand. Computing the factorial of $n$, testing whether a number is prime, extracting the digits of an arbitrarily large base expansion: these tasks take longer on larger inputs, and no branching program can perform them.

Iteration sends execution back to an instruction already passed.

The While Loop

Python’s while statement has the syntax of if: a test, a colon, and an indented body. The test is evaluated; if it is True the body runs in full and control returns to the test; if it is False the body is skipped and execution continues after the loop.

The following program computes $x^2$ by adding $x$ to a running total $x$ times.

x = 3
ans = 0
num_iterations = 0

while num_iterations != x:
    ans = ans + x
    num_iterations = num_iterations + 1

print(f"{x} squared is {ans}")

Recording the values of the variables each time the test is reached, as though one were the interpreter, is called hand simulation, and it is how we check what a loop does.

On the fourth evaluation num_iterations has reached x, and the program prints 3 squared is 9.

Whether it stops at all depends on x, and there are three cases. If $x = 0$, the test fails at once, the body never runs, and 0 squared is 0 is printed. If $x > 0$, the counter starts below x and rises by exactly one per pass, so after $x$ passes it equals x and the loop ends with the right answer. If $x < 0$, the counter runs through $0, 1, 2, \ldots$ and never equals a negative number: the test is never False, and the program runs forever. This is an infinite loop.

Weakening the test to num_iterations < abs(x) stops the loop after abs(x) passes, but each pass still adds the negative number x, so the program would announce that $(-3)^2 = -9$. The body has to be corrected too:

x = -3
ans = 0
num_iterations = 0

while num_iterations < abs(x):
    ans = ans + abs(x)
    num_iterations = num_iterations + 1

print(f"{x} squared is {ans}")   # -3 squared is 9

n = 72658489290098
n = abs(n)

while n >= 10:
    n = n // 10

print(n)   # 7

Two further pieces of Python are needed for the problems below. Writing + between two strings joins them end to end, so 'X' + 'X' is 'XX'. And input(prompt) prints its prompt, waits for the user to type a line, and returns what was typed as a string; int converts a string of digits to the integer it denotes, so int(input('n? ')) reads a number.

num_x = int(input('How many times should I print the letter X? '))
to_print = ''
# append X to to_print num_x times
print(to_print)

Leaving a Loop Early

A break statement ends the loop containing it at once and passes control to the first statement after it, without returning to the test.

# the smallest positive integer divisible by both 11 and 12
x = 1

while True:
    if x % 11 == 0 and x % 12 == 0:
        break
    x = x + 1

print(x, 'is divisible by 11 and 12')   # 132 is divisible by 11 and 12

The test while True never fails, so the break is the only way out, and the proof that the loop stops is about the break. This arrangement suits a loop whose exit condition is natural to check partway through the body rather than at the top.

Where one loop sits inside another, a break ends only the loop that immediately contains it; the outer loop carries on.

The For Loop

The loops above share a pattern: a counter is set up, tested at the top, and advanced at the bottom of the body. The for statement does that bookkeeping itself. Its form is

for variable in sequence:
    body

The variable is bound to the first entry of the sequence and the body runs; then to the second, and the body runs again; and so on until the sequence is exhausted or a break intervenes.

total = 0

for num in (77, 11, 3):
    total = total + num

print(total)   # 91

The object (77, 11, 3) is a tuple, an ordered finite sequence written in parentheses.

The Range Function

The sequence is most often produced by range, which generates a progression of integers and takes one, two or three arguments.

With one argument, range(stop) gives $0, 1, \ldots, \text{stop} - 1$.

for i in range(4):
    print(i)     # 0, then 1, then 2, then 3

With two, range(start, stop) gives $\text{start}, \text{start}+1, \ldots, \text{stop}-1$. The lower end is included and the upper end is not.

total = 0

for x in range(5, 11):
    total = total + x

print(total == 5 + 6 + 7 + 8 + 9 + 10)   # True

With three, range(start, stop, step) gives $\text{start}, \text{start} + \text{step}, \text{start} + 2\,\text{step}, \ldots$, and stops before reaching stop. For positive step the last entry is the largest $\text{start} + i\,\text{step}$ below stop; a negative step descends instead, so range(40, 5, -10) gives $40, 30, 20, 10$.

total = 0

for x in range(10, 3, -1):
    if x % 2 == 1:
        total = total + x

print(total)   # 9 + 7 + 5 = 21

Choosing the step to land on the right numbers is often more trouble than testing them inside the body. The following sums the odd numbers between m and n whatever the parity of m:

m, n = 4, 10
total = 0

for x in range(m, n + 1):
    if x % 2 == 1:
        total = total + x

print(total)   # 5 + 7 + 9 = 21

The two-argument form covers the one-argument form: range(0, 3) produces the same sequence as range(3). The entries are produced one at a time as the loop asks for them rather than stored all at once, so range(1000000) costs no more memory than range(3).

x = -3
ans = 0

for num_iterations in range(abs(x)):
    ans = ans + abs(x)

print(f"{x} squared is {ans}")   # -3 squared is 9

Reassigning the Loop Variable

Assigning to the loop variable inside the body does not disturb the loop.

for i in range(2):
    print(i)
    i = 0
    print(i)

This prints 0, 0, 1, 0 and stops. The sequence is fixed when the for statement is first reached, and at the start of each pass the variable is rebound to the next entry of it, whatever happened to the variable in between. The loop is equivalent to

index = 0
last_index = 1

while index <= last_index:
    i = index
    print(i)
    i = 0
    print(i)
    index = index + 1

For the same reason, changing a variable that was used in the range call has no effect, because the call is evaluated once:

x = 1

for i in range(x):
    print(i)
    x = 4

# prints 0, and nothing else

An inner for is a different matter: its range call is reached afresh on every pass of the outer loop and so is evaluated again.

x = 3

for j in range(x):
    print('Outer')
    for i in range(x):
        print('  Inner')
        x = 2

The outer range(x) is evaluated once, with $x = 3$, so the outer loop makes three passes. The inner range(x) sees $x = 3$ on the first pass and $x = 2$ afterwards, giving $3 + 2 + 2 = 7$ inner passes in total.

Iterating Over a String

A string is a sequence of characters. Its positions are numbered from $0$, so a string of length $k$ occupies positions $0, 1, \ldots, k-1$: len(s) gives the length, s[i] gives the character at position i, and the slice s[i:j] gives the characters at positions i up to but not including j. That upper end is excluded for the same reason it is excluded from range, and the two conventions agree: s[0:len(s)] is the whole of s, and the positions it covers are exactly those produced by range(len(s)).

Combined with in, the for statement walks a string directly, binding the variable to one character at a time and dispensing with the positions altogether.

total = 0

for c in '12345678':
    total = total + int(c)

print(total)   # 36

Nested Loops

A loop inside a loop runs the inner loop to completion on every pass of the outer one.

n = 5

for row in range(n):
    for col in range(n):
        print('*', end='')
    print()

*****
*****
*****
*****
*****

n = 5

for row in range(n):
    print(row, end=' ')
    for col in range(row):
        print('*', end=' ')
    print()

0
1 *
2 * *
3 * * *
4 * * * *

Continue and Pass

Two keywords sit alongside break. A continue abandons the rest of the current pass and goes straight to the next one: back to the test for a while, on to the next entry for a for. A pass does nothing, and exists because Python’s syntax requires a statement in places where no action is wanted.

for n in range(200):
    if n % 3 == 0:
        continue
    elif n == 8:
        break
    else:
        pass
    print(n, end=' ')

# 1 2 4 5 7

The multiples of three never reach the print, the loop ends when n reaches $8$, and the remaining values pass through the else branch and are printed.

Divisibility and Primality

Checking that $91$ is composite takes a single operation once the divisor $7$ is known, since 91 % 7 == 0 settles it; finding the divisor is where the work lies. Read as an instruction, the definition says to test every candidate between $2$ and $n - 1$ and to stop at the first one that divides.

n = 91
is_prime = n >= 2

for factor in range(2, n):
    if n % factor == 0:
        is_prime = False
        break

if is_prime:
    print(f'{n} is prime')
else:
    print(f'{n} is not prime')

# 91 is not prime

One divisor settles the question, so the loop stops at the first one it finds. Wrapping the whole thing in a second loop lists the primes below a bound:

for n in range(2, 100):
    is_prime = True
    for factor in range(2, n):
        if n % factor == 0:
            is_prime = False
            break
    if is_prime:
        print(n, end=' ')

# 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Trial Division to the Square Root

Testing every candidate up to $n - 1$ is more than necessary.

Only the integers up to $\sqrt{n}$ need be tested, and $2$ can be dealt with separately so that the loop skips the even candidates:

n = 1010809
is_prime = n >= 2

if n > 2 and n % 2 == 0:
    is_prime = False
else:
    max_factor = round(n ** 0.5)
    for factor in range(3, max_factor + 1, 2):
        if n % factor == 0:
            is_prime = False
            break

print(f'{n} is prime: {is_prime}')   # 1010809 is prime: True

round(n ** 0.5) returns either $\lfloor \sqrt{n} \rfloor$ or one more, never less, so the loop may test one candidate too many and never one too few.

The first program tests up to $n - 2$ candidates and the second about $\sqrt{n}/2$: for $n = 1010809$, about a million tests against about five hundred. Python’s time module measures it. The statement import time makes the module’s tools available, and time.time() returns the current time in seconds. A colon inside the braces of an f-string says how to format the value: :.2f prints it with two digits after the decimal point.

import time

n = 1010809

time0 = time.time()
is_prime_basic = True
for factor in range(2, n):
    if n % factor == 0:
        is_prime_basic = False
        break
time1 = time.time()
print(f'Basic: {(time1 - time0) * 1000:.2f} ms')

time0 = time.time()
is_prime_fast = n >= 2
if n > 2 and n % 2 == 0:
    is_prime_fast = False
else:
    max_factor = round(n ** 0.5)
    for factor in range(3, max_factor + 1, 2):
        if n % factor == 0:
            is_prime_fast = False
            break
time1 = time.time()
print(f'Optimised: {(time1 - time0) * 1000:.2f} ms')

print(is_prime_basic == is_prime_fast)   # True

The two agree, and on an ordinary machine the first takes tens of milliseconds where the second takes a small fraction of one.

Searching for the $n$th Object

Finding the $n$th number with a given property is a different kind of problem: the answer is not known in advance, so there is no range to run over. A counter of successes and a candidate that advances by one at a time turn it into a while loop.

target = 5
found = 0
guess = 0

while found <= target:
    guess = guess + 1
    if guess % 4 == 0 or guess % 7 == 0:
        found = found + 1

print(f'Counting from zero, entry {target} of the multiples of 4 or 7 is {guess}')
# entry 5 is 16

The multiples of four or seven begin $4, 7, 8, 12, 14, 16$, and counting from zero the entry numbered $5$ is $16$. Substituting the primality test for the divisibility test finds the $n$th prime:

target = 10
found = 0
guess = 1

while found <= target:
    guess = guess + 1
    is_prime = guess >= 2
    if guess > 2 and guess % 2 == 0:
        is_prime = False
    else:
        max_factor = round(guess ** 0.5)
        for factor in range(3, max_factor + 1, 2):
            if guess % factor == 0:
                is_prime = False
                break
    if is_prime:
        found = found + 1

print(f'Counting from zero, prime {target} is {guess}')   # prime 10 is 31

The primes are $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31$, and counting from zero the one numbered $10$ is $31$.

Digits in an Arbitrary Base

In the first chapter we read off base-$b$ expansions by hand, dividing by $b$, recording the remainder as the next digit from the right, and continuing with the quotient until it reached zero. Automating that needs a way of repeating instructions until a condition is met, which the while loop provides. The number of repetitions is the number of digits, and it is not known before the divisions are done.

The loop below carries out the proposition. Digits are produced from the last to the first, so each new one is put in front of what has been built so far, and digits above nine are turned into letters: str(d) turns the number d into the string of its decimal digits, ord(c) gives the code number of the character c, chr(k) gives the character with code k, and the codes of A to Z run consecutively.

n = 12345
b = 17
digits = ''

while n > 0:
    remainder = n % b
    if remainder < 10:
        digits = str(remainder) + digits
    else:
        digits = chr(ord('A') + remainder - 10) + digits
    n = n // b

print(digits)   # 28C3

Running Time

Timing the two primality tests measured one machine at one time. The number of instructions a program performs depends on the compiler and on the hardware, and we do not in any case know it exactly. We want a statement about the algorithm instead: how the amount of work grows with the input.

Two things remain to be fixed: how the size of an input is measured, and how precisely we count.

Landau Notation

The constant $\alpha$ must not depend on $n$; were it allowed to, every function would lie in $O(1)$ and the definition would say nothing. Nor does the inequality have to hold everywhere: it may fail for finitely many $n$, so changing $f$ at the first million values leaves the statement untouched.

Instead of $f \in O(g)$ one usually writes

read ”$f$ is big-Oh of $g$”. The equals sign here is not the symmetric one, since $O(g)$ is a set and $f$ is a member of it; the notation is standard nonetheless.

The argument of the first two examples works for any polynomial.

The Cost of Schoolbook Arithmetic

We all learned at school how to add and multiply natural numbers written in decimal: once $m + n$ and $mn$ are known for the single digits $0 \leqslant m, n \leqslant 9$, sums and products of arbitrary numbers follow by working column by column and carrying. These schoolbook methods are algorithms in the sense of the first chapter, and we can count their cost.

Throughout this section the size of the input is the number of digits, which for $x$ written in base $b$ is $\lfloor \log_b x \rfloor + 1$ by Corollary 2.22.