User talk:Petelomax: Difference between revisions
Phix: comments on the statements made for the Extensible Prime Generator....
m (→Boids) |
GordonBGood (talk | contribs) (Phix: comments on the statements made for the Extensible Prime Generator....) |
||
Line 20:
:: Thanks, it looks great. :-) [[User:Fwend|Fwend]] ([[User talk:Fwend|talk]]) 20:28, 7 June 2017 (UTC)
==Use of Factorization Wheels in Sieves==
As per the comment you made in your contribution to [[Extensible_prime_generator#Phix]], you said "I investigated the use of so-called "wheels", beguiled by the claim that "a 2-3-5-7 wheel saves 77%", until I realised the breakdown was 2: 50%, 3: 16%, 5: 7%, 7: 4% - it is unthinkable not to exclude even numbers, the added complexity (and subscripting) of a 30- or 210- element wheel does not seem worthwhile."
With respect, you are missing something: While it is true that for extremely large ranges of prime approaching infinity, the majority of the gain is derived from using only the low number wheel factors, the benefit is much greater than expected for commonly used ranges. As per [https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Computational_analysis this link to the Wikipedia Sieve of Eratosthenes formula and tables], there is a reduction of a factor of about 2.67 using odds-only but a further factor of about 4.16 using the extra 3-5-7 wheel for a sieving range of a hundred thousand as is the requirement of the task, and a factor of about 2.5 for odds-only but a further factor of an extra about 3.26 for a range of about a billion as you calculated (actually you calculated to about two billion). In addition, it is fairly easy to implement pre-culling of the array(s) for the even larger wheel of 11-13-17-19 for a further smaller gain.
You further mention added complexity in subscripting, which isn't necessary; While it is true that there is added complexity in a page segmented version such as this in computation of page start addresses per prime, the actual subscripting for the culling operations doesn't need to be any more complex than for the odds-only case, which could be considered to be just one of the modulo planes out of the total of 48 used for 2-3-5-7 wheel factorization.
BTW, about 27.5 seconds to calculate the 100 millionth prime for odds-only isn't particularly fast: even using odds-only Julia can calculate this range about ten times faster using an equivalent page segmented technique, although I don't know if the techniques of the bit operations required to do bit packing by bytes to make maximal use of the CPU L1 cache are available in Phix; this is without the more complex techniques of implementing modulo bit planes for efficient wheel factorizations as discussed above for a further reduction of about four times, then multi-processing can be added... --[[User:GordonBGood|GordonBGood]] ([[User talk:GordonBGood|talk]]) 05:25, 13 November 2018 (UTC)
| |||