The WHILE Loop

A for loop repeats a fixed, known number of times. Many problems instead need a loop that repeats until some condition changes, meaning the exact number of repetitions is not known ahead of time. A while loop handles this case, repeating its body for as long as a condition remains True.

WHILE Loop Structure

A while loop has the following ingredients.

  1. The reserved keyword while.

  2. A conditional statement that evaluates to True or False.

  3. A colon :.

  4. A block of code, called the loop body, which is indented with four spaces.

The following while loop mimics a for loop by updating a counter variable i at each iteration.

i = 0
while i < 5:
    print(i**2)
    i += 1
print("Done looping")

0
1
4
9
16
Done looping

At first, the condition i < 5 is True because i = 0 is set before the loop. During each iteration of the loop, the value of i is increased by one, until finally i = 5 and therefore i < 5 evaluates to False, at which point the loop exits and execution continues at the line after the indentation ends. In other words, the loop continues until i >= 5, the logical negation of i < 5.

In the previous example, it is easy to see that there will be 5 total iterations through the loop. With other conditional statements, the number of iterations may not be so easy to determine beforehand.

x = 10
count = 0
while x > 1e-12:  # While x is larger than 0.000000000001,
    x /= 2        # cut it in half.
    count += 1
print(count, x)

44 5.684341886080801e-13

After 44 times through the loop, x is finally smaller than 1e-12.

Infinite Loops

A for loop over a finite range always terminates on its own. A while loop is not guaranteed to terminate: if the update step is missing or never changes the condition’s truth value, the loop repeats forever. The following would never stop, since i is never updated.

i = 0
while i < 5:  # i never changes, so this condition is always True!
    print(i**2)
print("Done looping")

This is called an infinite loop. Always check that the condition governing a while loop can eventually become False, otherwise your program may never terminate.

Quick Check

What is the output of the following code?

x = 1
count = 0
while x < 20:
    x = x * 2
    count += 1

print(x, count)
Answer
32 5

  • In the loop body, x goes from 1 to 2 to 4 to 8 to 16 to 32.

  • The condition x < 20 is True in the first five passes, then False once x = 32.

  • count is incremented once per pass, so it ends at 5.

Problem 6

Consider the sequence of numbers defined through the following iteration:

\[\begin{split} x_{k+1} = \begin{cases} \frac{1}{2}x_k &\text{if}~x_k~\text{is even,} \\ 1 + 3x_k &\text{if}~x_k~\text{is odd.} \end{cases} \end{split}\]

For example, if \(x_0 = 3\), then the sequence is \((3, 10, 5, 16, 8, 4, 2, 1)\). In this case, the sequence reaches \(x_n = 1\) in \(n = 7\) steps.

The Collatz conjecture is the claim that no matter which positive integer is chosen as the starting point \(x_0\), the sequence will always reach \(1\) eventually. No one has proven that this is always the case, but a counterexample has yet to be discovered.

Write a function named collatz_steps() that accepts a positive integer \(x_0\) and counts the steps needed to reach \(x_n = 1\) by repeatedly applying the rule above. Return the number of steps \(n\).

Hint 1: An integer is even if, when divided by 2, the remainder is zero.
Hint 2: In the even case, use integer division //, not float division /.

Test Cases

print(collatz_steps(1))
print(collatz_steps(3))
print(collatz_steps(27))

0
7
111

Problem 7

In the famous wheat and chessboard problem, one grain of wheat is placed on the first square of a chessboard, then two grains are placed on the next square, then four, then eight, and so on, with each square containing twice as many grains as the square before it. The standard version of the problem is to find out the total number of grains placed on the 64 chessboard squares, which turns out to be about eighteen quintillion (\(1.84 \times 10^{19}\)).

Write a function named wheat_squares() that accepts a positive integer \(n\) and finds the least number of squares needed for the running total of grains to reach or surpass \(n\). Return the number of squares used, counting the square that first makes the total reach or exceed the threshold.

Test Cases

print(wheat_squares(1))
print(wheat_squares(10))
print(wheat_squares(1_000_000_000_000))  # One trillion.

1
4
40

Iterations and WHILE Loops

A while loop is one way to encode stopping criteria for numerical iterations. Consider the sequence defined by

\[ x_{k+1} = \frac{1}{2}x_k + 3, \qquad x_0 = 1. \]

Checking that two consecutive terms are very close to each other, that is, that

\[ |x_{k} - x_{k-1}| < \varepsilon \]

for some small \(\varepsilon > 0\), is one potential stopping criterion. However, the number of steps this takes is not known in advance. The following uses a while loop to handle this.

x = 1
tolerance = 1e-8

count = 0
x_new = 0.5 * x + 3
while abs(x_new - x) >= tolerance:
    x = x_new
    x_new = 0.5 * x + 3
    count += 1

print(x_new, count)

5.999999990686774 28

The loop condition is the logical negation of the stopping criterion: if we keep iterating as long as \(|x_{k} - x_{k-1}| \ge \varepsilon\), we will only stop when \(|x_{k} - x_{k-1}| < \varepsilon\).

Break

A loop sometimes needs to stop as soon as something specific happens, rather than waiting for its condition to become false on its own. The break statement immediately exits the nearest enclosing loop, skipping any remaining passes. This works with both for and while loops.

for i in range(1000000000):
    if i > 100:
        break
print(i)

101

A break is especially important when the condition for a while loop is always True. A loop like this only ever stops when a break is reached, and this makes the stopping condition easy to spot: it is whatever comes right before the break. This is also the usual way to add a safeguard against an iteration that never converges, by capping the number of passes.

x = 0.0
tolerance = 1e-8
max_iterations = 1000

count = 0
while True:
    x_new = 0.5 * x + 3
    if abs(x_new - x) < tolerance:
        break  # Stopping criterion fulfilled!
    x = x_new
    count += 1
    if count >= max_iterations:
        break  # Maximum number of iterations reached.

print(x_new, count)

5.9999999944120646 29

Problem 8

The bisection method estimates a root of a function \(f\) by repeatedly shrinking an interval \([a_{k}, b_{k}]\) that contains one. Since \(\sqrt{z}\) is the positive root of \(f(x) = x^2 - z\), the method can be used to estimate square roots. For a given positive number \(z\), the iteration is

\[\begin{split} \begin{aligned} x_{k} &= \frac{1}{2}(a_{k} + b_{k}) \\[.75em] a_{k+1} &= \begin{cases} x_{k} &\text{if}~x_{k}^2 - z < 0 \\ a_{k} &\text{if}~x_{k}^2 - z \ge 0, \end{cases} \qquad a_{0} = 0, \\[.75em] b_{k+1} &= \begin{cases} b_{k} &\text{if}~x_{k}^2 - z < 0 \\ x_{k} &\text{if}~x_{k}^2 - z \ge 0, \end{cases} \qquad b_{0} = \max\{1, z\}. \end{aligned} \end{split}\]

Write a function named sqrt_bisection() that accepts a positive number \(z\) and a positive stopping tolerance \(\epsilon\), then applies the iteration above until the current iterate \(x_k\) satisfies

\[ |x_k^2 - z| < \epsilon. \]

Return the final iterate \(x_k\).

Hint: consider using the following outline.

  1. Set the initial values \(a = a_0\) and \(b = b_0\).

  2. Set \(x = \frac{1}{2}(a + b)\).

  3. Enter a loop that ends when \(|x^2 - z| < \epsilon\).

  4. In the loop, if \(x^2 - z < 0\), set \(a = x\), leaving \(b\) unchanged.

  5. Otherwise, if \(x^2 - z \ge 0\), set \(b = x\), leaving \(a\) unchanged.

  6. Update \(x = \frac{1}{2}(a + b)\).

  7. After the loop, return \(x\).

Test Cases

print(sqrt_bisection(2, 1e-2))
print(sqrt_bisection(2, 1e-5))
print(sqrt_bisection(2, 1e-12))

1.4140625
1.414215087890625
1.4142135623733338