Heinrich Bohne created NUMBERS-104:
--------------------------------------
Summary: Speed up trial division
Key: NUMBERS-104
URL: https://issues.apache.org/jira/browse/NUMBERS-104
Project: Commons Numbers
Issue Type: Improvement
Components: primes
Reporter: Heinrich Bohne
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.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
