Hi. Le mar. 4 juin 2019 à 03:49, Heinrich Bohne <heinrich.bo...@gmx.at> a écrit : > > 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 >
Thanks for your contribution. PR 46 has been merged. Gilles --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
