(eval-when (:compile-toplevel :load-toplevel :execute)
(ql:quickload "cffi"))
(cffi:defcvar "errno" :int)
(cffi:defcfun "strerror" :string
"Map the error number to a locale-dependent error message string."
(errnum :int))
(cffi:define-foreign-library librt
(t (:default "librt")))
(cffi:use-foreign-library librt)
(cffi:defctype clockid-t :int)
(cffi:defctype time-t :long)
(cffi:defcstruct timespec
(tv_sec time-t)
(tv_nsec :long))
(cffi:defcfun (%clock-gettime "clock_gettime") :int
(clock-id clockid-t)
(tp (:pointer timespec)))
(defconstant +clock-realtime+ 0)
(defconstant +clock-monotonic+ 1)
(defconstant +clock-process-cputime+ 2)
(defconstant +clock-thread-cputime+ 3)
(defun clock-gettime (clock-id)
"Return the current value for the specified clock."
(let ((id (ccase clock-id
((:realtime) +clock-realtime+)
((:monotonic) +clock-monotonic+)
((:process-cputime) +clock-thread-cputime+)
((:thread-cputime) +clock-thread-cputime+))))
(cffi:with-foreign-object (tp 'timespec)
(unless (zerop (%clock-gettime id tp))
(error "Foreign function clock-gettime faild: ~a" (strerror *errno*)))
(values (cffi:foreign-slot-value tp 'timespec 'tv_sec)
(cffi:foreign-slot-value tp 'timespec 'tv_nsec)))))
(defmacro runtime ()
`(multiple-value-bind (sec nsec)
(clock-gettime :process-cputime)
(+ (* sec (expt 10 9)) nsec)))
(defun dividesp (a b)
(zerop (mod b a)))
(defun find-divisor (n test-divisor)
(cond ((> (expt test-divisor 2) n) n)
((dividesp test-divisor n) test-divisor)
(t (find-divisor n (1+ test-divisor)))))
(defun smallest-divisor (n)
(find-divisor n 2))
(defun primep (n)
(= n (smallest-divisor n)))
(defun report-prime (elapsed-time)
(princ " *** ")
(princ elapsed-time))
(defun start-prime-test (n start-time)
(when (primep n)
(report-prime (- (runtime) start-time))))
(defun timed-prime-test (n)
(terpri)
(princ n)
(start-prime-test n (runtime)))
(defun search-for-primes (start end)
(when (oddp start)
(timed-prime-test start))
(when (< start end)
(search-for-primes (1+ start) end)))runtimeがないので、clock_gettimeを使って定義する。精度はナノ秒。また、定義が自明なため、奇数の判別には組み込みのoddpを使っている。
> (search-for-primes 1000 1050) 1001 1003 1005 1007 1009 *** 9114 1011 1013 *** 8887 1015 1017 1019 *** 9054 1021 *** 9078 1023 1025 1027 1029 1031 *** 9275 1033 *** 9431 1035 1037 1039 *** 9162 1041 1043 1045 1047 1049 *** 9066 NIL > (search-for-primes 10000 10050) 10001 10003 10005 10007 *** 23444 10009 *** 23803 10011 10013 10015 10017 10019 10021 10023 10025 10027 10029 10031 10033 10035 10037 *** 23983 10039 *** 23486 10041 10043 10045 10047 10049 NIL > (search-for-primes 100000 100050) 100001 100003 *** 73907 100005 100007 100009 100011 100013 100015 100017 100019 *** 73650 100021 100023 100025 100027 100029 100031 100033 100035 100037 100039 100041 100043 *** 73279 100045 100047 100049 *** 73584 NIL > (search-for-primes 1000000 1000050) 1000001 1000003 *** 217447 1000005 1000007 1000009 1000011 1000013 1000015 1000017 1000019 1000021 1000023 1000025 1000027 1000029 1000031 1000033 *** 216698 1000035 1000037 *** 216829 1000039 *** 227579 1000041 1000043 1000045 1000047 1000049 NIL
おおむねそれらしい値になっている。純粋な処理時間以外にも、手続きを呼び出すオーバーヘッドなども含まれるので、多少の誤差は許容範囲内と思われる。
