[jira] [Commented] (NUMBERS-104) Speed up trial division

["Gilles (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/NUMBERS-104?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16853644#comment-16853644 ] 

Gilles commented on NUMBERS-104:
--------------------------------

{quote}here or on the developer mailing list
{quote}
It would be good to post to the"dev" ML too.

Unless I'm mistaken, it seems that the coverage of the {{boundedTrialDivision}} is fairly low compared to the rest of the {{SmallPrimes}} class.
 This should be improved by adding unit tests.

You can check the coverage (and several other reports) by running:
{noformat}
mvn clean site site:stage
{noformat}
and then look at the "Jacoco" report in the generated web site pages (in directory _target/staging_).

Thanks.

> 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
>          Time Spent: 20m
>  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)