http://www.reddit.com/r/programming/com ... _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))))
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)))
I wonder where my mistake is ...;; 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]>