BigPrimes II
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.
In this lab, we will improve on the algorithm we implemented last week to search for large prime numbers. In particular, we will implement the efficient approximate-reciprocal algorithm we discussed in lecture, and use this to implement faster div and mod operations in order to speed up our primality tests. Your implementation should be guided by the lecture notes from February 5th.
The algorithm used BigFloat so copy over the file big_float.py from your previous lab.
Approximate Reciprocal
In order to efficiently compute div and mod operations, we need to implement an algorithm to find the approximate reciprocal of a given BigFloat.
Task: First, let’s revise our base-case. In modulus2.py, implement base_case_one_fourth(x) which should compute an initial approximation with error at most one-fourth.
You can use your code from the last lab which computes an approximation with error at most one-half and use one iteration of the improvement step (remember that with each iteration, the error is squared).
Task: In modulus2.py, implement the recip procedure to recursively calculate an approximate reciprocal of a given BigFloat with a precision k.
Follow the pseudocode presented in the lecture notes. The basic idea is (a) recursively compute a slightly worse approximation, (b) refine it, and returnt the result.
However, the procedure adjust_precision(x, r, round_up) is used twice, once to reduce the precision of the input to the recursive call and once to reduce the precision of the refined
result before returning it.
Task: Finish the constructor of the Modulus class, initializing self.reciprocal using your recip algorithm with appropriate precision. What value of k is necessary?
Self-Checkpoint: Run test_recip() in test_modulus.py to check your implementation of recip.
Division
Now we can use our reciprocal algorithm to write an efficient implementation of div, computing (where is the modulus value) by calculating .
Task: Implement Modulus.div using the value self.reciprocal. Remember that the approximation is always an underestimate,
so the code should add self.increment (a very small number which corrects for the error in our approximation) before truncating the resulting BigFloat to an integer.
The design of Modulus intentionally separates out the computation of the approximate reciprocal (which happens in the constructor) and
the computation of div and mod using the already-computed approximate reciprocal. The advantage is that the former is computationally
more expensive than the latter. In the intended application, checking primality, modular exponentiation needs to perform
many mods with the same modulus, and many calls to modular exponentiation take place, again all with the same modulus.
Because computation of the approximate reciprocal is in the constructor, it need not happen again and again; it only happens once per modulus.
Self-Checkpoint: Run test_modulus_div() in test_modulus.py to check your implementation of div.
Modulus
Computing mod is based on div. You already wrote that part in the previous lab so we have provided the solution. You can
run test_modulus_mod() in test_modulus.py to check that __rmod__ is working as expected.
Next, let’s see how our algorithm fares against Python’s built-in mod function. We have provided some code in the __main__ method at the bottom of modulus.py to help you do this.
Task: Test your implementation against Python’s for large numbers by changing the assignment to the BITS variable near the end of modulus2.py and comparing the time each mod implementation takes.
You may not see an improvement until you test on very large inputs (say, a million bits).
If your code fails to beat Python for very large inputs, check your precision values in recip and the Modulus constructor against the lecture notes to make sure you aren’t executing more iterations or retaining more bits than necessary.
(See the end of this document for another hack to improve efficiency.)
TA-Checkpoint: Show a TA a BIT value for which your mod implementation beats Python!
Primality Testing Revisited
Now that we have implemented a more efficient algorithm for performing the mod operation, we can return to Euler’s Primality test and find even larger prime numbers. Copy over your primality.py file from the previous lab and start searching!
Final Checkpoint: Find the largest n for which search_for_prime(n) responds in a reasonable time, and show your TA the output. Congrats—you’ve finished lab three!
Note that the precision of the approximate reciprocal computed by recip(..) ends up being slightly higher than necessary to obtain the correct div answer.
To get a small but noticable speedup for div and therefore mod, you can modify the code in the constructor for Modulus so that adjust_precision(..) is applied to the output of recip(..) before the assignment to self.reciprocal.
Recall that for carrying out div we require that the error be no more than where is the bit-length of the modulus.
Assuming that the error of the return value of recip(..) is much smaller than that,
we need only ensure that the error introduced by the application of adjust_precision(..) is no more than .
Therefore it should suffice to retain bits in adjust_precision.
By the way, as discussed in the lecture notes, the running times for computing the approximate reciprocal and for computing div and mod all
depend on (and are within a constant factor of) the running time for integer multiplication. There is a much faster algorithm for
integer multiplication, but it is too advanced for this course. However, if you feel excited to find even bigger primes and want to
go deeper into algorithms, consider asking your professor to explain the faster algorithm.
You could implement it in Python and see whether it leads to bigger improvements in efficiency.