Rekursive Definition einer Taylorreiche

Ishildur

Kann mir noch schnell jemand erklähren, warum der naive Approach Milliarden von Berechnungen benötigt, für die 50zi Fibonacci Zahl? Das habe ich irgendwie noch nicht ganz verstanden...

Ishildur schrieb:

über 1h braucht?

*lol*
Mein Lisp ist mindestens 3600x schneller als deines, ich hab nämlich in dem Makro das 'memoize' vergessen, und es gar nicht gemerkt.

Ishildur schrieb:

Kann mir noch schnell jemand erklähren, warum der naive Approach Milliarden von Berechnungen benötigt, für die 50zi Fibonacci Zahl? Das habe ich irgendwie noch nicht ganz verstanden...

http://mitpress.mit.edu/sicp/full-text/book/ch1-Z-G-13.gif

Mein Lisp ist mindestens 3600x schneller als deines

Das nehm ich zurück. Ich hab mich nur die ganze Zeit verschaut und falsch kopiert. Es muss also heissen:

> (define-syntax defun
    (syntax-rules ()
      ((defun nam (arg ...) body ...)
       (define nam (memoize (lambda (arg ...) body ...))))))

Ishildur

@µngbd
Hehe, ich habe dieses Beispiel (also meines) als gutes Beispiel, wie man es NICHT macht, in die Doku geschrieben...

Ishildur schrieb:

@µngbd
Hehe, ich habe dieses Beispiel (also meines) als gutes Beispiel, wie man es NICHT macht, in die Doku geschrieben...

Man muss es nur richig interpretieren. Mit Common Lisp ist das nur ein wenig schwieriger:

(defun memoize (f)
  (let ((table (make-hash-table)))
    (lambda (x)
      (let ((old-result (gethash x table)))
        (or old-result
            (let ((result (funcall f x)))
              (setf (gethash x table) result)
              result))))))

(defmacro dufen (nam args . body)
  `(setf (fdefinition (quote ,nam))
         (memoize
           (lambda ,args
             ,@body))))

(dufen fibanocci (c)
 (if (> c 1) (+ (fibanocci (- c 1)) (fibanocci (- c 2))) c)
)