wozu gibts Rekursion ?
Iteration ist doch immer schneller als Rekursion, oder nicht?
Gibts da bestimmte Bereiche in denen man rekursiv arbeiten muss ?
Oder irgendwelche Vorteile von Rekursion ?
Soweit ich weiss, kann man auch alle rekursiven Programme/Methoden iterativ programmieren. Aber
manchmal ist's eben einfacher es rekursiv zu machen - meine Meinung.
Es gibt einfach ein paar Dinge, die man super mit Rekursion loesen kann. Wenn man nicht genau weiss, wie tief etwas
geschachtelt ist - zum Beispiel die Organisationsstruktur einer Firma, ... Da wird's dann komplizierter, wenn man's mit
Iteration versucht - denke ich.
Ist Rekursion immer langsamer? Hab' ich noch nicht gehoert. Macht das so viel aus? Ist doch nur eine Methode,
die sich selber wieder aufruft... ???:L
1) Jede Rekursion lässt sich iterativ ausdrücken !
-> Rekursion und Iteration sind äquivalente Konzepte.
2) Afaik ist in der Regel die iterative Lösung schneller und weniger speicherintensiv.
3) Wie bambi auch schon sagte gibt es gewisse Probleme die "von Natur aus" rekursiv sind, bekanntes Beispiel: Fakultät.
SOlche Probleme lassen sich dann schnell rekursiv lösen...wobei man manchmal u.U. etwas länger über einer iterativen Lösung sitzt.
Entscheidend ist das Abbruchkriterium, also der Anker der Rekursion - so dass du keine Endlosschleife fabrizierst.
wie meine Vorredner schon sagte, sie sind äquivalent. Dennoch gibt es probleme die intuitiver und einfacher zu lösen sind mit einer der beiden Wege.....
typische Fälle, wo Rekursion "einfacher" zu implementieren ist:
einen Verzeichnisbaum durchwandern
ein XML dokument durchwandern
überhaupt alles, wo baumähnliche strukturen verarbeitet werden
es gibt auch Algorithmen, die inhärent rekursiv definiert werden - z.B. der Quicksort für eine Liste mit n elementen
- teile die listen in zwei hälften
- so dass alle Elemente der Linken hälfte kleiner sind als alle rechten
- sortiere jetzt die linke Hälfte , sortiere die rechte hälfte (=die rekursion)
die umsetzung per "iteration" ist irgendwie "hässlich"...
3) Wie bambi auch schon sagte gibt es gewisse Probleme die "von Natur aus" rekursiv sind, bekanntes Beispiel: Fakultät.
SOlche Probleme lassen sich dann schnell rekursiv lösen...wobei man manchmal u.U. etwas länger über einer iterativen Lösung sitzt.
*Hust*, Fakultät ist wohl das Beispiel wo eine Rekursion total übertrieben ist... :wink:
Eine Rekursion muss übrigens nicht unbedingt längsämer als eine Iteration sein. Denn bei jedem Methodenaufruf werden nur ein paar Bytes auf den Stack geschrieben (ein Methodenaufruf "kostet" nicht viel). Wenn man stattdessen jedesmal irgendwas z.B. in einer Liste speichert (die auch noch die grösse eines Arrays verwalten muss, und und und..) kann das Iterative Verfahren schlechter sein.
(Irgendwelche Sortieralgorithmen, wie Mergesort, sind da ein Beispiel)
Mmh, okay das sind en paar durchaus einleuchtende Einwände.
Aber wie entscheide ich mich für bzw gegen Rekursion/Iteration ?
Nach welchen Kriterien gehe ich da vor, wenn ich etwas programmieren soll?
ist auch nette Illustration der Tatsache, dass man beim iterativen Algorithmus immer "den Zustand" mitschleppen muss - der bei der rekursion "unsichtbar" auf dem Stack liegt...
Code:
int summe=0;
int old_summe=1;
int older_summe=1;
for(int i=3;i<=20;i++){
summe = old_summe + older_summe;
System.out.println("fibo "+i+"="+summe);
older_summe = old_summe;
old_summe = summe;
}
@Bleiglanz
Genau. Eine "optimierte" iterativen Lösung ist schneller, trägt aber nicht unbedingt dazu bei,
dass der Code verständlicher wird. Insbesondere beim Aufbau einer Baumstruktur ist eine
Rekursion meist einfacher als eine entsprechende Iteration.
Nur mal zur Ergänzung. Fibonacci rekursiv. Hier erkennt man den Algorithmus besser
als in der iterativen Lösung.
public class Fibonacci1 {
static int fibonacci(int n) {
if (n <= 2)
return 1;
else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
public static void main(String args[]) {
int series = Integer.parseInt(args[0]);
int i = series-1;
System.out.println("Fibonacci["+(i+1)+"]= "+fibonacci(i));
}
}
Diese Art der Berechung ist wirklich verdammt langsam, sprich es ist ein schlechetr Algorithmus. Im übrigen funktioniert das bei int auch nicht mit größeren Zahlen. Selbst, wenn du die Methode als long machst, wird die Berechnung dadurch nicht schneller. Hinweis: Fibonbacci(48 ) dauerte auf meinem Rechner über 100 Sekunden!
Du kannst dir ja einmal überlegen, wie man den Algorithmus ändern muss, damit er deutlich schneller wird.
public class Fibonacci1 {
static int fibonacci(int n) {
if (n <= 2)
return 1;
else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
public static void main(String args[]) {
int series = Integer.parseInt(args[0]);
int i = series-1;
System.out.println("Fibonacci["+(i+1)+"]= "+fibonacci(i));
}
}
Ja, ja, aber ich hab mir nur sein verhackstücktes Code-Schnipsel zu Gemüte geführt und nicht den ganzen Kram.
Aber BTW: Schreib du doch einmal einen performanten Fibo-Algorithmus. Ich habe hier einen, der schafft Fibo(192) in 10 Millisekunden. Anstatt große Töne zu spucken, selber programmieren, ok?
Aber BTW: Schreib du doch einmal einen performanten Fibo-Algorithmus. Ich habe hier einen, der schafft Fibo(192) in 10 Millisekunden. Anstatt große Töne zu spucken, selber programmieren, ok?
Ist ja nicht böse gemeint
BTW:
So? laut Zeitmessung 0, aber das hat keine Aussagekraft bei einem Durchlauf :wink:
Code:
public class Fibo
{
public static final double a = (1.0 + Math.sqrt(5))/2.0;
public static final double b = (1.0 - Math.sqrt(5))/2.0;
public static final double c = 1.0/Math.sqrt(5);
static double fibonacci(int n)
{
return c*(Math.pow(a,n)-Math.pow(b,n));
}
public static void main(String[] args)
{
long time = System.currentTimeMillis();
System.out.println(System.currentTimeMillis()-time);
System.out.println((int)fibonacci(192));
}
}
Der stimmt! Für extrem große Fibo Zahlen nimmt man allerdings statt dieses Algorithmus eine Abschätzung.
Stellt sich nur die Frage wer so große Fibo Zahlen braucht
Der stimmt! Für extrem große Fibo Zahlen nimmt man allerdings statt dieses Algorithmus eine Abschätzung.
Stellt sich nur die Frage wer so große Fibo Zahlen braucht
Du hast anders gezählt, deshalb hatte ich unterschiedliche Ergebnisse. Im übrigen rechnet der schon ab Zahlen von ca. 110 falsch, z.B.bei dir ergibt Fibo(112) = 2147483647, bei mir ergibt das 70492524767089125814114.
Das ist schon ein Unterschied. Was große Zahlen hierbei sind, kann ich nicht beurteilen, da die Fibonacci-Zahlenberechnung für mich eher eine akdemische Spielerei ist. Mein Algorithmus schafft auch locker noch Fibonacci(2000) = 26110059261835017683386709468290973244
755551891148434673972732304837738700379233077304107193139
7229163815763923061384387059799748107093064866796002570736
40788518590170986725049865841448425487683732713095512818304
319605370916773150142666250271238722380112347499842054782306
1798897850061317051695288512344497147185467181256973997545086
6912490650853945622130138277040986146312325044424769652148982077548213909414076005501
Schön, nicht? So, jetzt ist aber gut für heute. Gute Nacht!
Du hast anders gezählt, deshalb hatte ich unterschiedliche Ergebnisse. Im übrigen rechnet der schon ab Zahlen von ca. 110 falsch, z.B.bei dir ergibt Fibo(112) = 2147483647, bei mir ergibt das 70492524767089125814114.
Das ist schon ein Unterschied. Was große Zahlen hierbei sind, kann ich nicht beurteilen, da die Fibonacci-Zahlenberechnung für mich eher eine akdemische Spielerei ist. Mein Algorithmus schafft auch locker noch Fibonacci(2000) = 26110059261835017683386709468290973244
755551891148434673972732304837738700379233077304107193139
7229163815763923061384387059799748107093064866796002570736
40788518590170986725049865841448425487683732713095512818304
319605370916773150142666250271238722380112347499842054782306
1798897850061317051695288512344497147185467181256973997545086
6912490650853945622130138277040986146312325044424769652148982077548213909414076005501
Schön, nicht? So, jetzt ist aber gut für heute. Gute Nacht!
noch nicht *gg* muss mir mal die grundlegenden sachen dazu anlegen und dann kann ich mich erst drüber stürzen aber vielen dank für den lösungsansatz, natürlich kann ich viel damit anfangen weil ich weiss ja dann wies wirklich gehört und kann es dann besser nachvollziehen
andere frage: was ist das beste buch um sich java so schnell wie möglich im selbststudium beizubringen? ich hab das buch von mössenböck, sprechen sie java
Ich bin damals mit Java in 21 Tagen ganz gut gefahren, aber das ist Geschmacksache.
Immer eine gute Ergänzung ist Java ist auch eine Insel, da kostenlos :wink:
Bücher sind IMHO nur Begleitwerk. Am besten lernt man immer noch durch learning by doing!
Der stimmt! Für extrem große Fibo Zahlen nimmt man allerdings statt dieses Algorithmus eine Abschätzung.
Stellt sich nur die Frage wer so große Fibo Zahlen braucht
Sorry, aber dein Algorithmus ist nur bis zu Zahlen einer bestimmten Größe gültig. Das liegt daran, dass du dich bei der Berechnung nicht an die exakte, folgende Definition der Fibonacci-Zahlen gehalten hast:
Fn+1 = Fn + Fn-1
mit F0 = 0 und F1 = 1
Du hast stattdessen eine mathematische Eigenschaft der Fibonacci-Folge in deinem Algorithmus ausgenutzt (Stichwort: Goldener Schnitt). Das führt aber bei der Berechnung größerer Fibo-Zahlen zu Rundungsfehlern, weil eben die Wurzelberechnung nur mit einer bestimmten Nachkommastellenzahl durchgeführt wird.
Das nur zum besseren Verständnis, warum ich auch gestern leichte Zweifel in Bezug auf Korrektheit des Algorithmus gehegt habe. Also: Der von dir verwendete Algorithmus würde nur bei entsprechender Genauigkeit der Wurzelberechnung korrekte Fibo-Zahlen insbesondere bei größeren Werten liefern. Ich hatte bereits bei Fibo(80) bzw. Fibo(81) Abweichungen wie folgt festgestellt
Das nur zum besseren Verständnis, warum ich auch gestern leichte Zweifel in Bezug auf Korrektheit des Algorithmus gehegt habe. Also: Der von dir verwendete Algorithmus würde nur bei entsprechender Genauigkeit der Wurzelberechnung korrekte Fibo-Zahlen insbesondere bei größeren Werten liefern. Ich hatte bereits bei Fibo(80) bzw. Fibo(81) Abweichungen wie folgt festgestellt
Das ist mir völlig bewusst! Meine Aussage war aber das der Algorithmus korrekt ist, und das ist er auch!
Die Rundungsfehler passieren durch die "mangelnde" Genauigkeit der zugrundeliegenden Datentypen.
Ein Algorithmus wird jedoch unabhängig von seiner konkreten Implementierung betrachtet und daher können Rundungsfehler für den eigentlichen Algorithmus vernächlässigt werden. Um soetwas macht man sich erst in der Implementierung Gedanken.
abollm hat gesagt.:
Du hast stattdessen eine mathematische Eigenschaft der Fibonacci-Folge in deinem Algorithmus ausgenutzt (Stichwort: Goldener Schnitt). Das führt aber bei der Berechnung größerer Fibo-Zahlen zu Rundungsfehlern, weil eben die Wurzelberechnung nur mit einer bestimmten Nachkommastellenzahl durchgeführt wird.
Goldener Schnitt ist ein guter Punkt!
Hier werden sehr große Fibonacci Zahlen verwendet, und wie du der Formel für den goldenen Schnitt leicht entnehmen kannst, kommt es nicht auf die Genauigkeit der Fibonacci Zahlen an, und Rundungsfehler spielen daher nicht wirklich eine Rolle. Bei größeren Zahlen wird wie oben erwähnt sogar nur eine Abschätzung vorgenommen, was auch völlig ausreichend ist.
Wie gesagt: der Algorithmus ist korrekt und leifert auf einem 'perfekten Rechner' auch immer die richtigen Werte!
Musste ich noch loswerden :wink:
Wie gesagt: der Algorithmus ist korrekt und leifert auf einem 'perfekten Rechner' auch immer die richtigen Werte!
Musste ich noch loswerden icon_wink.gif
selbst in der theoretischen informatik kommen algorithmen, die mit reelen Zahlen arbeiten nur ganz am rand vor, drum nennt sich ein teil davon manchmal auch "diskrete mathematik" oder so
sowas wie deinen perfekten rechner gibts nicht, nicht einmal theoretisch (allein um eine einzige reelle zahl zu speichern bräuchte der "unendlich" viel RAM) => dein "Algorithmus" ist einfach ein Witz
in der realen Welt völlig unbrauchbar, kein Mensch würde dafür überhaupt das Wort "Algorithmus" verwenden
[..]Das ist mir völlig bewusst! Meine Aussage war aber das der Algorithmus korrekt ist, und das ist er auch!
Die Rundungsfehler passieren durch die "mangelnde" Genauigkeit der zugrundeliegenden Datentypen.
Ein Algorithmus wird jedoch unabhängig von seiner konkreten Implementierung betrachtet und daher können Rundungsfehler für den eigentlichen Algorithmus vernächlässigt werden. Um soetwas macht man sich erst in der Implementierung Gedanken.
Also vorweg: Jetzt wird die Diskussion richtig schön akademisch. Das mag ich manchmal.
Meine Argumentation zielt in diesem Fall und in ähnlichen Fällen natürlich stets auf eine mögliche Implementierung ab und nicht auf einen reinen, "akademischen" Algorithmus. Denn nur zum Selbstzweck wirst du wahrscheinlich allenfalls für Lern- und ähnliche Zwecke einen Algorithmus entwerfen (auf die Frage der Implementierung hast du auch korrekterweise hingewiesen).
Zur Sache:
Allerdings würde deine Argumentation mit den Rundungsfehlern, übertragen auf ein reales Problem (hier habe ich ein Beispiel aus dem Bereich Gebäudemanagement gewählt, s.u.), in etwa folgendes Gespräch provozieren:
Kunde: Der Algorithmus zur Berechnung der monatlichen Flächenumlagen rechnet falsch.
Antwort: Doch der rechnet richtig.
Kunde: Nein, der rechnet falsch, und zwar gibt es bei großen Hauptnutzflächen Abweichungen in den Ergebnissen zur Weiterberechnung der Flächenumlage.
Antwort: Das kann nur an der "mangelnden" Genauigkeit der verwendeten Datentypen liegen.
Kunde: ...???...
...
Um es klarzustellen: Eine meiner Argumentationen war, dass du dich nicht an die exakte mathematische Definition bei der Berechung der Fibonacci-Zahlen gehalten hast, sondern eine mathematische Gesetzmäßigkeit der Verhältnisse zweier aufeinanderfolgender und jeweils sehr großer Fibonacci-Zahlen ausgenutzt hast. Das mit dem "goldenen Schnitt" ist _eine_ Gesetzmäßigkeit, die bei näherer Untersuchung der Fibonacci-Folge herauskommt. Ausgangspunkt von Fibonacci waren aber Überlegungen zur Entwicklung einer Kaninchenpopulation unter Berücksichtigung bestimmter (idealer) Randbedingungen. Also eine reine zahlentheoretische Fragestellung, ohne jedwede Rundungsbetrachtungen. Es geht dabei um natürliche Zahlen (nichts mit Rundung und so!).
Wildcard hat gesagt.:
Goldener Schnitt ist ein guter Punkt!
Hier werden sehr große Fibonacci Zahlen verwendet, und wie du der Formel für den goldenen Schnitt leicht entnehmen kannst, kommt es nicht auf die Genauigkeit der Fibonacci Zahlen an, und Rundungsfehler spielen daher nicht wirklich eine Rolle. Bei größeren Zahlen wird wie oben erwähnt sogar nur eine Abschätzung vorgenommen, was auch völlig ausreichend ist.
Wie gesagt: der Algorithmus ist korrekt und leifert auf einem 'perfekten Rechner' auch immer die richtigen Werte!
Musste ich noch loswerden :wink:
Ich hoffe, du merkst jetzt, was ich meinte und meine. Einen perfekten Rechner gibt es m.W. noch nicht, denn dann könnte man beispielsweise auch die Kreiszahl Pi beliebig genau berechnen. Die Algorithmen dafür sind ja längst (Gauß, Bailey-Borwein-Plouffe etc.) bekannt.
BTW: Es gab mindestens vor einigen Jahren eine Zeitschrift, die sich nur den neuesten Erkenntnissen aus der Fibonacci-Folge widmet. Der Titel lautet "Fibonacci-Quarterly", herausgegeben von der Fibonacci-Gesellschaft.
Wie gesagt: der Algorithmus ist korrekt und leifert auf einem 'perfekten Rechner' auch immer die richtigen Werte!
Musste ich noch loswerden icon_wink.gif
Um das mal klarzustellen: natürlich kann man eine geschlossene Formel (die niemand als Algorithmus bezeichnen würde) mit einigen Tricks "berechnen" -> siehe Maple und andere zum "symbolischen Manipulieren" fähige Tools
Einen perfekten Rechner gibt es m.W. noch nicht, denn dann könnte man beispielsweise auch die Kreiszahl Pi beliebig genau berechnen. Die Algorithmen dafür sind ja längst (Gauß, Bailey-Borwein-Plouffe etc.) bekannt.
Nein, "dafür" sind keine Algorithmen bekannt, was du meinst sind NÄHERUNGSFORMELN
Sowas kann in der Realität nicht existieren, weil so ein Algorithmus "unendlich lange brauchen" würde, ganz zu schweigen von der internen Repräsentation einer reelen Zahl
-> das sind alles Phantastereien, wenn man von Algorithmen oder Computern redet, meint man "diskrete Maschinen"
ein Algorithmus, der sqrt(5) als "exakten Input" erwartet ist einfach nur ein schlechter Witz, sqrt(5) ist etwas, das mit Computern, endlichen Automaten usw. niemals zu "fassen" sein wird
Einen perfekten Rechner gibt es m.W. noch nicht, denn dann könnte man beispielsweise auch die Kreiszahl Pi beliebig genau berechnen. Die Algorithmen dafür sind ja längst (Gauß, Bailey-Borwein-Plouffe etc.) bekannt.
OK, sprachlich und inhaltlich falsch von mir. Ich habe das auch eher rhetorisch gemeint. Zudem bin ich kein ausgebildeter Mathematiker oder "vollwertiger Informatiker", das sei hinzugefügt. Das mit den Näherungsformeln ist korrekt, zumal die meisten realen Probleme, die im Computer modellhaft abgebildet werden, auf Näherungsformeln basieren. Allerdings hatte ich in meinen Informatikvorlesungen an der Uni den Begriff Algorithmus stets als Rechen- bzw. Handlungsanleitung zur Lösung von realen Problemstellungen vermittelt bekommen.
Hallo!
Ich muss jetzt auch mal etwas Senf dazugeben ;-) :
a) bzgl. Begriff "beliebige Genauigkeit":
Zitat:
Einen perfekten Rechner gibt es m.W. noch nicht, denn dann könnte man beispielsweise auch die Kreiszahl Pi beliebig genau berechnen. Die Algorithmen dafür sind ja längst (Gauß, Bailey-Borwein-Plouffe etc.) bekannt.
Nein, "dafür" sind keine Algorithmen bekannt, was du meinst sind NÄHERUNGSFORMELN
Sowas kann in der Realität nicht existieren, weil so ein Algorithmus "unendlich lange brauchen" würde, ganz zu schweigen von der internen Repräsentation einer reelen Zahl
Beliebige Genauigkeit heißt doch lediglich endliche Genauigkeit. Also lassen sich auch jetzt schon die Dezimalbruchentwicklungen sämtlicher berechenbaren irrationalen Zahlen beliebig genau berechnen (natürlich im Rahmen des Speicherplatzes und der Anzahl der Atome im Universum), und zudem bestimmen, bis wohin sie zu 100% mit der 'echten' Zahl übereinstimmen (Fehlabweichung). Daher lassen sich selbst unter Rückgriff auf Dezimaldarstellungen für eine Berechnung 100%-ige Aussagen mit beliebiger Genauigkeit treffen (es ist nur teilweise sehr trickreich, das Zusammenwirken der Fehlabweichungen untereinander zu bestimmen, da sich diese gegenseitig immer weiter aufschaukeln).
b) bzgl. Computer und Rechnen mit rellen Zahlen:
ein Algorithmus, der sqrt(5) als "exakten Input" erwartet ist einfach nur ein schlechter Witz, sqrt(5) ist etwas, das mit Computern, endlichen Automaten usw. niemals zu "fassen" sein wird
Quark:
sqrt(5) läßt sich z.B. als 'sqrt(5)' oder auf andere Art codiert exakt übergeben. Man muss ja nicht mit den Dezimaldarstellungen arbeiten, sondern der Computer kann ja auch symbolisch rechnen, z.B. mit cos(23), sqrt(5), PI, log, (oder anderen exakten Darstellungen, z.B. Potenzreihen mit berechenbaren Koeffizienten) und den dafür bewiesenen Rechengesetzen.
So können Computer sogar exakte irrationale Ergebnisse aus allen rationalen und (berechenbaren) irrationalen Zahlen berechnen.
Lediglich die Ergebnisdarstellung ist vielleicht nicht so 'schön', wenn sie ein komplizierter Ausdruck ist, aber dieser kann ja für irgendwelche Zwecke beliebig genau als Dezimalbruchentwicklung dargestellt werden.
Die Forderung, ein Rechner solle unendlich viele Nachkommastellen darstellen ist nur eine schön verpackte Endlosschleife.
c) bzgl. Fibonacci-Zahlen:
Wer größere Ergebnisse braucht, kann folgende simple Schleife verwenden, welche einfach BigInteger nutzt und exakte Ergebnisse liefert. Selbst fib(4000) geht bei mir damit noch in 60ms.
Code:
/**
* Returns the n'th Fibonacci number as a BigInteger.
*
[i]fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5, fib(6)=8,...[/i]
*
If [i]n[/i] < 0 then the value 0 is returned.
* @param n the index of the requested Fibonacci number
* @return the n'th Fibonacci-number as a BigInteger.
*/
public static BigInteger fib (int n)
{
if (n <= 0) return BigInteger.valueOf(0);
if (n <= 2) return BigInteger.valueOf(1);
BigInteger an_m2;
BigInteger an_m1 = BigInteger.valueOf(1);
BigInteger an = BigInteger.valueOf(2);
for (int i=3; i<n; i++)
{
an_m2 = an_m1;
an_m1 = an;
an = an_m1.add(an_m2);
}
return an;
}
d) bzgl. Rekursion/Iteration (zum eigentlichen Thema ;-) ):
Manchmal ist es schwierig, auf Rekursion zu verzichten, nämlich wenn die rekursiven Aufrufe aus der Mitte des Codes stammen (im Gegensatz zu endrekursiven Algorithmen). Der einzige Vorteil von Rekursionen ist in meinen Augen die Eleganz und manchmal extrem einfache Darstellung durch sie. Ansonsten sind sie nur eine potentielle Fehlerquelle für einen Stack-overflow und meist etwas langsamer als die iterative Version.
Beliebige Genauigkeit heißt doch lediglich endliche Genauigkeit. Also lassen sich auch jetzt schon die Dezimalbruchentwicklungen sämtlicher berechenbaren irrationalen Zahlen beliebig genau berechnen (natürlich im Rahmen des Speicherplatzes und der Anzahl der Atome im Universum), und zudem bestimmen, bis wohin sie zu 100% mit der 'echten' Zahl übereinstimmen (Fehlabweichung). Daher lassen sich selbst unter Rückgriff auf Dezimaldarstellungen für eine Berechnung 100%-ige Aussagen mit beliebiger Genauigkeit treffen (es ist nur teilweise sehr trickreich, das Zusammenwirken der Fehlabweichungen untereinander zu bestimmen, da sich diese gegenseitig immer weiter aufschaukeln)
Das stimmt tatsächlich, es gibt einige mathematische Beweise, die mit Computern und "endlicher Genauigkeit" arbeiten und trotzdem exakt sind - eben weil die Fehlerabschätzung voll durchgeschleift wird
Ändert aber nichts an der tatsache, dass die reelle Zahl sqrt(5) - nicht der symbolische Ausdruck - für Computer nicht exisitert, also kann sie auch nicht in einem "Algorithmus" vorkommen
Quark:
sqrt(5) läßt sich z.B. als 'sqrt(5)' oder auf andere Art codiert exakt übergeben. Man muss ja nicht mit den Dezimaldarstellungen arbeiten, sondern der Computer kann ja auch symbolisch rechnen, z.B. mit cos(23), sqrt(5), PI, log, (oder anderen exakten Darstellungen, z.B. Potenzreihen mit berechenbaren Koeffizienten) und den dafür bewiesenen Rechengesetzen.
So können Computer sogar exakte irrationale Ergebnisse aus allen rationalen und (berechenbaren) irrationalen Zahlen berechnen.
Du hast es erfasst (hab ich ja oben schon gesagt dass Maple das kann). Leider geht das auch völlig am Thema vorbei: Wenn du irgendeine Manipulationsmaschine für Symbole bei der Diskussion über "Algorithmen" zulässt, dann hab ich hier eine kleine Überraschung für dich: mein extrem effizienter, angenehm kurzer und kaum zu verbessernder Algorithmus zur Berechnung der n.-ten Fibonaccizahl sieht dann einfach so aus
Code:
fibo(n)
Dabei ist fibo übrigens das Symbol für die Fibonacci Funktion...
Die Forderung, ein Rechner solle unendlich viele Nachkommastellen darstellen ist nur eine schön verpackte Endlosschleife
Nein können sie nicht, sie können irrationale Zahlen ja intern nicht einmal darstellen (es sei den als "Symbol"),
was soll da "exaktes irrationales Ergebnis" sein - ein "exaktes" Symbol? Die mathematische Theorie der "Berechenbarkeit von reellen Zahlen" schaut ganz anders aus (und ist ziemlich esoterisch)
oder meinst du etwa, dass das exakte Resultat der Division von Pi durch zwei so aussieht
Code:
PI / 2
=> das ist gar nichts, reine Symbolmanipuliererei, was ist daran "exakt"?
Naja, eine 'einfache' Endlosschleife sähe z.B. so aus:
Code:
for (;;)
schreibe '1'
Eine 'schön' verpackte:
Code:
x = "Berechnungsvorschrift für eine (berechenbare) irrationale Zahl, welche bewiesenermaßen unendlich viele Nachkommastellen hat"
for (i=0; i < "Anzahl Nachkommastellen von x"; i++)
schreibe die i-te Nachkommastelle von x
Die mathematische Theorie der "Berechenbarkeit von reellen Zahlen" schaut ganz anders aus (und ist ziemlich esoterisch)
Berechenbarkeit war bei uns Stoff der Vorlesung "Einführung in Berechenbarkeit, Komplexität und formale Sprachen" (Theoretische Informatik) und hat mit Esoterik überhaupt nichts am Hut. Berechenbarkeit von reellen Zahlen findet sich z.B. in der Analysis I-Vorlesung über Darstellung durch Potenzreihen, und ist so esoterisch wie Mathe.
Besonders aber die Analysis I-Vorlesung krempelt einiges an vorher in der Schulzeit gebildeten Vorstellungen um.
Daher versuche ich mal, den diesbzgl. Stoff hier in einige Zeilen zu packen:
Das wichtigste zuerst: " Zahlen und ihre Eigenschaften existieren losgelöst von ihrer Darstellung ! "
Daher ist es egal, ob wir nun die 'Zahl 21' symbolisch als '21' (21 ist selbst auch nur ein Symbol !!), oder '0x15', oder '10101b' darstellen, ihre Eigenschaften bleiben.
Selbiges bei z.B. '0.1 (ternär)', welches dezimal schon periodisch ist '0.3333333...'. Durch Hin- und Herrechnen zwischen verschiedenen Basen können in der einen Darstellung extrem einfache Zahlenwerte stehen, in der anderen extrem schwierige Perioden. Allerdings: die Zahlen bleiben immer rational, daher können sie auch alle im Computer exakt als Bruch dargestellt werden.
Auf der Suche z.B. nach dem Faktor, mit dem man den Durchmesser eines Kreises multiplizieren muss, um den Umfang zu erhalten, kam man auf 'PI'. Wie sich herausstellte, ist diese Zahl irrational, aber sie ist berechenbar, und es gibt unzählige verschiedenene Verfahren dafür (einfach mal hier gucken: http://de.wikipedia.org/wiki/Kreiszahl).
Dabei ist PI nur ein stellvertretendes Symbol für einen beliebigen PI berechnenden Ausdruck, welcher wieder nur ein Symbol für die von ihrer Darstellung losgelöste "Kreiszahl" ist .
Selbiges gilt z.B. für 'sin(x)'. Diese Zeichenkette 'sin(x)' ist einfach nur eine kurze Schreibweise für:
Das Gebilde da rechts ist eine ('halbe') Potenzreihe.
Eine Potenzreihe ist von der Form:
Wobei die ak eine Folge aus z.B. den reellen Zahlen sind. Beim Sinus haben diese ak einfach das entsprechend angegebene Gestaltungsgesetz.
Ähnliche Potenzreihen gibt es für sämtliche anderen trigonometrischen Funktionen, aber auch z.B. für die e-Funktion:
...ebenso für den Logarithmus, die n-te Wurzel und jede andere Funktion, die man in der Schulzeit gelernt hat.
In der Schule hat man sich aber nur mit deren Symbol und den Ergebnissen beschäftigt, und nicht gefragt, wie z.B. der Taschenrechner auf das Ergebnis des Sinus kommt. Das Geheimnis dahinter ist die Darstellung als Potenzreihe (oder eine andere geeignete Darstellung).
Nun haben wir also irgendeine Zahl x (einfachheitshalber mit der Einschränkung 0 <= x <= 1). Dann können wir x als Dezimalbruchentwicklung darstellen:
Wählen wir hier die ak aus der Menge {0,1,2,3,4,5,6,7,8,9} und grenzen damit den Wert von x ein, so geben z.B. die Koeffizienten a1=2, a2=3, a3=4, a4=3, ... in der Schreibweise 0,2343... den Zahlenwert als Dezimalzahl wieder.
Andersherum: Die Ziffernfolge jeder Dezimalzahl aus [0,1] kann aufgefasst werden als Folge der Koeffizienten der obigen (indexverschobenen) Potenzreihe (mit z=1/10).
Daher gilt z.B. auch 0.999999.... = 1, das ist keine Definition, sondern ergibt sich aus:
Eine andere Basis entsteht entsprechend durch ersetzen der 10 durch b und abändern der Menge der Ziffern zu genau b geordneten Symbolen.
Das ganze läßt sich problemlos auf Vorkommastellen zzgl. Vorzeichen, und damit auf ganz R erweitern.
Was bis jetzt klarwerden sollte war einfach der eingangs erwähnte Satz:
" Zahlen und ihre Eigenschaften existieren losgelöst von ihrer Darstellung ! "
Wie wir Zahlen jetzt einem Computer zum Rechnen übergeben, und wie der damit dann rechnet, ist ja nun erstmal völlig egal. Es hat sich zwar die sehr effektive Fließkommaarithmetik etabliert, aber für manche Berechnungen ist diese einfach ungeignet. Fakt ist: Man kann jede berechenbare irrationale Zahl auf endlich viel Platz darstellen, indem man ihre Berechnungsvorschrift angibt. Außerdem exisitieren Rechengesetze, so dass sich damit exakt beliebig lange rechnen läßt. Komplizierte Ausdrücke als Ergebnis sind jedoch für uns Menschen nicht so angenehm, und auch um eine Vorstellung von der Größe der Zahl zu bekommen, wollen wir oft ihre Näherung als z.B. Dezimalziffernfolge sehen, und können dass dann mit beliebiger Genauigkeit unter Fehlabschätzung tun (bzgl. der Sicherheit der Fehlabschätzung gibt es allerdings Ausnahmen (z.B. an fraktalen Grenzen), welche dann aber erkannt werden können, und meist immernoch ein probabilistisches Ergebnis liefern können: zu 99% sind die ersten 10 Nachkommastellen der Zahl exakt 1,2324252627 ).
Noch ein kurzes Beispiel:
Ein Rechner würde bei sqrt( 2 ) * sqrt( 8 ) = 1.414214 * 2.828427 = 4.000001 ausgeben,
aber ein anderer bei sqrt( 2 ) * sqrt( 8 ) = sqrt( 2*8 ) = sqrt( 16 ) = 4
Es kann also durchaus Vorkommen, dass man durch Rechnen mit exakten Ausdrücken für irrationale Zahlen im Endeffekt auf Ergebnisse gelangt, die viel klarer sind, als die durch Fließkommaoperationen, und vielleicht sogar wieder eine natürliche Zahl ergeben.
...sie können irrationale Zahlen ja intern nicht einmal darstellen (es sei den als "Symbol")
was soll da "exaktes irrationales Ergebnis" sein - ein "exaktes" Symbol?
Ein solches Symbol ist also eine absolut effiziente Darstellung für eine exakte Berechnungsvorschrift, welche z.B. in Form eines Bildungsgesetzes für die Koeffizienten einer Potenzreihe gegeben sein könnte, mit welchem dann intern exakt weitergerechnet wird.
Das gilt natürlich nur für berechenbare irrationale Zahlen, aber die anderen interessieren auch nicht, da man mit ihnen ja sowieso überhaupt nicht rechnen kann (auch nicht symbolisch, einfach gar nicht).
Hoffentlich war die Stunde Arbeit für diesen Beitrag nicht umsonst ?
Ciao
kopfsalat
Ist sie nicht, es können zwar beliebig viele Dezimalziffern berechnet werden - soviele man will - aber eben nicht "alle"! Gewöhn dich lieber dran, dass das Wort "berechenbar" irgendeine vernünftige Bedeutung haben soll.
Deine "Verfahren" sind lediglich Approximationsverfahren, die aus mathematischen Reihendarstellungen für PI gewonnen werden
Das Gebilde da rechts ist eine ('halbe') Potenzreihe.
AHA: eine "berechenbare irrationale Zahl" IST also eine Zahl mit "Berechnungsvorschrift", da stellt sich mir sofort die Frage, was eine "Berechnungsvorschrift" sein soll
Mal davon abgesehen, dass du mit dem Wort "berechenbar" ziemlich salopp umgehst und nicht erklärst, was eine "Berechnungsvorschrift" sein soll ist das trotzdem völlig falsch
Dass PI ein Symbol für eine gewisse relle zahl ist, und ich diese also auf "wenig Platz" darstellen kann ist ja ganz nett...
Das gilt natürlich nur für berechenbare irrationale Zahlen, aber die anderen interessieren auch nicht, da man mit ihnen ja sowieso überhaupt nicht rechnen kann (auch nicht symbolisch, einfach gar nicht).
Hä? oben hast für jede Zahl in [0,1] eine "Berechnungsvorschrift" angeben, jetzt gibt es plötzlich welche, mit denen man "gar nicht rechnen kann"...????
sowas wie deinen perfekten rechner gibts nicht, nicht einmal theoretisch (allein um eine einzige reelle zahl zu speichern bräuchte der "unendlich" viel RAM) => dein "Algorithmus" ist einfach ein Witz
in der realen Welt völlig unbrauchbar, kein Mensch würde dafür überhaupt das Wort "Algorithmus" verwenden
Natürlich gibt es keine "perfekten Rechner", aber das bedeutet nicht das dieser Alogrithmus (zugeben ist das einsetzen von Zahlen in eine Formel ein sehr einfacher Algorithmus, aber er ist eben trotzdem einer) nicht korrekt ist!
In der realen Welt völlig unbrauchbar?
Seh ich etwas anders! Selbst auf unseren realen Rechner liefert dieser Algorithmus auch für extrem große Zahlen eine sehr gute Abschätzung der n-ten Fibonacci Zahl. Mit einem nach O-Kalkül zu vernachlässigendem Aufwand. Ich denke schon das das ein großer Vorteil gegenüber der rekursiven Ursprungsvariante ist!
Wenn man sich das Urpsrungsproblem, der Entwicklung einer Kaninchenpopulation, ansieht, wird man wohl feststellen das sich das Paarungsverhalten von 'unsterblichen' Kaninchen ohnehin nicht exakt an die Fibonacci-Zahlen hält, insofern ist eine Abschätzung doch mehr als gerechtfertigt?
ja das schon, aben eben keiner zur Berechnung der n-ten Fibonacci Zahl, sondern einer zur Berechnung einer NÄHERUNG der n-ten Fibonacci Zahl
>> bedeutet nicht ... nicht korrekt ist
was soll "korrektheit" bei einem Algorithmus zur Berechnung einer Näherung schon großartig bedeuten?
>> liefert eine sehr gute Abschätzung der n-ten Fibonacci Zahl
ja und? früher wolltest du noch ganz was anderes loswerden:
Meine Aussage war aber das der Algorithmus korrekt ist, und das ist er auch!
Die Rundungsfehler passieren durch die "mangelnde" Genauigkeit der zugrundeliegenden Datentypen.
Ein Algorithmus wird jedoch unabhängig von seiner konkreten Implementierung betrachtet und daher können Rundungsfehler für den eigentlichen Algorithmus vernächlässigt werden.
Wie gesagt: der Algorithmus ist korrekt und leifert auf einem 'perfekten Rechner' auch immer die richtigen Werte!
Musste ich noch loswerden
Wenn du das Ersetzen einen Algorithmus
[exakte Berechnung der n-ten Fibo]
durch einen ganz ganz anderen
[Berechnen einer Näherung der n-ten Fibo]
als "großen Vorteil" sehen willst, dann ists ja gut
Wenn du Äpfel willst und dann Birnen bekommst - ist das auch ein großer Vorteil?
Eine "berechenbare irrationale Zahl" ist natürlich eine irrationale Zahl, die berechenbar ist.
D.h., sie ist eine irrationale Zahl (hat also eine unendliche nicht-periodische Dezimaldarstellung), aber sie ist keine zusammenhangslose 'gewürfelte' Ziffernfolge, sondern die Ziffernfolge lässt sich berechnen. Das geschieht unter Angabe eines Algorithmus (in seiner Definition als beliebige Berechnungsvorschrift), der z.B. auf einer Potenzreihe basieren kann und auf endlich viel Platz beschrieben werden kann.
Berechenbarkeit von reellen Zahlen findet sich z.B. in der Analysis I-Vorlesung über Darstellung durch Potenzreihen
Es gibt viele Definitionen von Berechenbarkeit, welche aber äquivalent zueinander sind.
Das Ergebnis der Berechnung einer Berechnungsvorschrift ist berechenbar. Eine Potenzreihe kann Ausgangspunkt für einen solchen Algorithmus sein, und damit die jeweilige reelle Zahl berechenbar. Auch der Wikipedia-Link entspricht dieser Definition (wäre schlimm, wenn nicht).
...kam man auf 'PI'. Wie sich herausstellte, ist diese Zahl irrational, aber sie ist berechenbar, und es gibt unzählige verschiedenene Verfahren dafür
Du wirfst gedanklich die Begriffe "n-te Partialsumme" und den "Wert der Reihe" (also 'nach' dem Grenzübergang n gegen unendlich) durcheinander.
Der Wert der Reihe (also der Limes der Partialsummen) ist der exakte Wert von PI.
Anhand einer solchen Darstellung kann man natürlich ein Verfahren ableiten, um PI als Dezimalzahl darzustellen. Eine Darstellung als Dezimalzahl kann natürlich auf endlich viel Platz nur eine Näherung sein, aber das ist egal, da der Computer ja ohne Fehlabweichungen auch mit dem Wert der Reihe rechnen kann, wenn er dies geschickt anhand einer geeigneten Darstellung tut (insbesondere nicht als binär codierte Fließkomma-Zahl).
Das Gebilde da rechts ist eine ('halbe') Potenzreihe.
'halbe' steht in Klammern und in Anführungsstrichen, falls sich jemand darüber wundert, dass im Exponenten 2k+1 und nicht k steht. So wie die Reihe dort steht, kann sie nicht durch symbolische Substitution aus der Definition der Potenzreihe gewonnen werden, aber man kann diese Reihe ohne ihren Wert zu ändern zu einer entsprechenden Darstellung erweitern.
Zahlen und ihre Eigenschaften existieren losgelöst von ihrer Darstellung
Die Zeichenkette 'PI' bezeichnet dasselbe wie eine entsprechende Reihendarstellung, nämlich den exakten Wert der Kreiszahl. Indem man symbolisch mit diesen Darstellungen rechnen kann, ist die Konsequenz, dass man also mit einem Computer mit (berechenbaren) irrationalen Zahlen ohne Fehler rechnen kann. Der Wert des Ausdrucks 'PI/2' z.B. als Ausgabe einer Rechnung ist also das exakte Ergebnis. Du hattest den Ausdruck PI/2 vorhin so verächtlich erwähnt. Wenn mir mein Rechner als Ergebnis PI/2 liefert, dann freue ich mich darüber, dass er das exakte Ergebnis - obwohl irrational - berechnen und ausgeben kann. Das Ergebnis 1,5707963267 wäre nicht so interessant, da man niemals wüßte, ob das Ergebnis nun wirklich PI/2 ist, oder nur nah dran.
Fakt ist: Man kann jede berechenbare irrationale Zahl auf endlich viel Platz darstellen, indem man ihre Berechnungsvorschrift angibt.
AHA: eine "berechenbare irrationale Zahl" IST also eine Zahl mit "Berechnungsvorschrift", da stellt sich mir sofort die Frage, was eine "Berechnungsvorschrift" sein soll
Mal davon abgesehen, dass du mit dem Wort "berechenbar" ziemlich salopp umgehst und nicht erklärst, was eine "Berechnungsvorschrift" sein soll ist das trotzdem völlig falsch
Immerhin weiss ich, was ich mit dem Begriff 'berechenbar' meine.
"Berechnungsvorschrift" ist doch eigentlich selbsterklärend? Wenn irgendwas im intuitiven Sinne berechenbar ist, dann ist die Berechnungsvorschrift die auf endlich viel Platz passende Angabe eines Verfahrens, um das Ergebnis zu bestimmen. Das kann durchaus in Worten auf Papier geschehen.
Also ist der Satz "Man kann jede berechenbare irrationale Zahl auf endlich viel Platz darstellen, indem man ihre Berechnungsvorschrift angibt." nicht "trotzdem völlig falsch", sondern ganz im Gegenteil: wahr.
Dass PI ein Symbol für eine gewisse relle zahl ist, und ich diese also auf "wenig Platz" darstellen kann ist ja ganz nett...
...insbesondere, wenn man dieses Symbol dann in eine andere äquivalente Darstellung umwandeln kann, und damit dann korrekt rechnen, um exakte Ergebnisse zu produzieren (z.B. PI/2).
Das gilt natürlich nur für berechenbare irrationale Zahlen, aber die anderen interessieren auch nicht, da man mit ihnen ja sowieso überhaupt nicht rechnen kann (auch nicht symbolisch, einfach gar nicht).
Hä? oben hast für jede Zahl in [0,1] eine "Berechnungsvorschrift" angeben, jetzt gibt es plötzlich welche, mit denen man "gar nicht rechnen kann"...????
Stellt dir eine beliebige chaotische unendliche Dezimalziffernfolge vor. Diese stellt ebenso eine irrationale Zahl dar, aber wenn für sie keine "Berechnungsvorschrift"=="erzeugender Algorithmus"=="sie berechnende Turingmaschine" existiert, ist sie auch nicht berechenbar.
Nach der Churchschen These lässt sich übrigens alles Berechenbare durch eine entsprechend äquivalente Codierung einer entsprechenden Berechnungsvorschrift auf einer Turingmaschine, und damit auch auf einem PC ausführen.
Interessant dabei ist, dass es abzählbar unendlich viele Berechnungsvorschriften gibt, aber z.B. überabzählbar unendlich viele Dezimalzahlen (mit unendlich vielen Nachkommastellen). Daher gibt es "unendlich mal mehr" nicht-berechenbare Zahlen.
Die Energie, so ausführlich zu antworten ziehe ich übrigens daraus, dass es mich in diesem Beitrag gestört hatte, wie vehement herablässig urteilend einige deiner Aussagen in diesem Thread auf mich wirkten, obwohl Du teilweise nur zu weniger als 100% zu wissen scheinst, wie konform deine Aussagen mit bestehenden Definitionen sind.
Einfacher: Manchmal stimmen deine Aussagen einfach nicht, und du bist nicht bereit, das einzusehen. Ist ja nichts schlimmes, mal falsche Aussagen zu treffen, solange man nicht darauf beharrt. Auch wäre bei einigen Dingen eine vorsichtigere Formulierung angebracht, um nicht mit der Vehemenz der Aussage deren angeblich offensichtliche Wahrheit zu betonen.
Das fördert Fehlinformation, und kommt vermutlich bei den wenigsten gut an. Deswegen wollte ich hier mal ein paar Aussagen von dir inhaltlich unter die Lupe nehmen (und von mir aus gerne auch weiter inhaltlich diskutieren), aber ohne dich persönlich anzugreifen.
Wahrscheinlich bist du auch ganz anders (und viel symapthischer), als es diese Aussagen manchmal vermitteln, und deine fachliche Kompetenz (die sich auch in vielen anderen Beiträgen zeigt), möchte ich dir auf keinen Fall abstreiten.
Richtig! Ich hab die Implemtierung eines Algorithmus (bzw. einer Formel) angegeben, aber ich denke jeder durchschnittlich begabte Mensch kann die Berechnungsformel aus diesem Programm herauslesen?
Ich würde vorschlagen, den rechnenden Computer dann "Perfekt" zu nennen, wenn er niemals wiedersprüchliche Ergebnisse erzeugt.
Natürlich kann er Pi als "Symbol" oder als Double-Konstante speichern...
wenn ich jedoch den Computer frage: "Vieviele Pixel hat ein Kreis der um den Punkt 30,30 mit dem Radius 10 geht?" und er kann mir GARANTIERT richtig antworten, so definiere ich den Algorithmus/Computer als "perfekt". Klar ist, das solange Pi nur als Double gesoeichert ist, man sich Kreisdurchmesser von auf dem Schirm gepixelten Kreisen vorstellen kann, bei denen ein Pixel abhanden kommt. Genauso würde die Mondlandefähre ihr Ziel vielleicht um einige Millimeter verfehlen.
Wenn die Genauigkeit jedoch als eine im irgendwie diskretisierten Ergebnis als IM RAHMEN DER FINALEN DARSTELLUNG richtiges (d.h. in der letzten Stelle korrekt gerundetes) Ergebnis erscheint, würde ich "Perfekt" sagen. Das ist nie "wirklich" Pi, denn da gäbe es unednlich Nachkommastellen. Es steht aber auch nicht im Wiederspruch zu Pi, von der Rundung am Ende abgesehen.
Heutige Computer sind allerdings (Ohne BigDecimal z.b.) zumnidest hochgradig unperfekt, z.B. eine Linie mit der Steigung Pi am Bildschirm läuft in die Gefahr, einen "falschen" Pixel zu bemalen (mal abgesehen von der Definition der "Pixel einer Linie"... die in java.awt z.b. sehr akribisch angegeben ist...)
Für "Perfektion" wäre vermutlich symbolisches Rechnen bis kurz vor der Ausgabe oder einer volkommene Durchsetzung der Algotithmen mit Fehlerschranken und -Schätzungen nötig..
Mensch Wildcard, beweise doch einmal ein wenig Lesekompetenz und versuche 1. die eigentlichen Aussagen von Bleiglanz sowie 2. seine Absicht zu verstehen.
Nach meiner wiederholt dargestellten Meinung hast du dich 1. nicht an die korrekte Definition der Fibonacci-Zahlen gehalten und hast 2. einen Algorithmus oder von mir aus die Implementierung eines Algorithmus (A.) für eine _Näherung_ der Fibonacci-Zahlen angegeben (-> Bleiglanz' Argumentation). Dass du 3. dagegen hältst, dass die mit deinem A. zwangsläufig produzierten Abweichungen zu vernachlässigen sind, mag für einen Näherungs-A. ja vielleicht stimmen, aber eben nicht für eine präzise Berechnung der Fibonacci-Zahlen.
Du drehst dich bei deiner Argumentation im Kreise:
Implementierung des A. ist eine Näherung
der A. selbst nicht (was bitte schön ist der A. denn dann?)
Richtig! Ich hab die Implemtierung eines Algorithmus (bzw. einer Formel) angegeben, aber ich denke jeder durchschnittlich begabte Mensch kann die Berechnungsformel aus diesem Programm herauslesen?
Du drehst dich bei deiner Argumentation im Kreise:
Implementierung des A. ist eine Näherung
der A. selbst nicht (was bitte schön ist der A. denn dann?)
HILFE!!!
Was ist den daran so schwer zu verstehen?
Die rekursive Definition der Fibonacci Zahlen ist nur EINE Definition! Es ist aber nicht die EINZIGE!
Der Algorithmus (oder die Formel) ist eben keine Näherung, sondern exakt!
Das das mit double Werten eben nur begrenzte Genauigkeit hat damit doch überhaupt nichts zu tun!
Wir drehen uns hier echt im Kreis. Warum ist es denn so schwer zu akzeptieren das es eben auch andere Möglichkeiten gibt an dieses Problem heranzugehen, und das man sich die für den spezifischen Fall passende heraussucht? Die Formel ist kein Ersatz für den rekursiven Algorithmus, sonder eben eine Alternative!
Du drehst dich bei deiner Argumentation im Kreise:
Implementierung des A. ist eine Näherung
der A. selbst nicht (was bitte schön ist der A. denn dann?)
HILFE!!!
Was ist den daran so schwer zu verstehen?
Die rekursive Definition der Fibonacci Zahlen ist nur EINE Definition! Es ist aber nicht die EINZIGE!
Der Algorithmus (oder die Formel) ist eben keine Näherung, sondern exakt!
Das das mit double Werten eben nur begrenzte Genauigkeit hat damit doch überhaupt nichts zu tun!
Wir drehen uns hier echt im Kreis. Warum ist es denn so schwer zu akzeptieren das es eben auch andere Möglichkeiten gibt an dieses Problem heranzugehen, und das man sich die für den spezifischen Fall passende heraussucht? Die Formel ist kein Ersatz für den rekursiven Algorithmus, sonder eben eine Alternative!
Mensch, bleib locker. Du schreibst es ja inzwischen selbst: Wir drehen uns hier im Kreise. Aber zu einem wesentlichen Teil auch deshalb, weil du immer wieder bestimmte, einzelne Punkte , die du und die anderen Beteiligten in der Vergangenheit in diesem Thread niedergeschrieben haben, nicht in einen allgemeinen Kontext stellst.
An deiner obigen Argumentation ist - für sich genommen - zunächst _nichts_ zu bemängeln. Aber beachte dann bitte auch sorgfältig die bisherige Historie. Erst dann kann ein "Schuh daraus" werden.
Keine Sorge! Und zumindest für mich ist das ganze auch überhaupt nicht persönlich, sondern eben nur eine Diskussion.
abollm hat gesagt.:
An deiner obigen Argumentation ist - für sich genommen - zunächst _nichts_ zu bemängeln. Aber beachte dann bitte auch sorgfältig die bisherige Historie. Erst dann kann ein "Schuh daraus" werden.
Und um welchen 'Schuh' geht es jetzt?
Mein Standpunkt(an dem sich nichts geändert hat):
Die Formel berechnet die n-te Fibonacci Zahl korrekt. In der Praxis entstehen zwar Rundungsfehler, abhängig vom jeweiligen Verwendungszweck können diese allerdings ignoriert werden.
Ist das bei einem konkreten Problem der Fall, so ist diese Berechnungsmethode IMHO der 'klassischen' rekursiven Methode vorzuziehen,
da unabhängig von der Eingabe praktisch kein Berechnungsaufwand besteht. Brauche ich aus irgendwelchen Gründen exakte Werte für beliebige Eingaben nimmt man eben einen anderen Algorithmus zum Preis des höheren Aufwands. Einfach nur ein neues Werkzeug. Nicht mehr nicht weniger :wink:
Vergiss auch nicht warum wir überhaupt hier gelandet sind! Du wolltest das ich eine Prog schreibe das performanter als deins ist. Da ich vermute das du dir einige Gedanken über deinen Algorithmus gemacht hast, würde es mich doch sehr wundern wenn ich auf dem gleichem Lösungsweg einen besseren Algorithmus eben mal in 5 Minuten aus dem Ärmel schütteln könnte :wink:
Stattdessen habe ich eine Alternative angegeben, und da können wir jetzt drüber diskutieren solange wir wollen, je nach Problemstellung ist es eine Alternative!
Ist das ein Schuh der uns beiden passt?
An deiner obigen Argumentation ist - für sich genommen - zunächst _nichts_ zu bemängeln. Aber beachte dann bitte auch sorgfältig die bisherige Historie. Erst dann kann ein "Schuh daraus" werden.
Und um welchen 'Schuh' geht es jetzt?
Mein Standpunkt(an dem sich nichts geändert hat):
Die Formel berechnet die n-te Fibonacci Zahl korrekt. In der Praxis entstehen zwar Rundungsfehler, abhängig vom jeweiligen Verwendungszweck können diese allerdings ignoriert werden.
Ist das bei einem konkreten Problem der Fall, so ist diese Berechnungsmethode IMHO der 'klassischen' rekursiven Methode vorzuziehen,
da unabhängig von der Eingabe praktisch kein Berechnungsaufwand besteht. Brauche ich aus irgendwelchen Gründen exakte Werte für beliebige Eingaben nimmt man eben einen anderen Algorithmus zum Preis des höheren Aufwands. Einfach nur ein neues Werkzeug. Nicht mehr nicht weniger :wink:
Also zum Thema Aufwand möchte ich jetzt nicht etwas schreiben. Auch nicht darüber, dass der rekursive Algorithmus schneller als deiner sei, denn dass habe ich _nie_ behauptet. Beachte auch einmal meinen Code ein Stück weiter oben, und zwar den mit der _nicht_-rekursiven Variante.
Vergiss auch nicht warum wir überhaupt hier gelandet sind! Du wolltest das ich eine Prog schreibe das performanter als deins ist. Da ich vermute das du dir einige Gedanken über deinen Algorithmus gemacht hast, würde es mich doch sehr wundern wenn ich auf dem gleichem Lösungsweg einen besseren Algorithmus eben mal in 5 Minuten aus dem Ärmel schütteln könnte :wink:
Stattdessen habe ich eine Alternative angegeben, und da können wir jetzt drüber diskutieren solange wir wollen, je nach Problemstellung ist es eine Alternative!
Ist das ein Schuh der uns beiden passt?
An dieser Stelle machst du einen - zugegeben sehr kleinen - Fehler. Ich wollte nicht, dass du einen Algorithmus schreibst, der performanter als "meiner" ist. Zu dem Zeitpunkt hatte ich gar keinen Code von mir gepostet, sondern nur eine falsche "Lösung" zu der Frage der Posterin gesendet. Das mit dem Code kam erst nach meiner Aufforderung an dich. Dass sich daraus nun so ein Thread entwicklen würde, habe ich nicht intendiert, aber ich finde es mal ganz lustig über solche Dinge zu diskutieren, anstatt irgendeinem/-er Java-Anfänger/-in zum N-ten Mal bestimmte Dinge zu erläutern.
)
