フィボナッチ計算アルゴリズム比較のアレ

gistfile1.sls

#!/opt/local/bin/gosh

;;;
;;; Source Code
;;;


;; Sequential T transform O(log(n))
(define (fib-t n)
  (let iter [(a 1) (b 0) (p 0) (q 1) (count n)]
    (cond [(= count 0) b]
	  [(even? count)
	   (let ((p2 (+ (* p p) (* q q)))
		 (q2 (+ (* q q) (* 2 p q))))
	     (iter a b p2 q2 (/ count 2)))]
	  [else
	   (let ((a2 (+ (* b q) (* a q) (* a p)))
		 (b2 (+ (* q a) (* p b))))
	     (iter a2 b2 p q (- count 1)))])))

;; Multiple Receive Values
(define (fib-m n)
  (letrec ((fib-i (lambda (n)
		    (if (<= n 1) (cons 1 1)
			(let* ((xs (fib-i (- n 1)))
			       (x0 (cdr xs))
			       (x1 (car xs)))
			  (cons (+ x1 x0) x1))))))
    (car (fib-i n))))

;; Orthodox Recursive
(define (fib-o n)
  (if (<= n 1) 1
      (+ (fib-o (- n 2)) (fib-o (- n 1)))))


;;;
;;; Running Result
;;;

(time (fib-t 730000))
; real   2.170
; user   2.140
; sys    0.010

(time (fib-m 150000))
; real   2.171
; user   2.080
; sys    0.030

(time (fib-o 35))
; real   2.184
; user   2.130
; sys    0.000

;;; EOF