Journal InTime

_ 素数の計算

Haskellで素数を求めるコードは、以下のように簡潔に書ける。

sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x /= 0]
primes = sieve [2..]

main = print $ primes !! 1000

これが遅いのは有名だけど、実はSICPにも同じような例がある。

(define (integers-starting-from n)
  (cons-stream n (integers-starting-from (+ n 1))))

(define (divisible? x y) (= (remainder x y) 0))

(define (sieve stream)
  (cons-stream
   (stream-car stream)
   (sieve (stream-filter
           (lambda (x)
             (not (divisible? x (stream-car stream))))
           (stream-cdr stream)))))

(define primes (sieve (integers-starting-from 2)))

(display (stream-ref primes 1000))

MIT Schemeだとこのまま動いたが、Gaucheだと(use util.stream)した上でcons-streamはstream-consにする必要があるようだ。

比べてみるとHaskellの方が断然速い。

$ time ./prime
7927
./prime  0.11s user 0.00s system 95% cpu 0.122 total
$ time mit-scheme --batch-mode < prime.scm
7927mit-scheme --batch-mode < prime.scm  2.39s user 0.18s system 98% cpu 2.602 total
$ time gosh prime2.scm
7927gosh prime2.scm  14.84s user 0.06s system 99% cpu 14.979 total

別にSchemeが遅いと言いたいわけではなくて、このアルゴリズムは効率悪いけど、Haskell自体はやっぱり速いんだな、と。

しかし、Project EulerとかやるとやっぱりHaskellでも遅いのでprimesパッケージを使うのであった(ずるい)。 primesパッケージのprimesとかprimeFactorsはすごく速いけど、コード読んでもさっぱりわからないのでだれか解説してください。