Back to courses

MATH40006 2022 23 assessment3

English review edition prepared on 4 October 2026 from a preserved source copy. It is a later presentation, not the historical study interface. Source checks and difficulty judgements describe the original material author's own process; they do not indicate Imperial College London endorsement.

Source SHA-256: 726c0f3fe891152bbd0efc18a0bcca64256b26a73de180fa856ced94b793bcfb
Source date: 2026-07-31

Notes — cell 1

# M40006 In-Course Assessment

# 23 March 2023, 2.10-4.10 pm

## Two Hours

### Answer all questions, submitting your answers as a single Jupyter notebook.

Notes — cell 2

To carry out this assignment, you may find useful, possibly amongst others:
<ul>
 <li>from the <code>sympy</code> module, the functions <code>Integer</code>, <code>together</code>, <code>expand</code>, <code>symbols</code>, <code>lambdify</code>, <code>diff</code>, <code>solve</code> and <code>Eq</code>, and the <code>subs</code> method;</li>
 <li>from the <code>numpy</code> module, the functions <code>linspace</code> and <code>dot</code>;</li>
 <li>from either <code>numpy</code> or <code>math</code>, the functions <code>sin</code> and <code>log2</code>, and the constant <code>pi</code>;</li>
 <li>from the <code>random</code>submodule of <code>numpy</code>, the <code>randint</code> function;</li>
 <li>from the <code>pyplot</code> submodule of <code>matplotlib</code>, the <code>plot</code>, function;</li>
</ul>

We recommend that you execute the following cell:

Code — cell 3

import sympy as sp
import numpy as np
import math
import matplotlib.pyplot as plt
import random
sp.init_printing()

Notes — cell 4

# Section A: Legendre Polynomials (35 marks)

## Question 1 (35 marks)

The Legendre polynomials, $P_n(x)$ are a family of functions satisfying the following equations:

$$\begin{eqnarray*}
P_0(x)&=&1,\\
P_1(x)&=&x,\\
n\,P_n(x)&=&(2\,n-1)\,x\,P_{n-1}(x) - (n-1)\,P_{n-2}(x) \quad \mbox{for }n\ge 2.
\end{eqnarray*}$$

The following code defines an <b>iterative</b> function for generating Legendre polynomials as SymPy expressions in a SymPy variable (note that the `together` function in SymPy simply makes sure that the expression has a common denominator rather than consisting of separate fractions):

Code — cell 5

def legendre_poly(n, x):
    "Calculates the nth Legendre polynomial as a SymPy expression"
    
    # known cases
    if n == 0:
        return sp.Integer(1)
    elif n == 1:
        return x
    
    # general case
    else:
        pa, pb = sp.Integer(1), x
        
        # loop from r=2 to r=n
        for r in range(2, n+1):
            pa, pb = pb, sp.together(sp.expand(((2*r-1)*x*pb - (r-1)*pa)/r))
            
        return pb

Notes — cell 6

(a) Test this function by setting up `x` as a SymPy symbolic variable and calculating expressions for $P_0(x), P_1(x), P_2(x), P_3(x)$ and $P_4(x)$.

Code — cell 7

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 8

(b) Write and run some code that does the following.
<ul>
 <li>Calculate the $5$th Legendre polynomial as an expression in $x$, assigning it to the variable <code>lp</code>;</li>
 <li>Using <code>lambdify</code> with appropriate arguments, create a function, <code>lpfn</code>, that takes a single argument and returns the value of the $5$th Legendre polynomial for that value of $x$; so that <code>lpfn(0.3)</code> should return the value of $P_5(0.3)$. Make sure you set your function up so that it also works if the argument is a NumPy array.</li>
 <li>Using the ordinary <code>plot</code> function from <code>pyplot</code>, plot $P_5(x)$ against $x$ for $100$ values of $x$ between $-1$ and $1$ inclusive.</li>
</ul>

Code — cell 9

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 10

(c) On a single pair of axes, plot $P_n(x)$ against $100$ values of $x$ for $-1\le x \le 1$, for all values of $n$ between $1$ and $10$ inclusive.

Code — cell 11

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 12

(d) Write and test a <b>recursive</b> version of `legendre_poly`: that is, a function that takes as its arguments a non-negative int $n$ and a symbolic variable $x$, and returns $P_n(x)$ as an expression in $x$, using recursion instead of iteration. 

You will probably want to give this function a slightly different name, so the original one still works. 

Make sure your function works fairly efficiently as $n$ gets larger; you may want to consider an "inner function and outer function" design, or something equivalent, to achieve this.

Code — cell 13

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 14

(e) Using either the original `legendre_poly` function or your recursive version (equal marks either way), write and run some code that does the following:
<ul>
 <li>Calculate the $5$th Legendre polynomial, $P_5(x)$, as an expression in $x$, assigning it to the variable <code>lp</code>;</li>
 <li>Calculate the derivative, ${P_5}'(x)$, as an expression in $x$;</li>
 <li>Find and print, as a Python list of SymPy expressions, the five solutions in $x$ of the equation $P_5(x)=0$;</li>
 <li>Find and print, as a Python list of <b>floats</b>, the values of $\displaystyle{\frac{2}{(1-x^2)\,{P_5}'(x)^2}}$ at each of those five values of $x$.</li> 
</ul>

Code — cell 15

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 16

(f) One major use of Legendre polynomials is in numerical integration. 

It is known that if $f$ is a (sufficiently "well-behaved") integrable function defined on the integral $[a, b]$ then
$$\int_a^b f(x)\,dx$$
is approximated well by
$$\frac{b-a}{2}\,\sum_{i=1}^{n}w_i\,f\left(\frac{b-a}{2}\xi_i + \frac{b+a}{2}\right),$$
where:
<ul>
 <li>the $\xi_i$ are the $n$ roots of $P_n(x)=0$;</li>
 <li>for each $i$, $\displaystyle{w_i=\frac{2}{(1-{\xi_i}^2)\,{P_5}'(\xi_i)^2}}$.</li>
</ul>
Using this formula, with $n=5$, calculate an approximate value, as a float, for
$$\int_0^{\pi/2}\sin x\,dx,$$
and comment briefly on its accuracy.

Code — cell 17

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 18

YOUR ANSWER HERE

Notes — cell 19

# Section B: Integer Square Roots (65 marks)

The bulk of this section concerns various solutions to the problem of calculating <b>integer square roots</b>; Question 2 is about some very efficient Python features you may not have met that might help.

Notes — cell 20

## Question 2 (10 marks)

The operator `<<`, in Python as in many computer languages, performs a "left bit shift", which is to say that for positive ints `a` and `r`, the operation
```python
a << r
```
is equivalent to multiplying `a` by `2**r`.

(a) Verify this by performing a series of tests.

Code — cell 21

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 22

(b) Investigate the operator `>>` by testing it with different positive integer values, and describe as accurately as possible what it does.

Code — cell 23

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 24

YOUR ANSWER HERE

Notes — cell 25

(c) Execute the following code, which explores the behaviour of a method called `bit_length`:

Code — cell 26

print([(n,n.bit_length()) for n in range(230,270)])

Notes — cell 27

Investigate further, and then write down, as precisely as possible, a relationship between the numbers `n.bit_length()` and $\log_2 n$.

Code — cell 28

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 29

YOUR ANSWER HERE

Notes — cell 30

## Question 3 (20 marks)

The <b>integer square root</b> of a positive integer $n$ is the greatest integer $r$ such that $r^2\le n$; that is, the value of $\left\lfloor \sqrt{n} \right\rfloor$, where the brackets $\left\lfloor .. \right\rfloor$ indicate "integer part".

There are various methods for calculating the integer square root of $n$. One of the simplest, and crudest, is simply to test $r=1, 2, 3, \dots$ etc until you find a value for which $(r+1)^2 > n$, and then to return this value of $r$.

(a) Write a function called `isqrt_version0` that takes a single positive integer $n$ as its argument and, using the crude "brute force" method outlined above, calculates its integer square root.

Code — cell 31

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 32

(b) Test the function on some suitable values of $n$; for each value, verify that the calculated integer square root $r$ satisfies the inequalities $r^2\le n$ and $(r+1)^2 > n$.

Your values of $n$ should include:
<ul>
 <li>at least one fairly small value (say two digits);</li>
 <li>at least one somewhat larger value (say eight digits);</li>
 <li>at least one perfect square;</li>
 <li>at least one number of the form $a^2-1$;</li>
 <li>at least one number of the form $a^2+1$.</li>
</ul>

(Note: this method is quite slow for <em>very</em> large values of $n$, so be cautious about the values you use in your testing; values up to a hundred million or so should be fine, though.)

Code — cell 33

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 34

(c) The number of iterations carried out by this function is equal to the value of the integer square root itself. Describe the dependence of the number of iterations on $n$ using the "big $\Theta$" (big Theta) notation.

Notes — cell 35

YOUR ANSWER HERE

Notes — cell 36

(d) The integer square root of $n$ can be proved to be greater than or equal to $2^{\left \lfloor \frac{1}{2}\,\log_2(n) \right \rfloor}$. 

Make use of this fact to write an improved function, `isqrt_version0a`, which initializes $r$ at this value instead of $1$ and therefore uses fewer iterations.

For full marks, make appropriate use in your code of `<<`, `>>` and/or `bit_length()`.

Test your function on a similar set of values of $n$ to the ones you used in part (b).

Code — cell 37

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 38

(e) Find, in terms of $n$, the number of iterations carried out by this function in the cases where:

(i) $n$ is an even power of $2$;

(ii) $n$ is one less than an even power of $2$.

You should give a reason for each of your answers, but you are welcome to introduce an "iteration count" variable into your code and experiment if you like.

Code — cell 39

# Space for experimenting if needed

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 40

YOUR ANSWER HERE

Notes — cell 41

(f) For your improved function, describe the dependence of the number of iterations on $n$ using the "big $\Omega$" and "big $O$" notations.

Notes — cell 42

YOUR ANSWER HERE

Notes — cell 43

## Question 4 (15 marks)

A more efficient method for finding integer square roots goes as follows.

<ul>
 <li>Initialize $r$ to zero.</li>
 <li>Calculate <code>smax</code>, the greatest <b>even</b> value of $s$ for which $2^s \le n$.</li>
 <li>For descending <b>even</b> values of $s$ between <code>smax</code> and zero inclusive:
 <ul>
 <li>Multiply $r$ by $2$.</li>
 <li>If $(r+1)^2 \le \left\lfloor n/2^s \right\rfloor$, add $1$ to $r$;</li>
 </ul>
 </li>
 <li>Return the final value of $r$</li>
</ul>

(a) Write a function, `isqrt_version1`, that calculates integer square roots using this method.

Test your function on some suitable values of $n$. As this method is much more efficient, you should be able to go up to, say, hundred-digit values of $n$ quite comfortably.

Code — cell 44

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 45

(b) For this method, describe the dependence of the iteration count on $n$ using "big $\Theta$" notation, giving reasons for your answer. [Hint: consider the relationship between $n$ and `smax`.]

Code — cell 46

# Space for experimenting if needed.
# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 47

YOUR ANSWER HERE

Notes — cell 48

(c) <b>Challenging</b>: Explain how this method works, by working through, by hand, the calculation of the integer square root of $120$.

Notes — cell 49

YOUR ANSWER HERE

Notes — cell 50

## Question 5 (20 marks)

Integer square roots can also be found using the discrete version of <b>Newton's method</b>. This starts with an $r_0$ known to be greater than or equal to $\left \lfloor \sqrt{n} \right\rfloor$, and performs the iteration

$$r_{k+1} = \left\lfloor \frac{1}{2} \left(r_k + \left\lfloor\frac{n}{r_k}\right\rfloor\right)\right\rfloor$$

until $r_{k+1}$ is no longer less than $r_k$, at which point the value of $r_k$ is returned.

(a) Write a function, `isqrt_version2`, which uses this method, starting with $r_0 = \left\lfloor n/2 \right\rfloor$. (You may need to make special arrangements for the few cases for which $r_0$ is not greater than $\left\lfloor \sqrt{n} \right\rfloor$.)

Test on some suitable values of $n$, including at least one quite large integer (again your function should be able to handle hundred-digit integers quite comfortably).

Code — cell 51

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 52

(b) Analysing, from first principles, the dependence of the number of iterations on $n$ for this method is tricky. Instead, introduce an iteration count variable, and hence calculate the number of iterations needed for $n=2, 4, 8, \dots, 2^{30}$.

Code — cell 53

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 54

(c) State a conjecture, using "big $\Theta$" notation, about the dependence of the number of iterations on $n$.

Notes — cell 55

YOUR ANSWER HERE

Notes — cell 56

(d) The integer square root of $n$ is known to be strictly less than $2^{\left\lfloor \frac{1}{2}\,\log_2(n) \right\rfloor+1}$. Using this fact, write and test an improved version, `isqrt_version2a`, that uses fewer iterations.

Code — cell 57

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 58

(e) It is claimed that this improved method is $\Theta(\log(\log n))$. By introducing an iteration count variable (if you haven't already), and looking at the iteration counts for 
$$n=2^{100}, 2^{200}, 2^{300}, \dots, 2^{10000},$$ 
comment on how consistent this claim is with the data.

Code — cell 59

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 60

YOUR ANSWER HERE