ハスケルを用いたプライムテストのパフォーマンス

Question

私は素数をテストする2つの方法があります。そのうちの1つはisPrimeと呼ばれ、もう1つはisBigPrimeです。私がもともと望んでいたのは、私がすでに計算した "小さい"素数で "大きな"素数をテストして、テストがより速くなるようにすることです。私は1700〜3E6とSQRT（3E6）までの素数を持っていると思った私は、これら2つのアルゴリズムを比較するために、それらの合計を取ったので、私は、上限として1700を選択した

intSqrt :: Integer -> Integer 
intSqrt n = round $ sqrt $ fromIntegral n 

isPrime' :: Integer->Integer -> Bool 
isPrime' 1 m = False 
isPrime' n m = do 
    if (m > (intSqrt n)) 
    then True 
    else if (rem n (m+1) == 0) 
     then False 
     else do isPrime' n (m+1) 

isPrime :: Integer -> Bool 
isPrime 2 = True 
isPrime 3 = True 
isPrime n = isPrime' n 1 
isBigPrime' :: Integer ->Int ->Bool 
isBigPrime' n i = 
    if ((smallPrimes !! i) > intSqrt n) 
    then True 
    else if (rem n (smallPrimes !! i) == 0) 
     then False 
     else do isBigPrime' n (i+1) 
smallPrimes = [2,3, List of Primes until 1700] 
--Start at 1 because we only go through uneven numbers 
isBigPrime n = isBigPrime' n 1 
primes m = [2]++[k | k <- [3,5..m], isPrime k] 
bigPrimes m = smallPrimes ++ [k | k <- [1701,1703..m], isBigPrime k] 
main = do 
    print $ (sum $ [Enter Method] 2999999) 

：ここに私の実装があります。私はbigPrimesが速くなると思ったのですが、最初はそれほど計算が少ないので、とはあまりにも大きすぎませんが、とにかく頭のスタートがあります。しかし、驚いたことにbigPrimesはprimesよりも遅かった。ここでの結果は以下のとおりです。primes

Performance counter stats for './p10': 


     16768,627686  task-clock (msec)   # 1,000 CPUs utilized   
       58  context-switches   # 0,003 K/sec     
       1  cpu-migrations   # 0,000 K/sec     
      6.496  page-faults    # 0,387 K/sec     
    53.416.641.157  cycles     # 3,186 GHz      
    <not supported>  stalled-cycles-frontend 
    <not supported>  stalled-cycles-backend 
    160.411.056.099  instructions    # 3,00 insns per cycle   
    34.512.352.987  branches     # 2058,150 M/sec     
     10.673.742  branch-misses    # 0,03% of all branches   

     16,773316435 seconds time elapsed 

については

、それはケースだろう、なぜbigPrimes

Performance counter stats for './p10': 

     19111,667046  task-clock (msec)   # 0,999 CPUs utilized   
       259  context-switches   # 0,014 K/sec     
       3  cpu-migrations   # 0,000 K/sec     
      6.278  page-faults    # 0,328 K/sec     
    61.027.453.425  cycles     # 3,193 GHz      
    <not supported>  stalled-cycles-frontend 
    <not supported>  stalled-cycles-backend 
    198.207.905.034  instructions    # 3,25 insns per cycle   
    34.632.138.061  branches     # 1812,094 M/sec     
     106.102.114  branch-misses    # 0,31% of all branches   

     19,126843560 seconds time elapsed 

のために私は思っていました。私はprimes!!nを使用してbigPrimesをいくらか遅くすることを疑っていますが、私は完全にはわかりません。

Answer 1

他の言語からもたらされる共通の反パターンは、インデックスを反復し、(!!)を使用してリストにインデックスを付けることです。 Haskellでは、リスト自体を単純に反復するのは慣用的です。だから：

isBigPrime' :: Integer -> [Integer] ->Bool 
isBigPrime' n [] = True 
isBigPrime' n (p:ps) = p > intSqrt n || (rem n p /= 0 && isBigPrime' n ps) 

isBigPrime n = isBigPrime' n (drop 1 smallPrimes) 

私のマシンでは、primesは25.3秒かかる。 bigPrimesには20.9秒かかります。私のbigPrimesは3.2秒かかります。他にもいくつかの果物があります（例えば、p > intSqrt nの代わりにp*p > nを使用しています）が、これははるかに重要なものです。