Week 2: Homework Solutions

3.

a = int(input("a: "))
b = int(input("b: "))
while a != b:
    a, b = min(a, b), max(a, b) - min(a, b)
print("The greatest common divisor is", a)

An example of a faster algorithm is Euclid's algorithm by division:

a = int(input("a: "))
b = int(input("b: "))
# Swap a and b if necessary, so that a <= b
a, b = min(a, b), max(a, b)
while b % a != 0:
    a, b = b % a, a
print("The greatest common divisor is", a)

This implementation uses of the Python modulus operator (%). For large values of a and b Euclid's algorithm by division tends to be faster than our subtraction algorithm, since it performs fewer operations.

4.

Here are two solutions. The first is a straight translation of the formulas on the Wikipedia page.

# To calculate the Gauss-Legendre approximation to pi. (1)
a, b, t, p = 1, 2**(-0.5), 1/4, 1
count = 1
# We will just run 10 iterations to see what we get
while count <= 10:
    a_new = (a + b)/2
    b_new = (a*b)**(0.5)
    t_new = t - p*(a - a_new)**2
    p_new = 2*p
    # now update the values to the new ones
    a, b, t, p = a_new, b_new, t_new, p_new
    pi_estimate = (a + b)**2 / (4*t)
    print("Estimate", count, "is", pi_estimate)
    count = count + 1

If you look carefully you will see that the only new variable on the right handside of the definitions is a_new in the definition of t_new, so substituting the definition of a_new in to t_new gives us a set of definitions that we can do with a single swoop in a parallel assignment.

# To calculate the Gauss-Legendre approximation to pi. (2)
a, b, t, p = 1, 2**(-0.5), 1/4, 1
count = 1
# We will just run 10 iterations to see what we get
while count <= 10:
    a, b, t, p = (a + b)/2, (a*b)**(0.5), t - p*((a - b)/2)**2, 2*p
    pi_estimate = (a + b)**2 / (4*t)
    print("Estimate", count, "is", pi_estimate)
    count = count + 1

When you run these programs you see that the accuracy of the approximation quickly exceeds the accuracy to which Python floats are presented. There are variable types in Python which are better suited than floats for higher precision work.