BigPrimes

Github Classroom

You can clone the starter files for this lab at this GitHub Classroom link. Be sure to open the assignment in VSCode and setup up your virtual environment following these instructions.

Modulus

The modulo (%) operation computes the remainder after division. We can implement this operation via a reduction to integer division.

Task: In modulus.py, there is a class Modulus. Each instance has a value which is an integer x. Implement the method reverse_div(y), which is supposed to return the (truncated) quotient of y divided by x. For now, just use Python’s built in truncated division operator //. Later we will use a more sophisticated method.

Task: Implement the __rmod__ method of Modulus. This method is supposed to compute y mod x, also written y % x. However, you are not supposed to use Python’s % operator here. Instead, implement this method using the reverse_div(y) method, based on the Quotient-Remainder Theorem, which states that y = quotient * x + remainder.

Self-Checkpoint: To use an instance m of Modulus, you can evaluate the expression y % m, and the __rmod__ method you wrote will be invoked. Check to see if this works correctly.

Primality

Task: You are to write the body of mod_exp in primality.py to implement modular exponentiation. Your algorithm should resemble the algorithm presented in the first lecture. Recall that this algorithm used squaring to achieve good efficiency. The difference is that this procedure takes a third argument, a Modulus. In order to keep the numbers from getting big, your modular exponentiation algorithm should, after each multiplication, reduce the result with respect to the Modulus.

Now, we can use an implementation of Fermat’s primality test to determine whether a number is prime!

Task: In primality.py, implement is_prime(n) using modular exponentiation, according to the following pseudocode:

First, set M = Modulus(n)

1) Choose a random integer b between 1 and n-1.

2) Check if mod_exp(b, n-1, M) is equal to 1.

3) If not, the number is composite: return false. If so, try again.

4) Repeat 20 or so times

5) If number is not found to be composite, return true.

Self-Checkpoint: Run test_is_prime() in test_primality.py to check your implementation of is_prime.

Now that we’re able to test whether a number is prime, we can use that function to find primes!

Task: Implement search_for_prime(n) to find primes in the range $(2^n, 2^{n+1}]$ using the following pseudocode:

1) Let $2^n$ and $2^{n+1}$ be your lower and upper bounds

2) Randomly sample an integer i in the range [lower, upper). (You can use Python’s randint.)

3) Check is_prime(i). If true, return i.

4) Repeat until a prime is found.

TA Checkpoint: Find the largest n for which search_for_prime(n) responds in a reasonable time, and show your TA the output.

Fast Multiplication

In class, we saw two algorithms for multiplying integers. In this section, we’ll ask you to implement these algorithms and compare the real-world performance of them on varying input sizes.

Task: In fast_multiply.py, implement the function multiply. By way of review, here is the idea of the algorithm

Let $x$ , $y$ be expressed in binary as $x_{m-1} \ldots x_0$ and $y_{n-1} \ldots y_0$ .

Write $x$ as $\underbrace{x_{m-1} x_{m-2} \cdots x_k}_{x_{upper}}\;\underbrace{x_{k - 1} \ldots x_0}_{x_{lower}}$

Write $y$ as $\underbrace{y_{n-1} y_{n-2}\ldots y_k}_{y_{upper}}\;\underbrace{y_{k - 1} \ldots y_0}_{y_{lower}}$

let $a = x_{upper} \cdot y_{upper}$

let $b = x_{lower} \cdot y_{upper}$

let $c = x_{upper} \cdot y_{lower}$

let $d = x_{lower} \cdot y_{lower}$

Then $x\cdot y = a \cdot 2^{k+k} + (b + c) \cdot 2^k + d$ .

Self-Checkpoint: Run the tests in test_fast_multiply.py to check your implementation of multiply!

Task: In fast_multiply.py, implement the function fast_multiply_karatsuba. The structure of the algorithm is very similar to that of multiply but use an idea discussed in class to use only three recursive calls instead of four.

Self-Checkpoint: Run the tests in test_fast_multiply.py to check your implementation of fast_multiply_karatsuba!

TA-Checkpoint: Run fast_multiply.py to plot the runtime of your two algorithms against each other. Does this align with what you already know about these algorithms from class? Also, compare the runtimes to the time required by Python’s built-in * operator.

Representing BigFloats

Computing the modulo operation can be quite expensive. We’ll focus on implementing a couple methods to efficiently compute the modulus of large integers.

Task: The file big_float.py contains a mostly-completed implementation of BigFloat, our exact but floating-point representation of numbers. Implement the float function. This should return the Python floating-point representation of the given BigFloat.

You’ll see many “magic” methods, methods whose names are surrounded by __. Magic methods are also called “dunders”. More information about magic methods can be found in the Python FAQ. The basic idea is that these methods allow you to use traditional operators such as +, -, *, >>, and << on instances of the class.

Task: In big_float.py, implement the truncate function.

Self-Checkpoint: Run the tests in test_big_float.py to check your implementation of truncate!

Reciprocal

Task: Using BigFloat, in rough_base_case_recip.py write base_case_recip(x), which gives a very rough underestimate of 1/x.

Estimate a = base_case_recip(x) should satisfy $1 - a \cdot x \leq 0.5$ .

Final Checkpoint: Show the TA your implementation of base_case_recip. Congrats—you’ve finished lab two!

If you have any feedback, you can fill out this anonymous Google Form!