私のAtkin篩の実装がEratosthenesよりも遅いのはなぜですか？

Question

私はRubyでProject Eulerの問題を抱えており、Atkinの篩を素数検索に実装していますが、Eratosthenesの篩よりも遅く実行されています。何が問題ですか？ Wikipedia saysとして

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

、（私の強調）「アトキンの近代的なふるいは、より複雑ですが、適切にを最適化する際速く」。

ループの最初のセットに時間を節約するための最初の明白な場所は、4*x**2 + y**2がnより大きい場合、yを反復して停止することです。たとえば、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以上の他のループにも適用されます。

---

高速化できる第2の場所は、yをループする戦略です。あなたは範囲内のyのすべての値をループして、あなただけの、そして完全に残りのテストyの正しい値を超えるだけのループを避けることができ、正しい余りが代わりに12を法とkの値につながるものかを確認し。

4*x**2 4モジュロ12である場合、4*x**2 8モジュロ12である場合、y**2がある必要があり、その後y**2は1又は9モジュロ12でなければならず、そうyは1、3、5、7、または11モジュロ12でなければなりません5または9が12を法とするので、yは3または9を法とする12でなければならない。4*x**2が12を法とする0の場合、y**2は1または5を法12にする必要があるため、yは1,5,7,9または11モジュロ12

---

私もエラトステネスのふるいあなたは以下の全ての素数で割り切れるをテストすることによって、無駄な仕事をしていることに注意してください。の平方根以下のすべての素数で割り切れをテストしたら、反復を停止することができます。

Answer 2

@Garethには、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のような計算が繰り返される場所もあります。

Answer 3

最初にエラトステネス篩を適切に実装していれば、多くの助けになります。

このふるいの重要な特徴は、プライムが1つの数値を分ける時間ごとに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問題に対して、このアルゴリズムは十分速くなければなりません。