[
https://issues.apache.org/jira/browse/NUMBERS-104?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Heinrich Bohne resolved NUMBERS-104.
------------------------------------
Resolution: Fixed
Fix Version/s: 1.0
> 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
> Priority: Minor
> Fix For: 1.0
>
> Time Spent: 50m
> Remaining Estimate: 0h
>
> 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)
