Advanced Flow Control Worksheet

The Story So Far

You are a mathematician, learning to program mathematics. You mainly have access to numbers right now - your instructor hasn't covered matrices, general groups, rings or functions - so numbers are what you will practice on.

Create a file NumberTheoryPractice.py. Inside, write a docstring for a function factorial(n), which returns the factorial as an integer for a nonnegative integer n. Include multiple examples, including at 0.

We are going to practice recursion:

Write a function, factorial(n), implementing your docstring using recursion. Use an unlimited cache to store the values.

Now let's try something a little more challenging;

Write a docstring for a function, gcd(a,b), with examples including positive, negative, and zero values for a and b.

Next you will implement this function.

Write a function, gcd(a,b), which computes the gcd using recursion. Remember that gcd(a,b) = gcd(a%b,b) = gcd(a,b%a).

While this is likely to terminate fairly quickly for any sensible pair a,b - far apart or close together - practice rewriting it as a while loop.

Rewrite gcd(a,b) using loops instead of recursion.

Often, we want more than just the gcd - we want the coefficients. Fortunately, we can adapt this algorithm; write an implementation egcd conforming to the following docstring:

""" Computes the Extended GCD $g$ of $a,b$. Returns $g,x,y$ with $g=ax+by$.

Parameters
----------
a : int
b : int

Returns
-------
g : int
    The GCD of $a,b$ - the smallest positive integer which can be
    expresssed as a linear combination of $a$ and $b$.
x : int
y : int
    Coefficients such that a*x+b*y = g. Selected such that x is the
    smallest possible nonnegative value.


Examples
--------
>>> egcd(0,5)
(5, 0, 1)

>>> egcd(1,2)
(1, 1, 0)

>>> egcd(4,6)
(2, 2, -1)
"""

Now that we have an extended GCD, we can:

Write an invmod(a,m) function which computes an integer b in the range [0,m) such that a*b = 1 mod m (in python speak, a*b%m == 1). This function should return a new type of Error named NonInvertibleError - a subclass of ValueError.

Now that we have this, we can:

Write a function find_invertible_mod(candidates,m) which takes in a list (or other iterable) and returns the inverse of the first element in that list mod m. Use the invmod function. For example, find_invertible_mod(range(2,10),30) should return 13, the inverse of 7.

Make sure your functions are passing all tests, that no extra code is executed. Save and upload the NumberTheoryPractice.py to Brightspace.