MATH40006 2026 Practice Paper 2

1.2 Question 1 (20 marks) For c in the rectangle -2 <= Re(c) <= 1, -1.5 <= Im(c) <= 1.5, start z0=0 and iterate z <- z^2+c. The escape time is the first iteration number r for which |z|>=2; use max_iterations when no escape occurs. 1 (a) Build 300-point coordinate arrays, meshgrid arrays, a complex parameter array c, and a zero complex array z0 of matching shape. [4] (b) Create an escape-time array initially -1 and use a Boolean mask to record points already satisfying |z0|>=2 at time 0. [3] (c) Perform one vectorised iteration only on unresolved positions and record newly escaped points at time 1. [3] (d) Write escape_time(c,z0,max_iterations) using Boolean masks. The function must not modify the caller’s z0. [7] (e) Evaluate it for the grid above with max_iterations=80 and display log(times+1) with correct extent and origin. [3] [2]: xr = np.linspace(-2,1,300) yr = np.linspace(-1.5,1.5,300) x,y = np.meshgrid(xr,yr) c = x + 1j*y z0 = np.zeros_like(c, dtype =complex) et = -np.ones(c.shape, dtype =int) et[(et==-1) & (np.abs(z0)>=2)] = 0 mask = et==-1 z0[mask] = z0[mask]**2 + c[mask] et[(et==-1) & (np.abs(z0)>=2)] = 1 def escape_time(c,z0,max_iterations): z = np.array(z0, dtype =complex, copy =True) result = -np.ones(c.shape, dtype =int) for r in range(max_iterations+1): 2 newly = (result==-1) & (np.abs(z)>=2) result[newly] = r unresolved = result==-1 if r == max_iterations or not np.any(unresolved): break z[unresolved] = z[unresolved]**2 + c[unresolved] result[result==-1] = max_iterations return result times = escape_time(c, np .zeros_like(c), 80) plt.figure() plt.imshow(np.log(times+1), origin ='lower', extent =[-2,1,-1.5,1.5],␣ ↪aspect='auto') plt.show() assert times.shape == c.shape and times.min() >= 0 and times.max() <= 80 Marking points / verification. 4 marks for correctly shaped coordinates, c and z0; 3 for initial state/mask; 3 for one selective update; 7 for a complete non-mutating function with correct time labels and stopping; 3 for the final logged image. The reference implementation explicitly copies z0. 3

1.3 Question 2 (20 marks) (a) Experiment with right shift and bit_length. State exact formulae for n >> r and n.bit_length() for positive integers. [3] (b) Write isqrt_linear(n) returning floor(sqrt(n)) by increasing r from 0 until (r+1)**2>n. [4] (c) Test it on a small integer, an eight-digit integer, a square, and numbers one below and one above a square. Verify the defining inequalities. [3] (d) Give a Theta bound for its iteration count. [2] (e) Write isqrt_newton(n) using the discrete Newton update new=(old+n//old)//2. Use bit_length to choose an initial power of 2 strictly above sqrt(n), and return when the update no longer decreases. Handle n=0 and n=1. [6] (f) Test isqrt_newton on a 100-digit integer and compare its result with isqrt_linear on manageable inputs. [2] [3]: for n in [7,8,255,256,257]: print(n, n >>2, n .bit_length()) # n >> r == n // 2**r; bit_length == floor(log2(n))+1 for n>0. def isqrt_linear(n): if n < 0: raise ValueError('n must be non-negative ') r = 0 while (r+1)**2 <= n: r += 1 return r def check(fun,n): r=fun(n) return r*r <= n < (r+1)*(r+1) for n in [37,12345678,144,143,145]: assert check(isqrt_linear,n) # Iteration count is Theta(sqrt(n)). def isqrt_newton(n): if n < 0: raise ValueError('n must be non-negative ') if n < 2: return n old = 1 << ((n.bit_length()+1)//2) new = (old + n//old)//2 while new < old: old, new = new, (new + n//new)//2 return old large = 10**100 + 123456789 4 assert check(isqrt_newton,large) for n in list(range(1000)) + [12345678,10**12+1]: assert isqrt_newton(n) == isqrt_linear(n) print('integer square-root tests passed ') 7 1 3 8 2 4 255 63 8 256 64 9 257 64 9 integer square-root tests passed Marking points / verification. 3 marks for both exact operator relations; 4 for the linear function; 3 for property-based tests; 2 for Theta(sqrt(n)); 6 for correct Newton iteration and bit- length initial bound; 2 for large and cross-implementation tests.

1.4 Question 3 (10 marks) The helpers below convert positive integers to and from binary digit lists. def binary_digits(n): return [int(c) for c in bin(n)[2:]] def from_binary_digits(bits): return int(''.join(map(str,bits)),2) (a) Test that the two functions are inverse for n=1,…,12. [2] (b) Write run_lengths(bits), returning lengths of consecutive equal-bit runs. Example: [1,1,1,0,0,1] -> [3,2,1] . [4] (c) Test it on the example and at least one single-run list. [1] (d) Write run_heads_value(n): retain only the first bit from each run of binary_digits(n), then convert that compressed bit list back to an integer. Test it for n=1,…,20. [3] [4]: def binary_digits(n): return [int(c) for c in bin(n)[2:]] def from_binary_digits(bits): return int(''.join(map(str,bits)),2) for n in range(1,13): assert from_binary_digits(binary_digits(n)) == n def run_lengths(bits): if not bits: return [] out=[]; current =bits[0]; count =1 for b in bits[1:]: if b==current: count += 1 else: out.append(count); current =b; count =1 out.append(count) return out assert run_lengths([1,1,1,0,0,1]) == [3,2,1] assert run_lengths([0,0,0]) == [3] 5 def run_heads_value(n): bits=binary_digits(n) heads=[bits[0]]+[bits[i] for i in range(1,len(bits)) if bits[i]!=bits[i-1]] return from_binary_digits(heads) print([(n,run_heads_value(n)) for n in range(1,21)]) [(1, 1), (2, 2), (3, 1), (4, 2), (5, 5), (6, 2), (7, 1), (8, 2), (9, 5), (10, 10), (11, 5), (12, 2), (13, 5), (14, 2), (15, 1), (16, 2), (17, 5), (18, 10), (19, 5), (20, 10)] Marking points / verification. 2 marks for inverse tests; 4 for correct run counting including the final run and empty input; 1 for the required tests; 3 for retaining run heads and reconversion. 6