4. Rekursive Definition einer Taylorreiche

Rekursive Definition einer Taylorreiche

  • I

    Hallo zusammen
    Ich benötige die rekursive Variante der Taylorreiche für den Sinus. Weiss vielleicht jemand, wie die geht?
    Vielen Dank! 🙂

    Samuel

    0
  • K

    Gegenfrage: Ist das fuer dein Lisp-Projekt? Da die Taylorreihe nur eine Summe ist, dann kannst du dir auch mal ueber die rekursive Variante einer Summe Gedanken machen. Dann brauchst du nur noch eine Vorschrift, wie die einzelnen Terme T(f,n) abhaengig von der zu entwickelnden Funktion als auch vom Index generiert werden (kann wahrscheinlich auch ohne Index geschehen, wenn man das wieder rekursiv gestaltet).

    Ansonsten steht hier was dazu: http://www.springerlink.com/content/u7857678773k6452/ . Kann aber nicht genau sagen ob es passt. Ich hoffe deine Schule/Uni/... hat freien Zugang dazu.

    0
  • I

    @knivil

    Hehe erwischt! 😉 Ich muss eben heute Abend um 00:00 Uhr abgeben und war zu faul (Zeitdruck), das zu berechnen, desshalb habe ich ins Forum geschrieben.
    Wenn du schon mal da bist, kann es sein, dass Lisp, um die 50zigste Fibonacci Zahl zu berechnen, über 1h 😮 braucht?

    ; function fibanocci
(defun fibanocci (c)
 (if (> c 1) (+ (fibanocci (- c 1)) (fibanocci (- c 2))) c)
)

    Mein (imperatives) C Pendant benötigt für die millionste Stelle gerade mal 2.93ms...
    Klar das Lisp Teil ist nicht Tailrekursiv, aber kann das alleine wirklich so viel ausmachen?

    0
  • K

    50zigste Fibonacci Zahl zu berechnen, über 1h

    Kommt drauf an, was du fuer ein Lisp benutzt. Kommt drauf an, ob Lisp interpretiert oder compiliert wird. Kommt drauf an, wie du die Folge implementiert hast ... Ich sehe, du hast die langsame (naive) Variante benutzt.

    Klar das Lisp Teil ist nicht Tailrekursiv, aber kann das alleine wirklich so viel ausmachen?

    Nein, mehrere Ausdruecke werden mehrfach neu berechnet. Das ist nicht noetig.

    0
  • I

    clisp kompiliert

    0
  • K

    Es gibt eine iterative Variante: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.2 . Auch weiss ich nicht wie weit der C-Kompiler die rekursive Variante optimiert.

    Btw.: Was bedeutet "millionste Stelle" bei dir. Auch waere es mit neu, dass C so grosse Datentypen von Haus aus mitbringt.

    Ein Testlauf der iterativen Variante unter Ikarus (interpretiert):

    > (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))))
> (time (fib 50))
running stats for (fib 50):
    no collections
    0 ms elapsed cpu time, including 0 ms collecting
    0 ms elapsed real time, including 0 ms collecting
    120 bytes allocated
12586269025

    Mein (imperatives) C Pendant benötigt für die millionste Stelle gerade mal 2.93ms...

    Ich habe es mal naive in C++ implementiert, kann die 2.93ms aber nicht bestaetigen.

    Programm:

    #include <stdint.h>
#include <iostream>

uint64_t fib(uint64_t n)
{
    if (n > 1) return fib(n-1) + fib(n-2);
    else return 1;
}

int main()
{
    std::cout << fib(50) << std::endl;
    return 0;
}
    0
  • I

    Du hasts ja auch rekursiv gemacht...

    // required headers
#include <stdio.h>

// function fibanocci
int fibanocci(int n){
 // declare local variables
 int a = 0, b = 1;
 int i,t;

 // a loop for iterating over
 // the intermediate results
 for(i=2;i<=n;++i){
  t = a;
  a = b;
  b = t+b;
 }

 // finally return the result
 return b;
}

// function call
int main(){
 int a;
 scanf("%d",&a);
 printf("%d",fibanocci(a));
 return 0;
}
    0
  • I

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

    0
  • K

    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.

    0
  • I

    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... 😉

    0
  • K

    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.

    0
  • I

    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?

    0
  • K

    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.

    0
  • I

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

    0
  • K

    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.

    0
  • B

    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.

    0
  • I

    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)))
    0
  • I

    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;
}
    0
  • ?

    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.
    🙂

    0
  • ?

    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

    🙂

    0
  • I

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

    0
Anmelden zum Antworten