Minor Description
Currently, the method SmallPrimes.boundedTrialDivision(int, int, List<Integer>) skips multiples of 2 and 3, thereby reducing the amount of integers to be tried to 1/3 of all integers. This can be improved at the cost of extra memory by extending the set of prime factors to be skipped in the trial division, for example, to 2, 3, 5, 7, and 11.
However, instead of code duplication, which is the way the code currently achieves this, a way to implement this could be:
- First, precompute and store all integers between 0 (inclusive) and 2⋅3⋅5⋅7⋅11=2310 (exclusive) that are not divisible by any of those 5 prime numbers (480 numbers in total, according to my experiments).
- Then, when performing the trial division, one only needs to try out numbers of the form 2310⋅k + c, where k is a non-negative integer and c is one of the 480 numbers described in the previous step.
That way, the amount of integers to be tried will be 480/2310 ≈ 20.78%, instead of 1/3 ≈ 33.33%, which is a speedup of about 60.42% compared to the current algorithm. Of course, with more prime factors eliminated, less numbers will have to be tried, but it seems that the returns are quickly diminishing compared to the required memory. For example, when also eliminating the prime factors 13, 17 and 19, the memory required increases to 1658880 integers, whereas the percentage of integers to be tried only drops to about 17.10%.
Since the class SmallPrimes already stores an array containing the first 512 prime numbers, a 480-element int array seems like a reasonable size and a small price to pay for a 60.42% speedup.
I'm just not entirely sure whether this should go here or on the developer mailing list. Since this is actually not a new idea, but just an enhancement of an already existing idea, I'm putting it here, but on the other hand, it requires some re-writing and some new code, so maybe I'm wrong.
Attachments
Issue Links
- links to
