# Rekursion versus Iteration



## Guest (12. Mrz 2005)

Hi,

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 ?


----------



## bambi (12. Mrz 2005)

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


----------



## mic_checker (12. Mrz 2005)

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.


----------



## bygones (12. Mrz 2005)

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


----------



## Bleiglanz (12. Mrz 2005)

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


----------



## Beni (12. Mrz 2005)

mic_checker hat gesagt.:
			
		

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


----------



## Guest (12. Mrz 2005)

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?


----------



## mic_checker (12. Mrz 2005)

Beni hat gesagt.:
			
		

> *Hust*, Fakultät ist wohl _das_ Beispiel wo eine Rekursion total übertrieben ist... :wink:


Naja - ich meinte damit eher die "mathematische Definition" der Fakultät:

n! = n * (n-1)!

Das lässt sich natürlich direkt rekursiv programmieren (ok, in diesem Fall ist die iterative Lösung nicht viel schwerer  )


----------



## Guest (13. Mrz 2005)

Versuche mal die Fibonacci-Funktion iterativ zu lösen. :bae:

```
: 1               für ( 0 < n <= 2 )
f(n) : f(n-1) + f(n-2) für ( n > 2      )
     : nicht definiert für ( n <= 0     )
```


----------



## Bleiglanz (13. Mrz 2005)

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

```
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;
}
```


----------



## Guest (13. Mrz 2005)

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

```
int fibonacci(int n) {
  return (n>2)? fibonacci(n-1) + fibonacci(n-2): 1;
}
```


----------



## babuschka (17. Mrz 2005)

hallo alle zusammen!
ich lerne seit einer woche java programmierung und hab eine frage zu dieser aufgabe:

static int fibonacci (int n)}
if(n<=2)}
return 1;
}else{
return fibonacci(n-1)+fibonacci(n-2);
}
}

wie stellt man das jetzt iterativ dar? hab herumprobiert aber mein programm schreibt mir immer fehlermeldungen  :cry:


----------



## abollm (17. Mrz 2005)

Java Anfaenger hat gesagt.:
			
		

> wie stellt man das jetzt iterativ dar? hab herumprobiert aber mein programm schreibt mir immer fehlermeldungen  :cry:



So z.B.:

```
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));
	   }
}
```


----------



## abollm (17. Mrz 2005)

Noch folgender Hinweis:

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.


----------



## Wildcard (17. Mrz 2005)

Java Anfaenger hat gesagt.:
			
		

> wie stellt man das jetzt iterativ dar? hab herumprobiert aber mein programm schreibt mir immer fehlermeldungen





			
				Abollm hat gesagt.:
			
		

> So z.B.:
> 
> 
> 
> ...


lol! Er wollte doch eine iterative Version haben


----------



## abollm (17. Mrz 2005)

Wildcard hat gesagt.:
			
		

> lol! Er wollte doch eine iterative Version haben



Stimmt - blöd, wenn man nicht richtig lesen kann! Aber, wenigstens funkt. die rekursive Lösung ja.


----------



## Wildcard (17. Mrz 2005)

Abollm hat gesagt.:
			
		

> Stimmt - blöd, wenn man nicht richtig lesen kann! Aber, wenigstens funkt. die rekursive Lösung ja.



Da steht da oben aber schonmal   


> ```
> int fibonacci(int n) {
> return (n>2)? fibonacci(n-1) + fibonacci(n-2): 1;
> }
> ```


----------



## abollm (17. Mrz 2005)

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?


----------



## abollm (17. Mrz 2005)

Da Wildcard nicht in die Strümpfe kommt, hier nun eine Variante mit rekursiver und nicht-rekursiver Berechung der Fibo-Zahl:


```
public class Fibonacci1 {

	/** Rekursive Methode */
	static long fibonacciRecursive(int n) {
		if (n <= 2)
			return 1;
		else {
			return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
		}
	}

	/** Nicht-rekursive, iterative Methode */
	static long fibonacciNonRecursive(int n) {
		int i = 1;
		long fibk = 1;
		long fibk_1 = 0;
		/*
		 * fibk   = fibonacci(i)
		 * fibk_1 = fibonacci(i-1)
		 */

		while (i < n) {
			i++;
			long fibk_2 = fibk_1;
			fibk_1 = fibk;
			fibk = fibk_1 + fibk_2;
		}
		return fibk;
	}

	public static void main(String args[]) {
		int series = Integer.parseInt(args[0]);
		int i = series - 1;
		long now1 = System.currentTimeMillis();
		System.out.println("Fibonacci rekursiv[" + (i + 1) + "]= "
				+ fibonacciRecursive(i));
		long duration1 = System.currentTimeMillis() - now1;
		System.out.println("Rekursive Berechnung benötigte " + duration1 + " "
				+ " Millisekunden zur Erzeugung");
		long now2 = System.currentTimeMillis();
		System.out.println("Fibonacci nicht-rekursiv[" + (i + 1) + "]= "
				+ fibonacciNonRecursive(i));
		long duration2 = System.currentTimeMillis() - now2;
		System.out.println("Nicht-rekursive Berechnung benötigte " + duration2 + " "
				+ " Millisekunden zur Erzeugung");
	}
}
```


----------



## Wildcard (17. Mrz 2005)

Abollm hat gesagt.:
			
		

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

```
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));
        
    }
}
```


----------



## abollm (17. Mrz 2005)

Wildcard hat gesagt.:
			
		

> [
> Ist ja nicht böse gemeint
> BTW:
> So? laut Zeitmessung 0, aber das hat keine Aussagekraft bei einem Durchlauf  :wink:
> [..]



Ist schon ok, aber sag mal, meinst du, dass dein Algorithmus richtig rechnet? Irgendwie kommen mir da Zweifel.


----------



## Wildcard (17. Mrz 2005)

abollm hat gesagt.:
			
		

> Ist schon ok, aber sag mal, meinst du, dass dein Algorithmus richtig rechnet? Irgendwie kommen mir da Zweifel.


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


----------



## abollm (17. Mrz 2005)

Wildcard hat gesagt.:
			
		

> abollm hat gesagt.:
> 
> 
> 
> ...



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!


----------



## Wildcard (17. Mrz 2005)

Abollm hat gesagt.:
			
		

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



Spassvogel! Weil du über den Zahlenbereich von int rausläuft! Mach halt wieder double draus!  :roll:
Hatte den cast nur wegen der Ausgabe drin.


----------



## babuschka (17. Mrz 2005)

ohhhhhhhh gotttttttt ich hoffe ich werd das auch mal alles so hinkriegen wie ihr!!!!!!!
außerdem der er ist ne sie *gg*


----------



## Wildcard (17. Mrz 2005)

SRY! Java-AnfaengER hat für mich männlich impliziert  :wink: 
Kannst du damit jetzt was anfangen?


----------



## babuschka (17. Mrz 2005)

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


----------



## Wildcard (17. Mrz 2005)

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!


----------



## abollm (18. Mrz 2005)

Wildcard hat gesagt.:
			
		

> abollm hat gesagt.:
> 
> 
> 
> ...



@Wildcard:

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

23416728348467748          -> Fibo 
23416728348467685          -> Fibonacci1 abollm


----------



## Wildcard (18. Mrz 2005)

abollm hat gesagt.:
			
		

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


----------



## Bleiglanz (18. Mrz 2005)

> Wie gesagt: der Algorithmus ist korrekt und leifert auf einem 'perfekten Rechner' auch immer die richtigen Werte!
> Musste ich noch loswerden icon_wink.gif


das ist bullshit

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


----------



## abollm (18. Mrz 2005)

Wildcard hat gesagt.:
			
		

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


----------



## abollm (18. Mrz 2005)

Bleiglanz hat gesagt.:
			
		

> > Wie gesagt: der Algorithmus ist korrekt und leifert auf einem 'perfekten Rechner' auch immer die richtigen Werte!
> > Musste ich noch loswerden icon_wink.gif
> 
> 
> ...



Bleiglanz, eines muss man dir lassen: Du hast manchmal eine sehr direkte, prägnante Ausdruckswahl. Ehrlichen Respekt!


----------



## Bleiglanz (18. Mrz 2005)

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


----------



## abollm (18. Mrz 2005)

Bleiglanz hat gesagt.:
			
		

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


----------



## kopfsalat (18. Mrz 2005)

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



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.

```
/**
     * 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.


----------



## Bleiglanz (19. Mrz 2005)

> 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

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


Das ist jetzt wirklich mal Quark, kannst du erklären, was dieser Satz aussagen soll?


----------



## Bleiglanz (19. Mrz 2005)

> So können Computer sogar exakte irrationale Ergebnisse aus allen rationalen und (berechenbaren) irrationalen Zahlen berechnen.


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

```
PI / 2
```
=> das ist gar nichts, reine Symbolmanipuliererei, was ist daran "exakt"?


----------



## kopfsalat (19. Mrz 2005)

> > Die Forderung, ein Rechner solle unendlich viele Nachkommastellen darstellen ist nur eine schön verpackte Endlosschleife
> 
> 
> Das ist jetzt wirklich mal Quark, kannst du erklären, was dieser Satz aussagen soll?


Naja, eine 'einfache' Endlosschleife sähe z.B. so aus:

```
for (;;)
  schreibe '1'
```
Eine 'schön' verpackte:

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


----------



## Bleiglanz (19. Mrz 2005)

> Hoffentlich war die Stunde Arbeit für diesen Beitrag nicht umsonst ?


leider doch, du hast nämlich vergessen zu sagen was eine "berechenbare irrationale Zahl" überhaupt sein soll 



> Berechenbarkeit von reellen Zahlen findet sich z.B. in der Analysis I-Vorlesung über Darstellung durch Potenzreihen


Das ist leider nicht die Art von "Berechenbarkeit", die man in der Informatik braucht 

http://de.wikipedia.org/wiki/Berechenbarkeit
http://de.wikipedia.org/wiki/Finitismus



> ...kam man auf 'PI'. Wie sich herausstellte, ist diese Zahl irrational, aber sie ist berechenbar, und es gibt unzählige verschiedenene Verfahren dafür


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.


neee nee, das ist schon eine ganze! dass ein paar Koeffizienten 0 sind macht gar nichts



> Zahlen und ihre Eigenschaften existieren losgelöst von ihrer Darstellung


ja und?



> 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

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


----------



## Wildcard (19. Mrz 2005)

Wow! reges Interesse   


			
				Bleiglanz hat gesagt.:
			
		

> das ist bullshit


Sehr sachlich  :wink: 



			
				Bleiglanz hat gesagt.:
			
		

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


----------



## Bleiglanz (19. Mrz 2005)

>>aber er ist eben trotzdem einer

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


Man kann eben gar nicht von "korrekt" reden, weil du ja gar keinen Algorithmus angegeben hast ....




> Ich denke schon das das ein großer Vorteil gegenüber der rekursiven Ursprungsvariante ist!


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?


----------



## kopfsalat (20. Mrz 2005)

Am liebsten würde ich ja nur folgendes antworten:
:### 

Aber inhaltlich wäre das dann doch ein bißchen wenig, daher...



> > Hoffentlich war die Stunde Arbeit für diesen Beitrag nicht umsonst ?
> 
> 
> leider doch, du hast nämlich vergessen zu sagen was eine "berechenbare irrationale Zahl" überhaupt sein soll


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
> 
> 
> Das ist leider nicht die Art von "Berechenbarkeit", die man in der Informatik braucht
> ...


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
> 
> 
> Ist sie nicht, es können zwar beliebig viele Dezimalziffern berechnet werden - soviele man will -  aber eben nicht "alle"!


PI ist berechenbar. Punkt.



> Gewöhn dich lieber dran, dass das Wort "berechenbar" irgendeine vernünftige Bedeutung haben soll.


Gewöhn dich lieber dran,  dass das Wort "berechenbar" bereits eine vernünftige Bedeutung _hat_.



> Deine "Verfahren" sind lediglich Approximationsverfahren, die aus mathematischen Reihendarstellungen für PI gewonnen werden


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.
> 
> 
> neee nee, das ist schon eine ganze! dass ein paar Koeffizienten 0 sind macht gar nichts


'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
> 
> 
> ja und?


Die Zeichenkette 'PI' bezeichnet dasselbe wie eine entsprechende Reihen_darstellung_, 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
> ...


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.

Nix für ungut + keep on rock'n roll.  8)


----------



## Wildcard (20. Mrz 2005)

Bleiglanz hat gesagt.:
			
		

> >>aber er ist eben trotzdem einer
> 
> 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


Zum letzten mal: Die Implementierung ist eine Näherung. Der Algorithmus nicht und insofern korrekt.


			
				Bleiglanz hat gesagt.:
			
		

> Man kann eben gar nicht von "korrekt" reden, weil du ja gar keinen Algorithmus angegeben hast ....


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?


----------



## dronus (20. Mrz 2005)

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


----------



## abollm (20. Mrz 2005)

Wildcard hat gesagt.:
			
		

> Bleiglanz hat gesagt.:
> 
> 
> 
> ...




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?



Ja, und? War das hier verlangt?


----------



## Wildcard (20. Mrz 2005)

abollm hat gesagt.:
			
		

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


----------



## abollm (20. Mrz 2005)

Wildcard hat gesagt.:
			
		

> abollm hat gesagt.:
> 
> 
> 
> ...



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.


----------



## Wildcard (20. Mrz 2005)

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?


----------



## abollm (20. Mrz 2005)

Wildcard hat gesagt.:
			
		

> [..]
> 
> 
> 
> ...


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.

Mir passt jetzt der "Schuh" durchaus, dir auch?


----------



## Wildcard (20. Mrz 2005)

abollm hat gesagt.:
			
		

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


Stimme ich dir voll und ganz zu!



> Mir passt jetzt der "Schuh" durchaus, dir auch?


Schön das wir jetzt beide neue Schuhe haben  :wink:


----------



## Sym (21. Mrz 2005)

Wildcard hat gesagt.:
			
		

> Abollm hat gesagt.:
> 
> 
> 
> ...


Der Algorithmus ist es gar nicht wert, ein Algorithmus geschimpft zu werden. Da wird einfach die explizite Formel genutzt. :LOL:
Mein bisher schnellster Algorithmus (bis auf die o.g Lösung ) war die Matrix-Vektor Multiplikation der entsprechenden Matrix.


----------



## Bleiglanz (21. Mrz 2005)

@kopfsalat: immer locker bleiben, es geht mir einzig und allein um eine gewisse Genauigkeit und Schärfe der Begriffe



> Am liebsten würde ich ja nur folgendes antworten:
> 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.


Wir sind uns wohl einig was wir mit "Berechenbarkeit" meinen? Nämlich die einzig existierende Definition, für die man laut Church jede sinnvolle bekannte Definition einsetzen kann, nehmen wir von mir aus Turingmachinenberechenbarkeit (ist ja egal)

Eine reelle Zahl x kann in dieser Definition gar nicht berechenbar sein (weil in diesem Kontext reelle Zahlen überhaupt nicht vorkommen), dagegen könnte es einen Algorithmus _D_ geben, der bei eingabe einer natürlichen Zahl k die ersten k Ziffern der Dezimalentwicklung von x berechnet.  Das  soll vermutlich deine Definition von "berechenbarer reeller Zahl" sein.

Finde ich ganz OK als Definition für "berechenbare reelle Zahl", IMHO macht es aber keinen Sinn zu sagen, dass der Algorithmus D den *WERT* dieser Zahl berechnet



> Das Ergebnis der Berechnung einer Berechnungsvorschrift ist berechenbar.


Frage: Ist als Ergebnis eine relle Zahl erlaubt?



> PI ist berechenbar. Punkt.


In obigem Sinn ja, allerdings macht der Algorithmus etwas anderes als man umgangssprachlich erwarten würde: er "berechnet" nicht die Zahl Pi, sondern für gegebenes k die ersten k Dezimalziffern. 

Und um zum ursprünglichen Fibonacci-Problem zurückzukehren: sqrt(5) ist "berechenbar" - egal was das heisst -  kann in diesem Fall sqrt(5) INNERHALB einer Berechnungsvorschrift (=Algorithmus, Programm) vorkommen???



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


Tu ich nicht, das ist mir noch nie passiert dass ich die beiden verwechsle. Dieser Wert kann überhaupt nicht in irgendeiner Rechenmaschine "dargestellt werden", also kannst IMHO nicht sagen, dass es eine Maschine gibt, die diesen Wert "berechnet"



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


Hä? Wie soll er mit "dem Wert der Reihe" rechnen, wenn er diesen Wert gar nicht kennt?? Er kann natürlich Berechnungen mit der Näherung durchführen - und bei geschickter Programmierung auch für das Ergebnis wieder Zusicherungen über die Genauigkeit machen (sog. Intervall-Artithmetik)



> Die Zeichenkette 'PI' bezeichnet dasselbe wie eine entsprechende Reihen_darstellung_, 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.


Du freust dich nur deshalb, weil _zufällig_ PI zum Alphabet deiner Symbol-Manipulations-Maschine gehört, über die allermeisten Wörter, die von dieser Maschine ausgespuckt werden würdest du dich wohl nicht freuen!

Schon wahr, das symbolische Rechnen hat einen gewissen Sex-Appeal. Aber angenommen, dein symbolischer Kalkulator gibt dir eine hyperkomplizierte Formel aus (eine unendliche Reihe oder was schlimmeres): der "Wert" könnte Pi sein oder auch nicht, wie willst du das entscheiden??



> Immerhin weiss ich, was ich mit dem Begriff 'berechenbar' meine.


es muss was sonderbares sein



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


wohl war, wenn man "berechenbare reelle Zahl" so definiert wie oben gesagt




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


Über die konformität meiner Aussagen mit "bestehenden Definitionen" bin ich mir schon im klaren, glaubs mir



> Einfacher: Manchmal stimmen deine Aussagen einfach nicht, und du bist nicht bereit, das einzusehen.


Ja, warum sagst du mir dann keine?? Die "stimmen nicht", weil wir unter den verwendeten Begriffen etwas ganz anderes verstehen (also meine Aussage "Alle Quargl sind Quirgl" ist in deinen Augen falsch, weil bei dir ein Quirgl eben etwas ganz anderes ist...

oder sag mir mal ganz konkret eine wirklich nachprüfbare falsche Aussage von mir in diesem Thread



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


das hast du eben ganz genau nicht gemacht. Wenn du das tun willst, dann schreib bitte vorher auf, was du unter

"berechenbarer reeller Zahl"

verstehen willst.


----------



## Bleiglanz (21. Mrz 2005)

ACH JA, UM MAL ZUM THEMA ZURÜCKZUKOMMEN

wollte ich eigentlich ganz am anfang schreiben, bin leider abgeschwoffen

bei manchen Rekursionen ("deterministisch") besteht die möglichkeit zur Optimierung: 

Die naive rekursive Implementierung f(n)=f(n-1)+f(n-2) hat einen gewaltigen Nachteil, weil nämlcih f(1) vieeeel zu oft berechnet wird

wenn man man genau hinschaut

f(n-1) 
/* wenn ich hier reinrekursiere...
    dann wird doch f(n-2) eh mit berechnet
    ...
    am besten ich lass mir f(n-2) als seiteneffekt mit zurückgeben
     .....
    das funktioniert ja dann auch "rekursiv..."
*/

+

f(n-2)


----------



## kopfsalat (21. Mrz 2005)

> (...)dann schreib bitte vorher auf, was du unter "berechenbarer reeller Zahl" verstehen willst.



Na, dass hier:



> Wozu führte Turing die Idee einer solchen Maschine ein? Mit ihrer Hilfe definierte er eine "berechenbare Zahl" ("computable number") als reelle Zahl, für die eine passend programmierte Turing-Maschine jede Dezimalstelle ausgeben kann, ausgehend von einem leeren Band. Turing zeigte, dass die Menge der berechenbaren Zahlen abzählbar ist, und gab auch eine nicht-berechenbare Zahl an.



Hinter deinem Wiki-Link stand zwar auch die Definition einer berechenbaren reellen Zahl, aber etwas versteckt:


> Zudem lassen sich geeignete Wörter definieren, die eine schnell konvergierende Approximation von reellen Zahlen darstellen. Über solche Wörter lässt sich der Berechenbarkeitsbegriff auf die Menge der reellen Zahlen ergänzen.



Deine Vermutung im letzten Beitrag also...


> In obigem Sinn ja, allerdings macht der Algorithmus etwas anderes als man umgangssprachlich erwarten würde: er "berechnet" nicht die Zahl Pi, sondern für gegebenes k die ersten k Dezimalziffern.
> (...)
> wohl war, wenn man "berechenbare reelle Zahl" so definiert wie oben gesagt


...ist richtig, den 'im obigen Sinne' bezeichnet genau den Sinn, den Turing ursprünglich beabsichtigte, und dann so definiert hat, und der genau so auch gelehrt wird.



> oder sag mir mal ganz konkret eine wirklich nachprüfbare falsche Aussage von mir in diesem Thread



Hier ein paar Aussagen von dir:


> (allein um eine einzige reelle zahl zu speichern bräuchte der "unendlich" viel RAM)


...müsste ergänzt werden zu: um eine einzige reelle Zahl in ihrer Dezimaldarstellung, also in Form der Aneinanderreihung der Koeffizienten der gegen sie konvergierenden Potenzreihe (für die Dezimalbruchentwicklung mit z=1/10) hinzuschreiben, bräuchte man "unendlich" viel RAM. Wählt aber man eine andere Potenzreihe als diese (mit demselben Wert), so kann man z.B. bei Wurzeln/Sinussen/e/ln/... einfach ein einfaches auf rationalen Zahlen arbeitendes Bildungsgesetz derer sämtlichen Koeffizienten angeben, speichern und damit auch weiterarbeiten. Also braucht man dafür nur endlich viel RAM.



> kein Mensch würde dafür überhaupt das Wort "Algorithmus" verwenden


'Algorithmus' hat mehrere Definitionen, und diese unterscheiden sich zum Teil sehr stark im Umfang dessen, was sie als Algorithmus durchgehen lassen. Der 'weiteste' Begriff ist sicherlich die Beschreibung einer Turingmaschine als Algorithmusbeschreibung zu sehen. Dann ist selbst das einfache Hinschreiben der Zahl '2' ein Algorithmus, wie jedes andere denkbare und beliebig komplizierte IO-Verfahren auch. Letztere Definition haben wir innerhalb einer Vorlesung genutzt (in einer anderen eine andere Definition, welche den Vorteil hat, dass dann nicht einfach jedes Verfahren ein Algorithmus ist, aber den Nachteil, dass die Grenze immer schwammig ist). Deine Aussage ist somit aber inkorrekt. Das ist wie mit N. Manche Profs nutzen die Definition 0 ist in N, andere die Definition, 0 ist nicht in N. 

Diese beiden Aussagen waren nur 2 Zeilen voneinander entfernt, gleich aus deinem nächsten Beitrag stammt diese:



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


Wie zwei Beiträge vorher von mir schon erwähnt: beliebig genau berechnen (hier im Sinne: die Dezimalstellen ausgeben) bedeutet, mit beliebig starker, aber endlicher Näherung zu berechnen. Dafür sind Algorithmen bekannt. (Und abgesehen davon: daher ist die entsprechende Zahl als berechenbar definiert.)

Soweit dazu.

Jetzt versuche ich nochmal mit folgendem aufzuräumen:


> Und um zum ursprünglichen Fibonacci-Problem zurückzukehren: sqrt(5) ist "berechenbar" - egal was das heisst - kann in diesem Fall sqrt(5) INNERHALB einer Berechnungsvorschrift (=Algorithmus, Programm) vorkommen???
> (...)
> Dieser Wert kann überhaupt nicht in irgendeiner Rechenmaschine "dargestellt werden", also kannst IMHO nicht sagen, dass es eine Maschine gibt, die diesen Wert "berechnet"



Durch die geeignete Wahl der Darstellung (insbesondere nicht als Dezimalzahl, also als Folge der Koeffizienten... (s.o.)), lässt sich sqrt(5) - wie auch zig andere irrationale Zahlen - zu 100%, absolut ohne Informationsverlust, binär codiert in einem Rechner speichern, indem man entweder einfach 'sqrt(5)' speichert (womit man noch nicht soo gut rechnen kann, ausser z.B. sqrt(5) * sqrt(45) = sqrt(225) = 15, was nun schon möglich ist), oder aber indem man für andere Berechnungen auf geeignetere Darstellungen zurückgreift, wo die Koeffizienten der Potenzreihe einem klaren Bildungsgesetz unterliegen. Dann kann man diese Reihen z.B. zusammenaddieren, die Brüche erweitern, kürzen, Teleskopsummen bilden, kreuz und quer hin und herrechnen (alles automatisiert), und gelangt dann auf mehr oder weniger schöne Ausdrücke als Ergebnis, welche wiederum stellvertretend für den exakten Wert des Ergebnisses stehen.


> Du freust dich nur deshalb, weil zufällig PI zum Alphabet deiner Symbol-Manipulations-Maschine gehört, über die allermeisten Wörter, die von dieser Maschine ausgespuckt werden würdest du dich wohl nicht freuen!


Es kommt auf den Zweck an. Wenn ich in Spielen irgendwelche Koordinaten zu berechnen wünsche, dann brauche ich diese Genauigkeit nicht, und mir reichen die schnell zu berechnenden Fliesskomma-Näherungen. Aber in vielen anderen Anwendungen der Mathematik bringt es einem Mathematiker viiiell mehr, einen auch komplizierten Ausdruck zu erhalten, als irgendeine wertlose Dezimalzahl - selbst wenn der Ausdruck sehr kompliziert ist. Man sieht dann darin z.B. Parallelen zu anderen Ausdrücken, etc. Auch kann es nur so passieren, das man z.B. als Ergebnis eine natürliche Zahl erhält, und _weiss_, dass diese das exakte Ergebnis ist.
Bei weitem nicht alle berechenbare Zahlen haben schließlich so ein einfaches Bildungsgesetz wie PI, sqrt, ln, e, etc., aber trotzdem können sie in Computern gespeichert und verarbeitet werden. 
Da der Mensch aber oft auch eine Vorstellung von der Größe der Zahl wünscht, rechnet er dann noch anhand dieser Formel eine Näherung in Dezimaldarstellung aus, und kann dann fröhlich seine Ordnungsrelation anwenden.

MuPad, Maple, Mathematica, etc. können mit sämtlichen berechenbaren Zahlen rechnen.

(btw: ich bin ganz locker :wink: Das ist nur das generelle Foren-Problem, dass man seinen Worten so schlecht und mißverständlich einen eindeutigen Unterton zuordnen kann.)


----------



## Bleiglanz (21. Mrz 2005)

kopfsalat hat gesagt.:
			
		

> > (...)dann schreib bitte vorher auf, was du unter "berechenbarer reeller Zahl" verstehen willst.
> 
> 
> Na, dass hier:
> ...


Warum sagst du das nicht gleich


> > oder sag mir mal ganz konkret eine wirklich nachprüfbare falsche Aussage von mir in diesem Thread
> 
> 
> 
> ...


Das ist jetzt wirklich Käse, natürlich habe ich nicht Zahlen wie 0,1 oder 2 gemeint 

Dein Einwand ist wie IMHO nicht korrekt, denn eine "Darstellung" einer reellen Zahl innerhalb eines Rechners als "symbolische Formel -Bildungsgesetz- für die Koeffizienten" ist ja nichts anderes, als eine etwas umgeschriebene Turingmschine (d.h. du speicherst _den Algorithmus_ von dem oben die Rede war)

Was ich meinte ist der WERT einer irrationalen reellen Zahl..., aber wenn du meinst, dass

"Wert einer reellen Zahl" == "formale Repräsentation einer Turingmaschine, die für gegebenen Input k die ersten k Ziffern berechnet

ist meine Aussage wohl falsch



> > kein Mensch würde dafür überhaupt das Wort "Algorithmus" verwenden
> 
> 
> 'Algorithmus' hat mehrere Definitionen, und diese unterscheiden sich zum Teil sehr stark im Umfang dessen, was sie als Algorithmus durchgehen lassen. Der 'weiteste' Begriff ist sicherlich die Beschreibung einer Turingmaschine als Algorithmusbeschreibung zu sehen. Dann ist selbst das einfache Hinschreiben der Zahl '2' ein Algorithmus, wie jedes andere denkbare und beliebig komplizierte IO-Verfahren auch. Letztere Definition haben wir innerhalb einer Vorlesung genutzt (in einer anderen eine andere Definition, welche den Vorteil hat, dass dann nicht einfach jedes Verfahren ein Algorithmus ist, aber den Nachteil, dass die Grenze immer schwammig ist). Deine Aussage ist somit aber inkorrekt. Das ist wie mit N. Manche Profs nutzen die Definition 0 ist in N, andere die Definition, 0 ist nicht in N.


Oh man, lies dir mal den Kontext durch?! Diese Aussage war natürlich falsch, weil ja in diesem Thread jemand unterwegs ist, der "dafür" das Wort Algorithmus verwendet!




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


jo, gut dass das jetzt geklärt ist: "beliebig genau" heisst für jedes gegebene FESTE k die ersten k Dezimalziffern berechnen zu können





> Jetzt versuche ich nochmal mit folgendem aufzuräumen:
> 
> 
> > Und um zum ursprünglichen Fibonacci-Problem zurückzukehren: sqrt(5) ist "berechenbar" - egal was das heisst - kann in diesem Fall sqrt(5) INNERHALB einer Berechnungsvorschrift (=Algorithmus, Programm) vorkommen???
> ...


typischer Fall von Verwechslung: wir reden die ganze Zeit von sqrt(5) und jetzt fängst du wieder mit dem String "sqrt(5)" an.



> MuPad, Maple, Mathematica, etc. können mit sämtlichen berechenbaren Zahlen rechnen.


Die können sogar VIEL mehr, nämlich mit ALLLEN reellen Zahlen rechnen, denn ist x obige konkret von Turing vorgelegte nicht berechenbare reele zahl (oder einfach nur IRGENDEINE reelle Zahl), dann können Mupad, Maple und Mathematika ohne Probleme

sin(x), cos(x), sqrt(x) 

"berechnen", in dem sie einfach diese strings ausspucken...

Das ist vermutlich einfach eine Geschmackfrage, meiner Meinung nach kann Maple nämlich überhaupt nicht mit Zahlen rechnen [wenn man von der Numerik mal absieht...], und wenn Maple auf seinem Bildschirm nach dem Prompt den String

"sqrt(5)"

ausgibt, dann hat Maple in meinen Augen nicht die Zahl sqrt(5) berechnet,,,,

locker bleiben!


----------



## kopfsalat (21. Mrz 2005)

Ahoi, ich bins nochmal, allerdings habe ich nicht viel Zeit, da ich gleich für eine Woche ins schöne Konstanz fahre!



> typischer Fall von Verwechslung: wir reden die ganze Zeit von sqrt(5) und jetzt fängst du wieder mit dem String "sqrt(5)" an.



Das meinte ich mit Trennung von einer Zahl selbst und ihrer Darstellung.

Jede Art und Weise, eine Zahl irgendwie graphisch zu veranschaulichen, ist eine symbolische Darstellung.
Eine Zeichenkette, wie 2 oder 3,234 oder 0x124 oder 0110101001110011010101100 oder 23^3 oder sqrt(5) oder PI oder eine Potenzreihe mit bestimmten Koeffizienten oder ein beliebiger Ausdruck kann eine Zahl darstellen.
Für das Rechnen damit braucht man dann ein umfangreiches Sammelsurium an äquivalenten Ersetzungen, so wie z.B. das kleine Einmaleins eines zusammen mit z.B. dem Stellenwertsystem eines ist, aber auch die Umwandlung von PI in eine geeignete äquivalente Potenzreihe.
Jeder Rechenschritt, auch 1+1=2, ist eine symbolische Termersetzung. Die Semantik dahinter jedoch liefert uns Zusammenhänge zwischen Zahlen, die wir nun mal völlig losgelöst von ihrer Darstellung annehmen. 1+1=2 bezeichnet dasselbe wie z.B. *?*_** oder auch add(sqrt(1), pow(13,0)) = sqrt(4)

Ich verstehe nicht, warum deiner Auffassung nach eine Turingmaschine mit der Zahl 5 rechnen kann, aber mit sqrt(5) nicht ?

Eine Turingmaschine arbeitet doch immer nur auf symbolischen Darstellungen einer Zahl (selbst unäre Codierung ist nur eine Darstellung), und nutzt für verschiedene Codierungen verschiedene Verfahren.
Wenn eine Turingmaschine nicht mit dem zur Zeichenkette 'sqrt(5)' gehörenden Zahlen_wert_ rechnen kann, dann kann sie es auch nicht mit der zur Zeichenkette '3' oder '4.5' gehörenden Zahlen_wert_.
Andererseits:
Wenn man es so sehen möchte, dass eine Turingmaschine mit dem Wert der Zahl '3' oder '4.5' rechnen kann, dann kann sie es auch mit 'sqrt(5)'.

Dein Einwand, dass Turingmaschinen dann mit ALLEN reellen Zahlen rechnen können ist interessant!
Natürlich könnte man sagen X, Y seien jeweils eine nicht-berechenbare Zahl, und Z = X+Y.
Dann könnte man sagen, man kann damit rechnen ? (Definitionssache)
(Es könnte sogar sein, dass Z eine natürliche Zahl ist !)
Allerdings ist das ziemlich 'pathologisch'. Im Gegensatz zu allen anderen Zahlen kann man die nicht-berechenbaren ja nicht in einen äquivalenten arithmetischen Ausdruck wandeln, und daher nicht im 'klassischen Sinne' damit 'rechnen'. (was immer das genau ist)
Für eine exakte Beschreibung einer nicht-berechenbaren Zahl, anhand derer man sie mit anderen bekannten Zahlen verknüpfen kann und ggf. die Ausdrücke danach vereinfachen, bräuchte man tatsächlich unendlich viel Platz.
Aber: von mir aus können _wir_ das gerne so definieren. :wink: 

(timeout)

Whoops, ich muss gleich los. Meine nächste Antwort kann etwas dauern, ich weiß nicht, wie es da mit Internet aussieht.
Hau rein + bis denne!
kopfsalat


----------



## Bleiglanz (22. Mrz 2005)

> Ich verstehe nicht, warum deiner Auffassung nach eine Turingmaschine mit der Zahl 5 rechnen kann, aber mit sqrt(5) nicht ?


Weil sqrt(5) für einen Rechner (und auch für Menschen?) ein undurchschaubares Mysterium ist; das ist ja in Wahrheit nur eine operative Definition ("ziehe die Quadratwurzel aus der Zahl 5"); das Ergebnis - der "Wert" von sqrt(5) , die reelle Zahl, die mit sich selbst multipliziert 5 ergibt - kann aber von Computern/Menschen/usw. nicht "erfasst" oder "gewusst" oder was auch immer werden.

Du kannst natürlich - um von der Turingmaschinen-Sprechweise zur Grammatik-Sprechweise zu wechseln - eine Sprache angeben, zu deren Elementarsymbolen "sqrt" gehört; das ist aber dann ganz was anderes!

Sagen wir die Ziffern von 0-9 gehören zu deinen Elementarsymbolen, dann ist alles unproblematisch, weil dann die Common-Sense-Interpretation 

"123" ist die Zahl 123 

problemlos funktioniert (nur in diesem Sinn kann eine Turingmaschine mit den natürlichen Zahlen rechnen): Die Interpretation "1" ist 1, "2" ist 2 usw. funktioniert und alles ist schön endlich...

Um mein Statement mal anders zu formulieren:

Es gibt keine Turingmaschine, die mit sqrt(5) rechnen kann, aber man kann eine bauen, die mit "sqrt(5)" rechnen kann


----------



## kopfsalat (27. Mrz 2005)

@Bleiglanz (und auch @ll)...
Hi, bin wieder zurück (s.o. - und es gab kein (!) Internet dort),



> Es gibt keine Turingmaschine, die mit sqrt(5) rechnen kann, aber man kann eine bauen, die mit "sqrt(5)" rechnen kann


Langsam wird es philosophisch. :wink: 

Als Elementarsymbole habe ich nicht die Ziffern 0,..,9 gesehen, sondern nur 0 und 1.
Dann sind Ganzzahlen/Fließkommazahlen/Brüche auch nur Bitstring-Codierungen (Integer-Zweierkomplement, IEEE-float, etc.) zusammen mit darauf definierten Operationen +-*/, etc. Dann hat man doch sowas wie eine Algebra und das heißt dann ja, dass man damit 'Rechnen' kann. (Mit 'damit' meine ich hier mit z.B. dem Wert 5 selbst)

Wenn man nun eine andere geeignete in sich abgeschlossene und semantisch korrekte Codierung nutzt, welche z.B. noch weit mehr umfasst, und dafür dann Operationen +-*/ etc. darauf definiert, dann hat man doch ebenfalls sowas wie eine Algebra und kann damit meiner Auffassung nach 'Rechnen'. (Mit 'damit' wäre dann hier sowas wie der Wert von sqrt(5) selbst gemeint).

Aber ich weiss nicht genau, wie man 'Rechnen' allgemeinhin definiert (wird aber ggf. auch Stoff von 'Einführung in die Algebra' nächstes Semester sein).

Allerdings vermute ich, dass 'Rechnen' _immer_ auf irgendeine symbolische Abstraktion angewiesen ist, auf deren Ebene dann symbolische Operationen definiert sind, deren Interpretation 'korrekte' Ergebnisse liefert. Daher sehe ich keinen Unterschied zwischen "Rechnen mit "5"" und "Rechnen mit "sqrt(5)""

Vielleicht ist dies hier der Kern davon (?):
Ich finde es richtig, zu sagen: Eine Turingmaschine kann mit sämtlichen berechenbaren Zahlen 'rechnen'.
Du hingegen meinst: Eine Turingmaschine kann nur mit den rationalen Zahlen 'rechnen' (also den berechenbaren Zahlen ohne die irrationalen) ?

Ich werd mich da schonmal auf die Suche nach einer Antwort machen.  ???:L  :###


----------

