Search and Approximation

In the AM session, we introduced iteration and used it to verify quantified statements by exhaustive checks over a domain. The primality test asked: does there exist a divisor of $n$ in $\{2, \ldots, n-1\}$? The universal check asked: does every element of a domain satisfy some predicate? In each case, the loop served as a computational implementation of a quantifier, scanning the domain one element at a time.

In this recitation, we push the idea further. Instead of merely checking whether a value with a given property exists, we use loops to find it. The shift from verification to search is where iteration becomes powerful, and it brings with it new questions: how do we guarantee that a search terminates? How quickly does it converge? And what happens when the arithmetic itself introduces errors?

Exhaustive Enumeration

The simplest search strategy is the one we have already seen in the context of quantifiers: try every candidate in some domain until one works. When the domain is finite (or can be made finite by restricting attention to a bounded range), this approach is called exhaustive enumeration, and it is guaranteed to find a solution if one exists.

Cube Roots

Suppose we want to find the integer cube root of a perfect cube. Given an integer $n$, we seek an integer $x$ such that $x^3 = n$, or wish to report that no such integer exists.

The strategy is direct: test $x = 0, 1, 2, \ldots$ in order until either $x^3 = |n|$ (success) or $x^3 > |n|$ (failure, since $a < b$ implies $a^3 < b^3$ for positive integers). For negative $n$, the cube root is the negation of the cube root of $|n|$.

n = 27
x = 0

while x ** 3 < abs(n):
    x = x + 1

if x ** 3 != abs(n):
    print(f'{n} is not a perfect cube')
else:
    if n < 0:
        x = -x
    print(f'Cube root of {n} is {x}')

# Cube root of 27 is 3

Hand simulation for $n = 27$:

The loop terminates when $x = 3$, and since $3^3 = 27 = |n|$, the programme reports success.

Termination and Decrementing Functions

Every loop in a correct programme must eventually terminate (unless it is intentionally infinite, such as a server’s event loop). To prove termination rigorously, we exhibit a quantity that strictly decreases on each iteration and is bounded below.

The existence of a decrementing function converts the informal assertion “this loop eventually stops” into a rigorous mathematical argument. For the cube-root search, the natural candidate is $D = \lceil |n|^{1/3} \rceil - x$: it starts non-negative, and each iteration reduces it by $1$.

But this uses a notation we have not yet formalised. In Homework 2 (Problem 12), we introduced the floor function $\lfloor x \rfloor$, the greatest integer less than or equal to $x$. Its companion rounds upward.

Approximate Solutions

The cube-root search works only for perfect cubes: it demands an exact integer answer. But many numerical problems have no exact answer in the integers, or even in the rationals. The square root of $2$ is irrational, If we insist on exactness, no finite programme can return $\sqrt{2}$. The remedy is to relax the requirement: instead of the exact root, we seek a value close enough.

The idea is to accept a controlled amount of error. The tolerance $\varepsilon$ is chosen by the programmer: a smaller $\varepsilon$ demands a more accurate answer but, as we shall see, may require vastly more computation.

Exhaustive Search for Square Roots

We adapt exhaustive enumeration to the approximate setting. Instead of testing integers $0, 1, 2, \ldots$, we test values $0, \delta, 2\delta, 3\delta, \ldots$ where $\delta > 0$ is a small step size. For each candidate $\hat{x}$, we check whether $|\hat{x}^2 - n| < \varepsilon$.

n = 25
epsilon = 0.01
step = 0.0001
guess = 0.0
num_guesses = 0

while abs(guess ** 2 - n) >= epsilon and guess <= n:
    guess = guess + step
    num_guesses = num_guesses + 1

if abs(guess ** 2 - n) >= epsilon:
    print(f'Failed to find sqrt({n})')
else:
    print(f'{guess} is close to sqrt({n})')
    print(f'Number of guesses: {num_guesses}')

# 4.9999... is close to sqrt(25)
# Number of guesses: ~49990

The programme tests roughly $n / \delta$ candidates before reaching the neighbourhood of $\sqrt{n}$. For $n = 25$ and $\delta = 0.0001$, that is up to $250{,}000$ candidates. The result is not $5$ exactly, but that is by design: $4.9999\ldots$ is within $\varepsilon = 0.01$ of the true root, which is all we asked for.

n = 0.25
epsilon = 0.01
step = 0.0001
guess = 0.0

while abs(guess ** 2 - n) >= epsilon and guess <= n:
    guess = guess + step

if abs(guess ** 2 - n) >= epsilon:
    print(f'Failed to find sqrt({n})')

# Failed to find sqrt(0.25)

There is a deeper tension at work. The step size $\delta$ controls both the accuracy of the answer and the running time. A smaller $\delta$ gives a more precise result but requires more iterations. We need a fundamentally better strategy.

Bisection Search

The key observation is that exhaustive enumeration ignores information. Each failed guess tells us whether $\hat{x}^2$ was too small or too large, but we discard this knowledge and blindly proceed to $\hat{x} + \delta$. A cleverer strategy would use the comparison to eliminate half the remaining candidates at each step.

This is exactly what you do when looking up a word in a dictionary. You do not start at page one and scan every entry. You open the dictionary near the middle. If the word you seek comes after the visible page, you discard the first half; otherwise, you discard the second half. You then repeat on the surviving half, halving the search space each time.

Before stating the algorithm precisely, we fix notation for the sets it operates on.

The figure below traces bisection search for $\sqrt{25}$ on the interval $[0, 25]$. Each row shows one iteration: the grey bar is the surviving interval, the green diamond marks the midpoint, and the dashed red line marks the true root at $x = 5$.

Implementation

n = 25
epsilon = 0.01
low = 0.0
high = max(1.0, n)
guess = (low + high) / 2.0
num_guesses = 0

while abs(guess ** 2 - n) >= epsilon:
    num_guesses = num_guesses + 1
    if guess ** 2 < n:
        low = guess
    else:
        high = guess
    guess = (low + high) / 2.0

print(f'{guess} is close to sqrt({n})')
print(f'Number of guesses: {num_guesses}')

# 4.999923706054... is close to sqrt(25)
# Number of guesses: 13

Where exhaustive enumeration needed roughly $50{,}000$ guesses, bisection needs $13$. Note the use of max(1.0, n) for the upper bound: Python’s built-in max returns the larger of its arguments (Homework 2, Problem 4), so this ensures that $\sqrt{n}$ lies within $[0, h]$ whether $n \geqslant 1$ or $0 < n < 1$, correcting the failure we observed with exhaustive approximation.

Convergence

The bisection algorithm produces a sequence of guesses $m_0, m_1, m_2, \ldots$ that draw progressively closer to the true root. Each step halves the interval containing the root, so the distance between the guess and the true answer shrinks by a factor of $2$ at every iteration. This is an instance of a general phenomenon, a sequence of values approaching a target, which we will later study under the name convergence. For now, we establish the rate at which bisection approaches its target.

The bound involves the logarithm base $2$, written $\log_2(N)$: the power to which $2$ must be raised to produce $N$. For example, $\log_2(8) = 3$ since $2^3 = 8$, and $\log_2(1024) = 10$ since $2^{10} = 1024$. For values that are not exact powers of $2$, $\log_2$ is not an integer; for instance, $\log_2(2500) \approx 11.29$.

Machine Arithmetic

The approximate methods above assume that arithmetic on real numbers is exact: that $0.1 + 0.1 + 0.1$ equals $0.3$, that halving an interval truly halves it, and that the only source of error is the deliberate tolerance $\varepsilon$. On a computer, these assumptions are false.

Binary Fractions

Computers store numbers in binary. Just as the decimal system represents fractions using negative powers of $10$, so that $0.375 = 3/10 + 7/100 + 5/1000$, the binary system uses negative powers of $2$:

But not every decimal fraction is so accommodating.

This is not a quirk of the number $1/10$. A rational number $p/q$ in lowest terms has a finite binary expansion if and only if $q$ is a power of $2$. Since $10 = 2 \times 5$, the fraction $1/10$ requires an infinite repeating binary expansion, just as $1/3 = 0.333\ldots$ repeats infinitely in decimal.

Floating-Point Consequences

Python’s float type stores numbers using the IEEE 754 double-precision format: $64$ bits encoding a sign, an $11$-bit exponent, and a $52$-bit significand (plus one implied leading bit). This provides approximately $15$ to $17$ significant decimal digits of precision.

The practical consequence is that decimal constants which look exact in source code are silently rounded to the nearest representable binary fraction. We can expose this by using the format specifier :.20f inside an f-string, which prints $20$ digits after the decimal point:

print(0.1)              # 0.1  (display is rounded)
print(f'{0.1:.20f}')    # 0.10000000000000000555

print(0.1 + 0.1 + 0.1 == 0.3)    # False
print(f'{0.1 + 0.1 + 0.1:.20f}') # 0.30000000000000004441
print(f'{0.3:.20f}')              # 0.29999999999999998890

The sum $0.1 + 0.1 + 0.1$ is not $0.3$: it overshoots by approximately $5.5 \times 10^{-17}$. Meanwhile, the literal 0.3 is itself rounded downward from the true $3/10$. The two rounding errors go in opposite directions, so == returns False.

x = 0.0
count = 0

while x != 1.0:
    x = x + 0.1
    count = count + 1
    if count > 20:
        print('Gave up')
        break

x = 0.1 + 0.1 + 0.1
print(abs(x - 0.3) < 1e-9)   # True

total = 0.0

for i in range(1000):
    total = total + 0.1

print(f'{total:.20f}')    # not exactly 100.0
print(total == 100.0)      # False
print(abs(total - 100.0))  # small but nonzero

Exercises