This page is mainly about the fibonacci sequence for now!
I created this page to have a playground for sharing scheme code.
I haven't read the license yet, but I hope its ok.
Here goes some code:
;; ;; Simple, but horrible implementation of Fibonacci. ;; Fine for numbers up to 20-30 with a modern PC. ;; (define (fib x) (if (< x 2) x (+ (fib (-1+ x)) (fib (- x 2)))))
Slightly improved version (I guess its O(n) ?)
(define (fib2 x)
(define (fib-call i fibonacci-of-i-before fibonacci-of-i x-to-reach)
(cond ((>= i x-to-reach)
fibonacci-of-i)
((< i x-to-reach)
(fib-call (1+ i)
fibonacci-of-i
(+ fibonacci-of-i-before fibonacci-of-i)
x-to-reach))))
(cond ((< x 2)
x)
(#t (fib-call 1 0 1 x))))
;; ;; Slightly shorter version of the above ;; (define (fib n) (let loop ((v '#(0 1)) (n n)) (cond ((< n 2) (vector-ref v n)) (else (loop (vector (vector-ref v 1) (+ (vector-ref v 0) (vector-ref v 1))) (- n 1))))))
In GNU Emacs Lisp, you can do a hash implementation, I guess with the complexity about O(n) like this:
(defun fib-init-hash-fib () "Initialiser hash mm." (setq fib-hash (make-hash-table)) (puthash 0 0 fib-hash) (puthash 1 1 fib-hash)) (defun fib-hash-fib (n) "Returns fibonacci of n, using hash-optimizing." (let* ((debug nil) (tmp (gethash n fib-hash))) (cond ((null tmp) (progn (if debug (insert (format "Calculating fib for %d (no hash yet). " n))) (setq tmp (+ (fib-hash-fib (1- n)) (fib-hash-fib (- n 2)))) (puthash n tmp fib-hash) (if debug (insert (format "The result of fib(%d) has been calculated, it is %d!\n" n tmp))) tmp)) (t (progn (if debug (insert (format "The hash tells me that fib(%d) er %d.\n" n tmp))) tmp)))))
You would run it like this:
(fib-init-hash-fib) (progn (let ((n 40)) (insert (format "\nFibonacci of %d is %d!" n (fib-hash-fib n)))))
According to Evoli, it might be possible to implement it O(log n)? with matrices (I don't understand matrices - yet)). She has pasted this code: (I hope its ok to publish it here).
;; for everyone wondering what "transpose" is (define (transpose m) (apply map list m)) ;; matrix multiplication: (define (rowxcol row col) (fold-right + 0 (map * row col))) (define (make-row row cols) (map (lambda (col) (rowxcol row col)) cols)) (define (m-mult m1 m2) (let ((cols (transpose m2))) (map (lambda (row) (make-row row cols)) m1))) ;; raise matrix to pwr ; only works for positive integers (define (exp-m m pwr) (cond ((= pwr 1) m) ((even? pwr) (exp-m (m-mult m m) (/ pwr 2))) (else (m-mult m (exp-m m (- pwr 1)))))) (define (fib n) (caar (exp-m '((1 1) (1 0)) (- n 1))))
;; ;; Slightly shorter version of the matrix computation above ;; (define (fib n) (define (elem v w i j k l) (+ (* (vector-ref v i) (vector-ref w j)) (* (vector-ref v k) (vector-ref w l)))) (define (mul v w) (vector (elem v w 0 0 1 1) (elem v w 0 1 1 2) (elem v w 1 1 2 2))) (vector-ref (let loop ((v '#(1 0 1)) (n n)) (cond ((= n 0) v) ((even? n) (let ((w (loop v (/ n 2)))) (mul w w))) (else (mul (loop v (- n 1)) '#(0 1 1))))) 1))