Есть ли быстрый, функциональный первичный генератор?

Question

Предположим, у меня есть натуральный номер n, и я хочу список (или любой другой) всех простых чисел до n.

Классический алгоритм простого сита работает в O(n log n) времени и O(n) пространство - это нормально для более императивных языков, но требует внесения изменений в списки и случайный доступ на месте.

Существует функциональная версия с приоритетными очередями, которая довольно гладкая - вы можете проверить ее here. Это лучшее пространство сложности около O(n/log(n)) (асимптотически лучше, но спорное в практических масштабах). К сожалению, анализ времени неприятный, но это почти O(n^2) (на самом деле, я думаю, это примерно O(n log(n) Li(n)), но log(n) Li(n) составляет примерно n).

Асимптотически говоря, было бы лучше просто проверить правильность каждого числа при его создании, используя последовательное пробное деление, поскольку это займет всего O(1) места и O(n^{3/2}) времени. Есть ли способ лучше?

Редактировать: Оказалось, что мои вычисления были просто неправильными. Алгоритм в статье O(n (log n) (log log n)), который статьи объясняют и доказывают (и см. Ответ ниже), а не сложный беспорядок, который я поставил выше. Мне все равно понравится чистый алгоритм bona-fide O(n log log n), если он есть.

Answer 1

Вот реализация Хаскелла алгоритма Мелиссы О'Нейл (из связанной статьи). В отличие от реализации, с которой связан Gassa, я использовал минимальную ленту, так что анализ производительности ясен - O (n log n log log n), то есть, линейный в n log log n, число пишет, сделанное императивом Сито Эратосфена.

Реализация кучи - это просто дерево турниров. Логика балансировки находится в push; путем замены детей каждый раз, мы гарантируем, что для каждой ветки левое поддерево имеет тот же размер или один больше по сравнению с правым поддеревом, что обеспечивает глубину 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 n p) = 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 p h@(Leaf _ _) = branch (leaf p) h 
push p (Branch _ h1 h2) = branch (push p h2) h1 

primes :: [Nat] 
primes 
    = let helper n h 
      = case compare n (top h) of 
       LT -> n : helper (n + 2) (push n h) 
       EQ -> helper (n + 2) (pop h) 
       GT -> helper n (pop h) 
     in 2 : 3 : helper 5 (leaf 3) 

Answer 2

Здесь он, если (Haskell's) чистые массивы считаются чистыми (они должны, ИМО). Сложность, очевидно, O (п журнал (журнал N)), при условии, accumArray действительно тратит O (1) времени для каждого индекса это дают, как это должно:

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)] 

Рассчитывает простые числа с помощью сегменты между последовательными квадратами простых чисел (бит map (^2)), генерируя композиты путем перечисления кратных растущих префиксов простых чисел (бит inits), как и любое правильное сито Эратосфена, путем повторных добавлений.

Таким образом, простые числа {2,3} используют сито сегмент из к ; {2,3,5} от до ; и так далее. See also.

Кроме того, Python generator-based sieve может считаться функциональным. Python's dict s чрезвычайно эффективны, empirically, хотя я не уверен в точной стоимости схемы многократного избыточного производства, используемой там, чтобы избежать дублирования композитов.

---

обновление:testing it действительно производит благоприятные результаты, как и ожидалось:

{-  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 
-} 

с empirical orders of growth вычисленная для получения п простых чисел, где О (п войти войти п) обычно наблюдается как n ^{1.05 ... 1.10} и O (n log n log log n) как n ^{1,20 ... 1,25}.

"nested-feed" вариант реализует postponement технику (как также видно в приведенном выше связаны Python answer), что обеспечивает квадратичную уменьшение размера кучи, которые по-видимому, имеет заметное влияние на эмпирической сложности, даже если не совсем достижения еще лучших результатов для массива на основе этого ответа, который is able to produce 10 миллионов простых чисел менее чем за 10 секунд на ideone.com (общий темп роста всего n ^1.09 в тестируемом диапазоне).

("original heap" - это, конечно, код от the other answer).

Answer 3

Я получил первую генераторную функцию (генерирует все простые порядки) некоторое время назад. Создал 6-страничный документ для этого. Я думаю, что это первая основная производящая функция в истории на самом деле (по крайней мере, я не мог найти других примеров).

Здесь:

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

Не знаете, как быстро он может быть вычислен. Он возвращает 0 для всех простых чисел (или, может быть, 1, не помню). Гамма-функция по существу факториала, поэтому она может быть быстрой на ранней стадии. Повышение отрицательного 1 до дробного показателя является целым другим зверем, хотя, я полагаю, он использует интегралы в base_e, возможно, или некоторые тригонометрические функции; не помню.

Я не знаю LaTeX, поэтому, если кто-то хочет отредактировать мое сообщение и включить версию LaTeX, которая была бы потрясающей!