Почему моя реализация сита Аткина медленнее, чем Эратосфена?

Question

Я делаю задачи из Project Euler в Ruby и реализовал сито Аткина для поиска простых чисел, но оно работает медленнее, чем сито Эратосфена.В чем проблема?

def atkin_sieve(n)
  primes = [2,3,5]

  sieve = Array.new(n+1, false)

  y_upper = n-4 > 0 ? Math.sqrt(n-4).truncate : 1
  for x in (1..Math.sqrt(n/4).truncate) 
    for y in (1..y_upper)
      k = 4*x**2 + y**2
      sieve[k] = !sieve[k] if k%12 == 1 or k%12 == 5
    end
  end

  y_upper = n-3 > 0 ? Math.sqrt(n-3).truncate : 1
  for x in (1..Math.sqrt(n/3).truncate)
    for y in (1..y_upper)
      k = 3*x**2 + y**2
      sieve[k] = !sieve[k] if k%12 == 7
    end
  end

  for x in (1..Math.sqrt(n).truncate)
    for y in (1..x)
      k = 3*x**2 - y**2
      if k < n and k%12 == 11
    sieve[k] = !sieve[k]
      end
    end
  end

  for j in (5...n)
    if sieve[j]
      prime = true
      for i in (0...primes.length)
        if j % (primes[i]**2) == 0
          prime = false
          break
        end
      end
      primes << j if prime
    end
  end
  primes
end

def erato_sieve(n)
  primes = []
  for i in (2..n)
    if primes.all?{|x| i % x != 0}
      primes << i
    end
  end
  primes
end

Answer 1

Очень помогло бы, если бы вы на самом деле правильно применили Сито Эратосфена.

Критическая особенность этого сита заключается в том, что вы выполняете только одну операцию за раз, когда простое число делит число. В отличие от этого вы делаете работу для каждого простого числа меньше, чем число. Разница невелика, но последствия для производительности огромны.

Вот фактическое сито, которое вы не смогли реализовать:

def eratosthenes_primes(n)
    primes = []
    could_be_prime = (0..n).map{|i| true}
    could_be_prime[0] = false
    could_be_prime[1] = false
    i = 0
    while i*i <= n
        if could_be_prime[i]
            j = i*i
            while j <= n
                could_be_prime[j] = false
                j += i
            end
        end
        i += 1
    end
    return (2..n).find_all{|i| could_be_prime[i]}
end

Сравните это с вашим кодом, чтобы найти все простые числа до 50 000. Также обратите внимание, что это можно легко ускорить в 2 раза, используя специальную логику для четных чисел. Благодаря этой настройке этот алгоритм должен быть достаточно быстрым для каждой задачи Project Euler, требующей вычисления большого числа простых чисел.

Answer 2

Как говорит Википедия : «Современное сито Аткина более сложное, но более быстрое при правильной оптимизации » (мой акцент).

Первое очевидное место, чтобы сэкономить некоторое время в первом наборе циклов, это прекратить итерации по y, когда 4*x**2 + y**2 больше n. Например, если n равно 1 000 000, а x равно 450, то вам следует прекратить итерацию, когда y больше 435 (вместо продолжения до 999, как вы делаете в данный момент). Таким образом, вы можете переписать первый цикл как:

for x in (1..Math.sqrt(n/4).truncate)
    X = 4 * x ** 2
    for y in (1..Math.sqrt(n - X).truncate)
        k = X + y ** 2
        sieve[k] = !sieve[k] if k%12 == 1 or k%12 == 5
    end
end

(Это также позволяет избежать повторного вычисления 4*x**2 каждый раз вокруг цикла, хотя это, вероятно, очень небольшое улучшение, если таковое имеется.)

Подобные замечания применимы, конечно, к другим циклам над y.

---

Второе место, где вы можете ускорить процесс, - стратегия зацикливания на y. Вы перебираете все значения y в диапазоне, а затем проверяете, какие из них приводят к значениям k с правильными остатками по модулю 12. Вместо этого вы можете просто зациклить правильные значения только y, и вообще не проверяйте остатки.

Если 4*x**2 равно 4 по модулю 12, то y**2 должно быть 1 или 9 по модулю 12, и поэтому y должно быть 1, 3, 5, 7 или 11 по модулю 12. Если 4*x**2 равно 8 по модулю 12, тогда y**2 должно быть 5 или 9 по модулю 12, поэтому y должно быть 3 или 9 по модулю 12. И, наконец, если 4*x**2 равно 0 по модулю 12, то y**2 должно быть 1 или 5 по модулю 12 поэтому y должно быть 1, 5, 7, 9 или 11 по модулю 12.

---

Я также отмечаю, что ваше сито с Эратосфеном делает бесполезную работу, проверяя делимость на все простые числа ниже i. Вы можете остановить итерацию после проверки делимости на все простые числа, меньшие или равные квадратному корню из i.

Answer 3

@ Гарет упоминает некоторые избыточные вычисления, касающиеся 4x ^ 2 + y ^ 2.И здесь, и в других местах, где у вас есть вычисления внутри цикла, вы можете использовать вычисления, которые вы уже выполнили, и сократить их до простого сложения.

Вместо X=4 * x ** 2 вы можете полагаться на фактчто X уже имеет значение 4 * (x-1) ** 2.Поскольку 4x ^ 2 = 4 (x-1) ^ 2 + 4 (2x - 1), все, что вам нужно сделать, это добавить 8 * x - 4 к X.Вы можете использовать этот же трюк для k и других мест, где вы повторяли вычисления (например, 3x ^ 2 + y ^ 2).