MAS115 Mathematical Investigation Skills: Python

Dr Alexander Fletcher
Autumn 2020/21

3  More program writing

3.1  Refactoring

Last time we were trying to find the factors of all numbers up to 50,000 using trial division and ended up with the following code.

1
2
3
4
5
6
7
8
9
n = 1
while n <= 50000:
    print("n =", n)
    i = 1
    while i <= n:
        if n % i == 0:
            print(i)
        i = i + 1
    n = n + 1

We have subsequently learnt about the for loop, which will achieve the same as our while loops in this case. We can refactor the code, that is rewrite it to make it more readable, but without changing the way it works.

3.2  Improving the performance

The following code is now more readable and easier to understand. This tidying up of the code is like rewriting rough work.

1
2
3
4
5
6
for n in range(1, 50001):
    print("n =", n)
    
    for i in range(1, n+1):
        if n % i == 0:
            print(i)

This code runs very slowly for big numbers. Can we do anything to speed it up and improve the perfomance? Go back and think about the method we were using.

3.3  Timing a program

There are several ways that you can time how long a program takes to run. One way is to import and use the time module, as follows.

1
2
3
4
5
6
7
import time

start = time.time()
# Insert your program here
end = time.time()

print("This program took", end - start, "seconds")

(You will learn more about Python modules in Week 6.)

3.4  Task: Producing Pascal's triangle I

The homework this week is to write a program to draw Pascal's triangle. We will now look at what steps are needed to do that, but we won't produce the Python code.

Task:

  1. Write out the first five lines of Pascal's triangle.
  2. What is the 8th line of Pascal's triangle?
  3. What is the $n$th line of Pascal's triangle?

3.5  Task: Producing Pascal's triangle II

Task: Produce detailed written instructions on how to draw the first $n$ lines of Pascal's triangle, for $n\in\mathbb{N}$.

Things you should assume about the reader:

(The reader will behave like a computer.)

3.6  Task: Producing Pascal's triangle III

After a short break...

Task: Take a fresh piece of paper and precisely follow the instructions you have been given, using $n = 6$. You should do no more and no less than is written in the instructions.