Rekursive Definition einer Taylorreiche

Ishildur

Musste noch int mit __int64 ersetzen, sonsts gehts nicht...

knivil

Du hasts ja auch rekursiv gemacht...

Es ist voellig witzlos, die iterative Variante mit der rekursiven zu vergleichen. Das hat auch nichts mit Lisp oder C zu tun, sondern allein mit der Laufzeitkomplexitaet: Sie waechst bei der naiven Variante mit fib(n), d.h. fuer fib(50) braucht man einige Milliarden Operationen. Bei der iterativen Variante eben nur 50. Daraus irgendwas abzuleiten ist Bullshit. Es sind grundsaetzlich zwei verschiedene Algorithmen. Mit Ikarus (Scheme) + iterativ habe ich 0ms gebraucht, um fib(50) zu berechnen.

Ishildur

Ich finde es äberhaupt nicht witzlos, denn Lisp ist eine funktionale Programmiersprache. Wenn ich iterativ programmieren will, brauche ich keine funktionale Programmiersprache sondern kann gleich eine imperative verwenden...

Ich habe in der funktionalen Programmiersprache Lisp ein funktionales Programmierparadigma und in der imperativen Sprache C ein imperative Programmierparadigma verwendet und die beiden Varianten bezüglich Laufzeitkomplexität verglichen...

knivil

Wenn ich iterativ programmieren will, brauche ich keine funktionale Programmiersprache

Die iterative Variante ist auch rekursiv, wenn du mal genau hinschaust. Auch scheinst du noch nicht den Sinn oder Unsinn von funktionalen Sprachen verstanden zu haben.

Ich habe in der funktionalen Programmiersprache Lisp ein funktionales Programmierparadigma

Nein, hast du nicht.

Ishildur

Die iterative Variante ist auch rekursiv

Ist sie das?

Auch scheinst du noch nicht den Sinn oder Unsinn von funktionalen Sprachen verstanden zu haben

Das ist gut möglich, erkärst du es mir?

knivil

1.) iterativ != imperativ
2.) rekursiv != funktional

Wenn du dir den Wikipedia-Artikel http://de.wikipedia.org/wiki/Funktionale_Programmierung durchliesst, dann fallen bei der Zusammenfassung (also ganz oben) weder die Begriffe Rekursion noch iterativ.

Ishildur

Ja das ist mir schon klar, aber ist es nicht so, dass die funktionalen Sprachen tendenziell eher rekursive Problemlösungsstrategien propagieren?

knivil

Problemlösungsstrategien propagieren?

Ja, aber wie du siehst, kann Rekursion in vielen Gestallten daherkommen. Hier ruft sich fib-iter auch rekursiv auf:

(define (fib n)
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

Was ich damit sagen will: Man kann in C (oder C++ oder Java oder ...) als auch in Lisp (oder Scheme oder Haskell oder ...) schlecht programmieren.

Das ist gut möglich, erkärst du es mir?

Schau bei Wikipedia und Co. Bei konkreten Fragen kann ich gern konkrete Antworten liefern, aber du verlangst etwas viel zu umfassendes.

Bashar

Ishildur schrieb:

Ja das ist mir schon klar, aber ist es nicht so, dass die funktionalen Sprachen tendenziell eher rekursive Problemlösungsstrategien propagieren?

Ja, aber nur, weil man ohne Zuweisungen keine Schleifen realisieren kann. Das heißt nicht, dass man munter drauf los ineffizienten Code schreibt. Man kann den Fibonacci auch rekursiv effizient implementieren. Mancheiner nennt das dann auch "iterativ" (=> SICP), aber das ist nicht sehr verbreitet.

Ishildur

Ich habe wegen der Taylor Reihe mal folgenden Lisp Code geschrieben, aber sobal ich mehr als 17 Iterationen mache, kommt Lisp mit einem "floating point overflow" weisst du vielleicht, was das zu bedeuten hat?
Die berechneten Sinuswerte stimmen ansonsten (bei iterationen kleiner 17)

; function power (x^n)
(defun pow (x n)
 (if (eql n 0) 1 (* x (pow x (- n 1))))
)

; function factorial (n!)
(defun fac (n)
 (if (eql n 0) 1 (* n (fak (- n 1))))
)

; function taylor (sin(x) n = resolution)
(defun taylor (x n)
 (let ((a (+ (* n 2) 1)))
  (if (eql n 0) x (+ (* (if (eql (rem n 2) 0) 1 -1) (/ (pow x a) (fac a))) (taylor x (- n 1))))
 )
)

; function call
(format t "~A~%"  (time (taylor 1.57 1000)))

Ishildur

Hier ist noch das iterative C Pendant, dass ich geschrieben habe. Vielleicht vereinfacht dies das Verständnis (Ich habe absichtlich auf die math.h library (pow) verzichtet):

// function sin (iterative implementation)
double sin(double x,int n){
 // declare and init local variables
 int i,k;        // iterators
 double r = 0.0; // result
 double a,b;     // two temporary variables

 // start a loop for walking each iteration
 for(i=0;i<n;++i){
  // init both temporary variables by
  // the multiplicative identity
  a = b = 1.0f;

  // start a loop for evaluating
  // the expression on the right side
  for(k=1;k<=2*i+1;++k){
   a *= x;
   b *= k;
  }

  // add the current iteration to the result
  r += (i%2 ? -1 : 1)*a/b;
 }

 // finally return the result
 return r;
}

Ishildur schrieb:

Wenn du schon mal da bist, kann es sein, dass Lisp, um die 50zigste Fibonacci Zahl zu berechnen, über 1h braucht?

Bashar schrieb:

Man kann den Fibonacci auch rekursiv effizient implementieren. Mancheiner nennt das dann auch "iterativ" (=> SICP), aber das ist nicht sehr verbreitet.

Ach was. Blätter weiter bis zu "memoizing", und spar dir die iterativen Trivialitäten, die kennst du doch ohnehin schon.

Also etwa so:

> ; SRFI 69
(define (memoize f)
  (let ((table (make-hash-table)))
    (lambda (x)
      (let ((old-result (hash-table-ref table x)))
        (or old-result
            (let ((result (f x)))
              (hash-table-set! table x result)
              result))))))
> (define-syntax defun
    (syntax-rules ()
      ((defun nam (arg ...) body ...)
       (define nam (lambda (arg ...) body ...)))))
> ; kaum macht mans richtig :)
(defun fibanocci (c)
 (if (> c 1) (+ (fibanocci (- c 1)) (fibanocci (- c 2))) c)
)
> (fibanocci 500)
139423224561697880139724382870407283950070256587697307264108962948325571622863\
290691557658876222521294125

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