読者です 読者をやめる 読者になる 読者になる

フィボナッチ数の話

素数体係数多項式の拡張GCDを書かないといけないのだが, それはさておき.
ストリーム版が無いけど気にするな.

;;;素朴
(define (fib1 n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib1 (- n 1)) (fib1 (- n 2))))))
;(time (fib1 30))
; real   0.285
; user   0.281
; sys    0.000

;;;末尾再帰
(define (fib2 n)
  (define (fib-iter i a b)
    (if (= n i) a
      (fib-iter (+ i 1) b (+ a b))))
  (fib-iter 0 0 1))
;(time (number? (fib2 100000)))
; real   1.407
; user   1.217
; sys    0.156

;;;ハッシュ
(define (fib3 n)
  (define fib-in-memo
    (let1 ht (make-hash-table 'eqv?)
          (define (memo m v) (hash-table-put! ht m v) v)
          (lambda (m)
            (cond ((= m 0) 0)
                  ((= m 1) 1)
                  ((hash-table-get ht m #f))
                  (else
                   (memo m
                         (+ (fib-in-memo (- m 1))
                            (fib-in-memo (- m 2)))))))))
  (fib-in-memo n))
;(time (number? (fib3 100000)))
; real   2.077
; user   1.514
; sys    0.546

;;;行列
;;;                                 (1 1)
;;; (f(n+2) f(n+1)) = (f(n+1) f(n)) (1 0)
(use gauche.array)
(define (fib4 n)
  (array-ref (array-expt (array (shape 0 2 0 2) 1 1 1 0) n) 1 0))
;(time (number? (fib4 100000)))
; real   0.215
; user   0.218
; sys    0.000

;;;エラー処理とか面倒ですよね
(define (fib n)
  (if (and (integer? n) (not (negative? n)))
      (array-ref (array-expt (array (shape 0 2 0 2) 1 1 1 0) n) 1 0)
    (error "Non-negative integer required:" n)))