Re: [PrimeNumbers] Eratosthenes
- --- Paul Leyland <paul@...> wrote:
> > For example, if you only care about 2-almost primes then you'd useLest I get mistaken for someone who actually knows stuff, I have to contradict
> > a 2-bit tally with values 00=0, 01=1, 10=2, 11=more.
> Phil doubtless knows this, but others may not --- a 2-bit saturating
> tally is exactly what is needed when combining relations in the NFS, QS
> and similar algorithms. Any prime (or prime ideal) which occurs zero or
> once is useless; two or more is useful and we don't actually care that
> much whether there are more than two.
you. That I did not know. (I knew the condition for uselessness, I just didn't
know you implemented the shortcut. Makes 100% sense in retrospect, being as it
is a shortcut.)
The situation where I have encountered saturating tallies is another quadratic
sieve - the Atkin sieve. (It's one of my minor peeves that QS is named after an
implementation detail of only part of part of the procedure.) If you can't be
bothered to remove squaresome numbers (pet peeve number 2 - since when was
"squareful" a sensible nomenclature for something which isn't squarefree?)
numbers, explicitly as a post-processing step, then you can instead double your
bitmap size and use a saturating tally instead, and in that case only the '01's
are of interest to you.
I'm thinking of trying to implement the Galway sieve using the tricks from
Primegen, but think I may opt for a saturating tally as the memory footprint
has decreased remarkably, and do away with the square postprocessing stage in
its entirety (as I don't understand the implementation, basically!).
() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed
[stolen with permission from Daniel B. Cristofani]
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around