Gaucheで素数ストリーム

Scheme Gauche

エラトステネスの篩

(define (divisor? x y)
  (eqv? 0 (remainder x y)))

(define-constant +primes+
  (stream-cons 2 (stream-filter prime? (stream-iota -1 3 2))))

;; (define (prime? n)
;;   (not (stream-any (cut divisor? n <>) (stream-take-while (cute >= (sqrt n) <>) +primes+))))

(define (prime? n)
  (let1 limit (sqrt n)
    (let loop ((srm +primes+))
      (let1 x (stream-car srm)
        (or (< limit x)
            (if (divisor? n x)
                #f
                (loop (stream-cdr srm))))))))

;(time (stream-ref |+primes+| 10000))
; real   0.868
; user   0.840
; sys    0.020

; => 104743

stream-take-while を使った版は 5.132s かかった．
Gaucheでエラトステネスの篩で素数ストリーム(世間一般のやつより速い) - Gemmaの日記 のと比較してみたら，向こうのは 7.792s かかったのでこちらの方が大分速い．
でもこれを Haskell に移植して Haskell 版で比較すると 0.179s と 0.123s で向こうの方が速かった．
ところが，-O つけてコンパイルするとどちらも 0.104s くらいで同じになった…
takeWhile を使うと 0.695s と遅くなっていたのが -O 付きでは 0.078s と一番速くなった．


HaskellのtakeWhile展開版

primes = 2 : filter isPrime [3,5..]
{-
isPrime n = not $ any (isDivisor n) $ takeWhile (limit >=) primes
    where
      limit = floor $ sqrt $ fromIntegral n
-}
isPrime n = loop primes
    where loop (x:xs) | limit < x = True
                      | isDivisor n x = False
                      | otherwise = loop xs
              where limit = floor $ sqrt $ fromIntegral n

isDivisor n m = rem n m == 0

main = print $ primes !! 10000