dabian

Dabians page

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)) 

category-userpage