MATH40006 Practice Paper 4

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: 9d209e6ac138dc211dcc217ba35189f31ce7bd44b70f001680797260a2026aca
Source date: 2026-08-06

Notes — cell 1

# MATH40006 Revised Historical-Coverage Mock 4

**Time allowed:** 60 minutes 
**Total marks:** 50 
**Questions:** 3 (20 + 20 + 10) 
**Role:** 2021-23 early historical ability: Legendre quadrature, integer square roots and LCM complexity

Answer all questions in this Jupyter notebook. Show testing code and outputs. Unless the question explicitly requests an in-place operation, functions should return a value without changing their inputs.

Code — cell 2

import numpy as np
import sympy as sp
import matplotlib.pyplot as plt
import pandas as pd
from time import perf_counter
from copy import copy
import pickle
import ast
import math
sp.init_printing()

def legendre_poly(n,x):
    if n==0:return sp.Integer(1)
    if n==1:return x
    pa,pb=sp.Integer(1),x
    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

def lcm_add(a,b):
    a0,b0=a,b
    while a!=b:
        if a<b:a+=a0
        else:b+=b0
    return a
def lcm_euclid(a,b):
    a0,b0=a,b
    while b>0:a,b=b,a%b
    return a0*b0//a

Notes — cell 3

## Question 1 (20 marks)

The supplied `legendre_poly` generates the Legendre polynomial P_n(x) iteratively.

(a) Test P_0 through P_4 as exact SymPy expressions. **[2]**

(b) Lambdify P_6 for NumPy arrays and plot it on 200 points of [-1,1]. **[3]**

(c) Write an efficient recursive version using only one recursive call at each level, and compare it with the iterative function for n=0,...,8. **[5]**

(d) Find the four exact roots of P_4 and the corresponding Gauss-Legendre weights `2/((1-xi**2)*P_4'(xi)**2)` as floats. **[5]**

(e) Use those roots and weights to approximate integral_0^1 exp(-x) dx, and compare with `1-exp(-1)`. **[5]**

Code — cell 4

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 5

## Question 2 (20 marks)

(a) State the exact relation between `n.bit_length()` and floor(log2(n)) for positive n. **[2]**

(b) Implement the bit-by-bit integer square-root algorithm: choose the greatest even `smax` with 2**smax <= n, then build r from descending even shifts. **[7]**

(c) Test small, hundred-digit, square, one-below-square and one-above-square cases using the defining inequalities. **[3]**

(d) Give a Theta bound for the number of loop iterations. **[2]**

(e) Implement discrete Newton iteration with a bit-length power-of-two starting value strictly above sqrt(n). **[5]**

(f) Compare the two functions on several values. **[1]**

Code — cell 6

# YOUR CODE HERE
raise NotImplementedError()

Notes — cell 7

## Question 3 (10 marks)

The supplied functions compute an LCM by repeated addition and by Euclid's gcd algorithm.

(a) Produce instrumented versions returning `(lcm,comparison_count)`, counting the final failed while test. **[4]**

(b) Test coprime, non-coprime, equal and one-valued inputs. **[2]**

(c) For `a=144`, scan 1<=b<a and report the b with largest count for each method. **[2]**

(d) Explain why the worst repeated-addition count is O(a), while Euclid is O(log a). **[2]**

Code — cell 8

# YOUR CODE HERE
raise NotImplementedError()