Navigation
Topics Register • News • History • How to • Sequences statistics • Template prototypes

Frequently suggested improvements

From Prime-Wiki
Jump to: navigation, search

Why not skip the modular reduction in the LL test and reuse residues?

The residues would become huge if it weren't for the modular reduction. Since we square at each step of the Lucas-Lehmer test, the number of digits approximately doubles each time. So after only 50 iterations, the residue would be about 640,000,000,000,000 decimal digits long - far too large to store in any personal computer. The modular reduction is what allows us to run these tests with millions of iterations at all.

Why not use several processors in parallel for one LL test?

While technically possible, we already have a way for parallelising GIMPS to several processors - running a separate test on each! For the most part we are interested in completing the largest possible number of tests with the available CPU time, and running one test per core is the most efficient way of doing it. In rare cases, we want to complete one test in the least possible amount of elapsed time (when double checking a supposed Mersenne prime). In this case SMP variations of the LL test can be used and are used - see Glucas.

Update: Since version 25, Prime95 has supported running one LL test on several processors or cores. Although the total throughput is less than when running a separate test on each core, the shorter elapsed time needed to complete a single test might appeal to many users, especially those working on very large exponents. There is also now a GPU based LL program that takes advantange of the massive parallel computing power of GPUs - see Maclucas.cuda.

Why not start computing at both ends of the LL sequence and meet in the middle?

The LL iteration computes the square of a residue, then subtracts 2. If we assumed that the number we test is prime and so the LL test must leave a 0 residue, we could start with that 0 residue and repeatedly add 2 and take a square root. Unfortunately, taking a modular square root is computationally very expensive - about as expensive as a complete forward LL test. What's worse, a square root produces two results, which are negatives of one another - we could not guess which is the correct one to use to continue the next step of the reverse computation.