Dr Alexander Fletcher

Autumn 2021/22

By the end of this lecture, you will be able to:

- refactor Python code using for loops;
- improve the performance of code;
- write instructions on how to produce Pascal's triangle.

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.

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.

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 8.)

Next week's homework 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:**

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

**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:

- they know how to calculate ${n \choose i}$;
- they will follow your instructions literally (they won't try to guess what you
*really*mean); - they have not seen Pascal's triangle before;
- when writing they start at the left of the page;
- they can move down to the beginning of the next line but never up;
- on each line they can write something, or leave gaps of a given number of spaces, or move to the next column;
- they are writing on paper that extends infinitely to the right.

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.