# 10. Iteration with `while`

#

This work is licensed under Creative Commons Attribution-ShareAlike 4.0 International

## 10.1. Introduction#

The last fundamental tool for describing algorithms is *iteration* or “looping”: tasks that repeat the same sequence of actions repeatedly, with possible variation like using different input values at each repetition.

The section on Iteration with `for`

covered the easier case where the number of iterations to be done is determined before we start;
now we consider the case where we must decide “on the fly” whether the iteration is finished, by checking some conditions as part of each repetition; this is usualy done with `while`

loops.

## 10.2. Repeating an initially unknown number of times, with `while`

loops#

Often, calculating numerical approximate solutions follows a pattern of iterative improvement, like

Get an initial approximation.

Use the best current approximation to compute a new, hopefully better one.

Check the accuracy of this new approximation.

If the new approximation is good enough, stop — otherwise, repeat from step 2.

For this, a `while`

loop can be used. Its general meaning is:

```
while "some logical statement is True":
repeat this
and this
and so on
when done with the last indented line, go back to the "while" line and check again
This less indented line is where we continue after the "while" iteration is finished.
```

### 10.2.1. Example A: Computing cube roots, quickly#

We are now ready for illustrations that do something more mathematically substantial: computing cube roots using only a modest amount of basic arithmetic. For now this is just offered as an example of programming methods, and the rapid success might be mysterious, but is explained in a numerical methods course like Math 245. Also, the phrase “backward error” should be familiar to students of numerical methods.

Note how the backward error allows us to check accuracy without relying on the fact that — in this easy case — we already know the answer. Change from ‘a=8’ to ‘a=20’ to see the advantage!

```
# We are going to approximate the cube root of a:
a = 8
```

```
# A first very rough approximation:
root = 1
# I will tolerate an error of this much:
error_tolerance = 1e-8
# Aside to students in a numerical course: this is a _backward error_ specification.
# The answer "root" should satisfy root**3 - a = 0, so check how close we are:
while abs(root**3 - a) > error_tolerance:
root = (2*root + a/root**2)/3
print(f'The new approximation is {root:20.16g}, with backward error of {abs(root**3 - a):e}')
print('Done!')
print(f'The cube root of {a:g} is approximately {root:20.16g}')
print(f'The backward error in this approximation is {abs(root**3 - a):.2e}')
```

```
The new approximation is 3.333333333333333, with backward error of 2.903704e+01
The new approximation is 2.462222222222222, with backward error of 6.927316e+00
The new approximation is 2.081341247671579, with backward error of 1.016332e+00
The new approximation is 2.003137499141287, with backward error of 3.770908e-02
The new approximation is 2.000004911675504, with backward error of 5.894025e-05
The new approximation is 2.000000000012062, with backward error of 1.447429e-10
Done!
The cube root of 8 is approximately 2.000000000012062
The backward error in this approximation is 1.45e-10
```

**Aside D:** I have thrown in some more refinements of output format control, “:20.16g”, “:e” and “:.2e”.
If you are curious, you could try to work out what they do from these examples, or read up on this, for example in the notes on formatted output
But that is not essential, at least for now.

### 10.2.2. Example B: computing and printing the factorials less than N#

As a variant of Example F: The first n factorials in the previous section,
if we want to compute the all factorials that are less than N, we do not know in advance how many there are, which is a problem with a `for`

loop.

Thus, in place of the `for`

loop used there, we can do this:

```
N = 1000
```

```
"""
Compute and print all factorials less than N
"""
i = 0
i_factorial= 1
print(f"{i}! = {i_factorial}")
while i_factorial < N:
i += 1
i_factorial *= i
if i_factorial < N: # We have to check again, in case the latest value overshoots
print(f"{i}! = {i_factorial}")
```

```
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
```

If we want to store all the values, we cannot create an array of the correct length in advance, as was done in Example F.
This is one place where Python *lists* have an advantage over Numpy *arrays*; lists can be extended incrementally.
Also, the way we do this introduces a new kind of Python programming tool: a *method* for transforming an *object*.

## 10.3. Appending to lists, and our first use of Python *methods*#

In an exercise like the above, it might be nice to accumulate a list of all the results, but the number of them is not known in advance, so the array creation strategy seen in Example F cannot be used.

This is one place where Python lists have an advantage over Numpy arrays; lists can be extended incrementally.
Also, the way we do this introduces a new kind of Python programming tool: a *method* for transforming an object.
The general syntax for methods is

```
object.method(...)
```

which has the effect of transforming the object, and can take a tuple of arguments, or none. Thus, it is sort of like

```
object = method(object, ...)
```

but for one thing, avoids repetition of the object name.

**Aside E: A taste of object-oriented programming.** This is our first encounter with the notation and concepts of *object-oriented programming*, which is so important in languages like **Java** and **C++**.
A *method* is a special kind of function [here `append()`

] which does things like transforming an *object* [here the list `factorials`

].

This course will use only little bits of this object-oriented programming style, but Python has a full collection of tools for it, which CSCI students in particular will probably appreciate.

### 10.3.1. Example C: creating and appending to a list#

We start with an empty list and then append values with the method `.append()`

.

```
listOfPrimes = [] # An empty list
print(listOfPrimes)
listOfPrimes.append(2)
print(listOfPrimes)
listOfPrimes.append(3)
print(listOfPrimes)
```

```
[]
[2]
[2, 3]
```

### 10.3.2. Example D: Storing a list of the values of the factorials the factorials less than N#

Now we use this new list manipulation tool to create the desired list of factorial values: creating a list of all values \(i!\) with \(i! < N\).

```
"""
Collecting a Python list of all the factorials less than N.
"""
factorials = [] # Start with an empty list
i = 0
i_factorial = 1
print(f"{i}! = {i_factorial}")
factorials.append(i_factorial)
while i_factorial < N:
i += 1
i_factorial *= i
if i_factorial < N: # We have to check again, in case the latest value overshoots
print(f"{i}! = {i_factorial}")
factorials.append(i_factorial)
print()
print(f"The list of all factorials less that {N} is {factorials}")
```

```
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
The list of all factorials less that 1000 is [1, 1, 2, 6, 24, 120, 720]
```

**Note:** Of course, the list could then be converted to an array with

```
factorials = numpy.array(factorials)
```

if having an array is useful later.

### 10.3.3. Exercise A: Fibonacci numbers less than \(N\)#

Write a Python function that inputs a natural number \(N\), and with the help of a `while`

loop, computes and prints in turn each Fibonacci number less than or equal to \(N\).

For now the values are only printed, and so one does not need to store them all; only a couple of the most recent ones.

Note well; this is all \(F_i \leq N\), not the Fibonacci numbers up to \(F_N\).
Thus we do not know how many there are initially: this is the scenario where `while`

loops are more natural than `for`

loops.

**Written planning.** Again, start by working out and writing down your mathematical plan, and check it with me before creating any Python code.

### 10.3.4. Exercise B: all output via a `return`

statement; no `print`

to screen in the function#

Modify your function from the previous exercise to cumulate the needed Fibonacci numbers in a Python list, and `return`

this list.
This time, your function itself should not `print`

anything: instead, your file will display the results with a single `print`

function after invoking the function.

**NOTE:** This approach of separating the **calculations** in a function from subsequent **display of results** is the main way that we will arrange things from now on.