http://www.reddit.com/r/programming/comments/2mzy3/ask_reddit_whats_the_fastest_fibonacci_algorithm

- Code: Select all
`(define (pair-multiply p1 p2)`

(let ((ac (* (car p1) (car p2)))

(ad (* (car p1) (cadr p2)))

(bc (* (cadr p1) (car p2)))

(bd (* (cadr p1) (cadr p2))))

(list (+ ac ad bc) (+ ac bd))))

(define (pair-pow p n)

(cond

((= n 1) p)

((even? n)

(let ((result (pair-pow p (truncate (/ n 2)))))

(pair-multiply result result)))

(else

(let ((result (pair-pow p (truncate (/ n 2)))))

(pair-multiply p (pair-multiply result result))))))

(define (fib n)

(if (zero? n)

0

(car (pair-pow '(1 0) n))))

My quick attempt is :

- Code: Select all
`(defun pair-multiply (p1 p2)`

(let ((ac (* (car p1) (car p2)))

(ad (* (car p1) (cadr p2)))

(bc (* (cadr p1) (car p2)))

(bd (* (cadr p1) (cadr p2))))

(list (+ ac ad bc) (+ ac bd))))

(defun pair-pow (p n)

(cond

((= n 1) p)

((evenp n)

(let ((result (pair-pow p (truncate (/ n 2)))))

(pair-multiply result result)))

(let ((result (pair-pow p (truncate (/ n 2)))))

(pair-multiply p (pair-multiply result result)))))

(defun fast-fib (n)

(if (zerop n)

0

(car (pair-pow '(1 0) n)))

And CLISP says :

;; Loading file fibonacci.lisp ...

*** - SYSTEM::%EXPAND-FORM: (RESULT (PAIR-POW P (TRUNCATE (/ N 2)))) should be

a lambda expression

The following restarts are available:

SKIP :R1 skip (DEFUN PAIR-POW # ...)

STOP :R2 stop loading file C:\Users\Andre\Codes\fibonacci.lisp

ABORT :R3 Abort main loop

Break 1 [2]>

I wonder where my mistake is ...