计算素数时Haskell的效率

Question

我有以下一组函数来计算Haskell中小于或等于数n的素数.

算法取一个数字,检查它是否可以被2整除,然后检查它是否可被奇数整除,直到被检查数字的平方根.

-- is a numner, n, prime? 
isPrime :: Int -> Bool
isPrime n = n > 1 &&
              foldr (\d r -> d * d > n || (n `rem` d /= 0 && r))
                True divisors

-- list of divisors for which to test primality
divisors :: [Int]
divisors = 2:[3,5..]

-- pi(n) - the prime counting function, the number of prime numbers <= n
primesNo :: Int -> Int
primesNo 2 = 1
primesNo n
    | isPrime n = 1 + primesNo (n-1)
    | otherwise = 0 + primesNo (n-1)

main = print $ primesNo (2^22)

使用GHC和-O2优化标志,计算n = 2 ^ 22的质数数量需要~3.8秒.以下C代码需要~0.8秒:

#include <stdio.h>
#include <math.h>

/*
    compile with: gcc -std=c11 -lm -O2 c_primes.c -o c_orig
*/

int isPrime(int n) {
    if (n < 2)
        return 0;
    else if (n == 2)
        return 1;
    else if (n % 2 == 0)
        return 0;
    int uL = sqrt(n);
    int i = 3;
    while (i <= uL) {
        if (n % i == 0)
            return 0;
        i+=2;
    }
    return 1;
}

int main() {
    int noPrimes = 0, limit = 4194304;
    for (int n = 0; n <= limit; n++) {
        if (isPrime(n))
            noPrimes++;
    }
    printf("Number of primes in the interval [0,%d]: %d\n", limit, noPrimes);
    return 0;
}

这个算法在Java中占用大约0.9秒,在JavaScript中占用1.8秒(在节点上),所以它只是觉得Haskell版本比我预期的要慢.无论如何,我可以在不改变算法的情况下更有效地在Haskell中编码吗？

---

编辑

@dfeuer提供的以下版本的isPrime将运行时间缩短了一秒,将其降低到2.8秒(从3.8降低).虽然这仍然比JavaScript(节点)慢,这需要大约1.8秒,如此处所示,还有另一种语言速度测试.

isPrime :: Int -> Bool
isPrime n
  | n <= 2 = n == 2
  | otherwise = odd n && go 3
  where
    go factor
      | factor * factor > n = True
      | otherwise = n `rem` factor /= 0 && go (factor+2) 

---

编辑

在上面的isPrime函数,该函数去调用因素*因素为每个除数为单个n.我认为将因子与n的平方根进行比较会更有效,因为这只需要每n计算一次.但是,使用下面的代码,计算时间增加了大约10%,每次评估不等式时(每个因子),是否重新计算n的平方根？

isPrime :: Int -> Bool
isPrime n
  | n <= 2 = n == 2
  | otherwise = odd n && go 3
  where
    go factor
      | factor > upperLim = True
      | otherwise = n `rem` factor /= 0 && go (factor+2)
      where
        upperLim = (floor.sqrt.fromIntegral) n 

Answer 1

我强烈建议您使用不同的算法，例如 Melissa O'Neill 的论文中讨论的埃拉托斯特尼筛法，或者arithmoiMath.NumberTheory.Primes包中使用的版本，该版本还提供了优化的素数计数函数。然而，这可能会让你更好的常数因素：

-- is a number, n, prime? 
isPrime :: Int -> Bool
isPrime n
  | n <= 2 = n == 2
  | otherwise = odd n && -- Put the 2 here instead
        foldr (\d r -> d * d > n || (n `rem` d /= 0 && r))
                True divisors

-- list of divisors for which to test primality
divisors :: [Int]
{-# INLINE divisors #-} -- No guarantee, but it might possibly inline and stay inlined,
               -- so the numbers will be generated on each call instead of
               -- being pulled in (expensively) from RAM.
divisors = [3,5..] -- No more 2:

摆脱的原因2:是，称为“foldr/build fusion”、“short cut deforestation”或“list fusion”的优化可能会使您的除数列表消失，但是，至少在 GHC < 7.10 的情况下.1，这2:将阻止优化。

编辑：这似乎不适合你，所以这里还有其他可以尝试的方法：

isPrime n
  | n <= 2 = n == 2
  | otherwise = odd n && go 3
  where
    go factor
      | factor * factor > n = True
      | otherwise = n `rem` factor /= 0 && go (factor+2)