I have been advised to raise this improvement suggestion on the developers' mailing list. It is about the trial division algorithm in the method SmallPrimes.boundedTrialDivision(int, int, List<Integer>) in the primes module. Currently, this algorithm skips multiples of 2 and 3 as trial candidates, which reduces the number of integers to be tried to 1/3 of all integers. The choice of these two prime numbers as the only ones whose multiples should be skipped seems arbitrary and is probably rooted in the fact that the way the code currently achieves this is based on code duplication (by hard-coding the alternation of the trial candidate's increment between 2 and 4), and choosing any other prime number, or more prime numbers, would increase the extent of the code duplication to insufferable dimensions.
However, when altering the code's mechanism not to rely on code duplication, using more primes than just 2 and 3 is conceivable. For example, when skipping multiples of 2, 3, 5, 7 and 11, the number of integers to be tried can be reduced to 16/77 of all integers, at the cost of storing 480 pre-computed integers in an array. Considering that the class SmallPrimes already contains an array with the first 512 prime numbers, this does not seem like very much. Some more details about this suggestion are explained here: https://issues.apache.org/jira/browse/NUMBERS-104 --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
