8. Iteration with while¶
This work is licensed under Creative Commons Attribution-ShareAlike 4.0 International
8.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.
8.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.
8.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.
8.2.2. Example B: computing and printing the factorials less than N¶
As a variant of Exercise 5D above, 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 afor loop.
Thus, in place of the for loop in Example F above, 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.
8.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.
8.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]
8.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.
8.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.
8.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.