Loading ...
Sorry, an error occurred while loading the content.
 

Re: [PrimeNumbers] Eratosthenes

Expand Messages
  • Phil Carmody
    ... Lest I get mistaken for someone who actually knows stuff, I have to contradict you. That I did not know. (I knew the condition for uselessness, I just
    Message 1 of 4 , May 22, 2006
      --- Paul Leyland <paul@...> wrote:
      > > For example, if you only care about 2-almost primes then you'd use
      > > 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.

      Lest I get mistaken for someone who actually knows stuff, I have to contradict
      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!).

      Phil

      () 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
      http://mail.yahoo.com
    Your message has been successfully submitted and would be delivered to recipients shortly.