DouKaku? 6824 baal: Gauche と Chicken で計測...(Meertens数)

Comment detail

Gauche と Chicken で計測してみました。
流石にコンパイラの Chicken は速いです。
インタプリタの Gauche もなかなか健闘していると思います。

20桁だと Chicken を使えば 19 時間くらいでしょうか。
まだもうちょっと枝刈り頑張れそうな気もします。

Gauche
   8 桁    0.330s
   9 桁    1.158s
  10 桁    3.924s
  11 桁   12.226s
  12 桁   37.540s
  13 桁 1m48.757s

Chicken
   8 桁    0.122s
   9 桁    0.376s
  10 桁    1.201s
  11 桁    3.670s
  12 桁   10.892s
  13 桁   31.896s

CPU: Intel(R) Pentium(R) 4 CPU 1.80 GHz

(define make-primes (lambda (n)
    (let loop1 ((i 3) (result '(2)) (len 1))
        (if (< len n)
            (if (let loop2 ((ls result))
                    (or (not (pair? ls))
                        (and (not (zero? (modulo i (car ls))))
                            (loop2 (cdr ls)))))
                (loop1 (+ i 1) (append result (list i)) (+ len 1))
                (loop1 (+ i 1) result len))
            result))))

(define meertens (lambda (digit)
    (letrec ((primes (make-primes digit))
            (mx (expt 10 digit))
            (search (lambda (n g d p result)
                (if (< d digit)
                    (let loop ((i 0) (r result))
                        (if (< i 10)
                            (let ((nn (+ (* n 10) i)) (gg (* g (expt (car p) i))))
                                (if (< gg mx)
                                    (let ((rr (loop (+ i 1) (search nn gg (+ d 1) (cdr p) r))))
                                        (if (= nn gg) (cons nn rr) rr))
                                    r))
                            r))
                    result))))
        (search 0 1 0 primes '()))))

(for-each
    (lambda (x) (display x) (newline))
    (meertens 10))

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq