Meertens数 in Scheme DouKaku?

Meertens数

お題#100「正整数のゲーデル数化？」で定義した goedel を適用すると自分自身になるような数，すなわち goedel (n) == n となるような正整数 n を見つける関数を定義してください．

このような数のことをMeertens数と言うそうです．

32bitsの符号なし整数(あるいは10進10桁整数)までの範囲で探すのにどのくらい計算時間がかかったかをCPUのスペックとともに教えてください．また，その実装で64bit符号なし整数(あるいは10進20桁整数)までの範囲で探すのにどのくらい計算時間がかかりそうか見積ってください(もちろん実際に計算して計算時間を示していただくのでもかまいません)．

補足：

自分でやってみたHaskellでは30行ほどのプログラムで、10進10桁の範囲までの探索は ghci で 4.56秒(CPU Intel Core 2 Duo 2.6GHz)でした。

post comment

Posted feedbacks - Scheme

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?

Meertens数

Posted feedbacks - Scheme

Index

Feed

Other

Link

Pathtraq