Is there a fast, functional primary generator?

Question

Suppose I have a natural number n , and I need a list (or any other) of all primes up to n .

The classic simple sieve algorithm works in O(n log n) time and O(n) space - it is great for more imperative languages, but requires a radical change in lists and random access.

There is a functional version with priority queues that is pretty smooth - you can check it here . This is the best space complexity at a temperature near O(n / log(n)) (asymptotic is better, but controversial on a practical scale). Unfortunately, time analysis is unpleasant, but it is very close O(n^2) (in fact, I think it is O(n log(n) Li(n)) , but log(n) Li(n) about n ).

Asymptotically, it would be better to simply check the correctness of each number when creating it, using sequential trial division, since it only takes O(1) space and O(n^{3/2}) . Is there a better way?

Edit: It turns out that my calculations were simply incorrect. The algorithm in the article is O(n (log n) (log log n)) , which the articles explain and prove (and see the answer below), and not the complicated mess I put above. I still like to see a clean bona-fide O(n log log n) algorithm, if any.

Answer 1

Here's the Haskell implementation of Melissa O'Neill's algorithm (from a related article). Unlike the implementation that Gassa is associated with, I used minimal tape, so the performance analysis is clear - O (n log n log log n) , i.e. linearithmic in n log log n, the number of records made by the imperative sieve of Eratosthenes.

Heap implementation is just a tournament tree. The balancing logic is in push ; replacing children each time, we guarantee that for each branch the left subtree is the same size or one larger than the right subtree, which provides a depth of O (log n).

 module Sieve where type Nat = Int data Heap = Leaf !Nat !Nat | Branch !Nat !Heap !Heap deriving Show top :: Heap -> Nat top (Leaf n _) = n top (Branch n _ _) = n leaf :: Nat -> Heap leaf p = Leaf (3 * p) p branch :: Heap -> Heap -> Heap branch h1 h2 = Branch (min (top h1) (top h2)) h1 h2 pop :: Heap -> Heap pop (Leaf np) = Leaf (n + 2 * p) p pop (Branch _ h1 h2) = case compare (top h1) (top h2) of LT -> branch (pop h1) h2 EQ -> branch (pop h1) (pop h2) GT -> branch h1 (pop h2) push :: Nat -> Heap -> Heap push ph@(Leaf _ _) = branch (leaf p) h push p (Branch _ h1 h2) = branch (push p h2) h1 primes :: [Nat] primes = let helper nh = case compare n (top h) of LT -> n : helper (n + 2) (push nh) EQ -> helper (n + 2) (pop h) GT -> helper n (pop h) in 2 : 3 : helper 5 (leaf 3) 

Answer 2

Here, if (Haskell's) pure arrays are considered clean (they should, IMO). The complexity is obviously O (n log (log n)), provided that accumArray really spends O (1) time for each index it accumArray , as it should be:

 import Data.Array.Unboxed import Data.List (tails, inits) ps = 2 : [n | (r:q:_, px) <- (zip . tails . (2:) . map (^2)) ps (inits ps), (n,True) <- assocs ( accumArray (\_ _ -> False) True (r+1,q-1) [(m,()) | p <- px, let s=(r+p)`div`p*p, m <- [s,s+p..q-1]] :: UArray Int Bool )] 

Calculates primes by segments between consecutive squares of primes ( map (^2) bit map (^2) ), generating composites, listing multiple growing prime prefixes (bit inits ) just like any regular Eratosthenes sieve, by repeating the addition.

So, prime numbers {2,3} are used to sift a segment from 10 to 24; {2,3,5} from 26 to 48; and so on. See also .

In addition, the Python syntactic generator solution can be considered functional. Python dict extremely effective, empirically , although I'm not sure about the exact cost of the multiplication scheme used for over-production to avoid duplication of composites.

---

update: testing really gives favorable results, as expected:

 {- original heap tweaked nested-feed array-based (3*p,p) (p*p,2*p) JBwoVL abPSOx 6Uv0cL 2x speed-up another 3x+ speed-up n^ n^ n^ n^ 100K: 0.78s 0.38s 0.13s 0.065s 200K: 2.02s 1.37 0.97s 1.35 0.29s 1.16 0.13s 1.00 400K: 5.05s 1.32 2.40s 1.31 0.70s 1.27 0.29s 1.16 800K: 12.37s 1.29 1M: 2.10s 1.20 0.82s 1.13 2M: 1.71s 1.06 4M: 3.72s 1.12 10M: 9.84s 1.06 overall in the tested range: 1.33 1.21 1.09 -} 

with empirical growth orders calculated to obtain n primes, where O (n log log n) is usually considered as n ^{1.05 ... 1.10} and O (n log n log log n) as n ^{1.20 ... 1.25} .

The nested-feed option implements a deferral method (as also seen in the Python answer above) that provides a quadratic reduction in heap size, which obviously has a noticeable effect on empirical complexity, even if it does not achieve even better results for the array on based on this answer, which is capable of producing 10 million primes in less than 10 seconds on ideone.com (with a total growth rate of only n ^1.09 in the test range).

( "original heap" is of course the code from another answer here).

Answer 3

I got the main producing function (generating all simple orders) some time ago. Created a 6-page document for this. I think this is the first major production function in history actually (at least I could not find other examples).

Here he is:

(-1)^((4*gamma(x)+4)/x)-1

Not sure how fast it can be calculated. It returns 0 for all primes (or maybe 1, I don’t remember). The gamma function is essentially a factorial, so it can be fast at an early stage. Raising a negative 1 to a fractional exponent is a whole different beast, although I suppose it uses the integrals in base_e, perhaps some trigonometric functions; I do not remember.

I don’t know LaTeX, so if someone wants to edit my post and include a version of LaTeX that will be awesome!