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

Re: Sieve superior to Eratosthenes

Expand Messages
  • WarrenS
    ... --no. However, prodded by you, I just looked at The pseudosquares prime sieve by Jonathan P. Sorensen 2006 and some other stuff he cites. The particular
    Message 1 of 4 , Mar 7, 2013
      > Please forgive my curtness, but have you read all the material by, for example, Sorenson?
      > --Phil Carmody

      --no. However, prodded by you, I just looked at
      "The pseudosquares prime sieve" by Jonathan P. Sorensen 2006 and some other stuff
      he cites.

      The particular algorithm advanced by JPS in this paper looks like a clearly bad idea.
      His review of other work, contains these claims:

      JPS CLAIM 1. the fastest known sieves take O(N/loglogN) time.
      This is even faster than mine, which in turn is faster than Eratosthenes.
      To back this up he cites: P.Pritchard CACM 24,1 (1981) 18-23 & 772
      and B.Dunten, J.Jones, JP Sorensen: Info Proc Lett 59 (1996) 79-84.
      I have not seen Pritchard but did see D+J+S 1996 and the latter is completely useless
      because it requires huge memory.

      JPS CLAIM 2. Memory in some (other) sieves can be reduced to O(N^(1/3)) or even O(N^(1/4)), perhaps with aid of conjectures. I'm doing better than that, I can reduce to O(N^(1/K)) for any fixed integer K.

      The idea behind my sieve is extremely simple. Simply sieve enough to get a set of primes
      and nonprimes that is small (no more than a constant times the primes alone) and then test these using the $640 primality test. (I also use a "wheel" idea in 2 ways to save loglogN time factors during the sieving to prevent the time use from being superlinear.)

      "Pritchard's Wheel Sieve" as described here
      and this description is pretty much exactly the same as "step 2" in my algorithm, and takes order N time.
      This contradicts Sorensen's claim that Pritchard achieves O(N/loglogN) time.
      So there must have been another idea too. I can see one way to accomplish sublinear time
      (perhaps the idea Pritchard had?) which is (basically) that you only sieve out multiples M*P of primes P where M is still possibly-prime according to your current partially-sieved table. This would be a pyrrhic victory since you'd need immense memory consumption to do it.

      Is any method known that achieves sublinear time and way-sublinear memory simultaneously? I know of none.

      The best I know is way-sublinear memory and linear time (my method) but I only achieve that by using the $640 primality test which probably ultimately will fail, hence my algorithm actually is presumably wrong. This in practice seems irrelevant since the first failure is way larger than anybody will ever sieve.

      [Incidentally in my algorithm step 2, one could omit the wheel and just use Eratosthenes, thus suffering a loglogN factor time-use expansion in theory, but in practice it might be faster for a long way. There's a lot of games like that one could play to speed up
      programs non-asymptotically.]
    Your message has been successfully submitted and would be delivered to recipients shortly.