[
https://issues.apache.org/jira/browse/NUMBERS-104?focusedWorklogId=253478&page=com.atlassian.jira.plugin.system.issuetabpanels:worklog-tabpanel#worklog-253478
]
ASF GitHub Bot logged work on NUMBERS-104:
------------------------------------------
Author: ASF GitHub Bot
Created on: 04/Jun/19 00:58
Start Date: 04/Jun/19 00:58
Worklog Time Spent: 10m
Work Description: coveralls commented on issue #46: NUMBERS-104: Speed up
trial division
URL: https://github.com/apache/commons-numbers/pull/46#issuecomment-497873456
[](https://coveralls.io/builds/23771969)
Coverage increased (+0.2%) to 93.642% when pulling
**7b15fad6c3eeece124f635b7a5c2fd72443f2017 on Schamschi:NUMBERS-104** into
**daac9ac15f6161b32fa4c1374c2d6b563c90af87 on apache:master**.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
Issue Time Tracking
-------------------
Worklog Id: (was: 253478)
Time Spent: 0.5h (was: 20m)
> 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: 0.5h
> 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)
