Fibonacci Folge negativ?

Code:

---

#include <iostream>
#include <Windows.h>

using namespace std;

int main()
{
unsigned__int64 zahl1 = 0;
unsigned__int64 zahl2 = 1;
int i = 0;
cout << zahl1 << endl << zahl2 << endl;
do
{
unsigned__int64 ausgabe= zahl1+zahl2;
cout << ausgabe << endl;
zahl1 = zahl2;
zahl2 = ausgabe;
i++;
}while(i<80);

system ("pause"); \\ @mog: Ich mag aber die Pausefunktion :o
return 0;
}

---

0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
-1323752223
512559680
-811192543
-298632863
-1109825406

Ich hab mal versucht die FibonacciFolge in C++ iterativ auszudrücken.
Allerdings kommt es, dass sie ab der 47. Stelle eine negative Zahl herauskommt. Dabei addiert der Code doch nur 2 positive Zahlen, wie kann da eine negative Zahl herauskommen?!
Der Witz ist auch, dass sie anscheinend bis zu46. Stelle noch stimmt.

Könnte mir jemand zeigen, was am Code falsch ist?

Der Code ist wohl richtig aber es findet an der Stelle ein Überlauf statt, da das Ergebnis ein int ist. d.h. das höchstwertige Bit ist zuständig für das Vorzeichen und ab der Stelle, wo die erste negative Zahl vorkommt, wird das höchstwertige Bit auf 1 gesetzt und somit ist die Zahl negativ

Zitat:

---

Zitat von Whiz-zarD

Der Code ist wohl richtig aber es findet an der Stelle ein Überlauf statt, da das Ergebnis ein int ist. d.h. das höchstwertige Bit ist zuständig für das Vorzeichen und ab der Stelle, wo die erste negative Zahl vorkommt, wird das höchstwertige Bit auf 1 gesetzt und somit ist die Zahl negativ

---

Das heißt ich sollte long statt int verwenden?
EDIT:
Meh. Das funktioniert leider auch nicht.

Muss es nicht eig.:

Code (CPP):

#include <iostream>
#include <windows.h>
#include <winbase.h>
 

heißen?

Sonst müsstest du ja jedes mal alle Header Dateien in dein Working-Directory kopieren.

Dein Problem kannst du beheben in dem du den Integer-Variablen den Minus-Bereich raubst:

Code (CPP):

unsigned int zahl1 = 0;
unsigned int zahl2 = 1;
[...]
unsigned int ausgabe= zahl1+zahl2;
 

/edit: long ist in 32Bit Systemen genauso groß wie ein int nämlich 4 Byte.

Zitat:

---

/edit: long ist in 32Bit Systemen genauso groß wie ein int nämlich 32Bit.

---

Hab aber 64 Bit^^

Und mit long long funktioniert es Oo
Mit unsigned int auch

EDIT:

Nein, mit unsigned int geht es auch nur bis zur 48ten. Dann kommt wieder eine kleiner Zahl, die nicht in die Folge passt.
Also bräuchte ich nur ein usigned long oder (unsigned) long long

Okay, hab das Problem jetzt verstanden, es liegt am Variablentyp^^

Zitat:

---

Zitat von Mivey

Das heißt ich sollte long statt int verwenden?
EDIT:
Meh. Das funktioniert leider auch nicht.

---

unsigned long long int sollte das Problem beheben.
Der geht bis 18.446.744.073.709.551.615 und ist 8 Bytes groß.

Zitat:

---

Der geht bis 18.446.744.073.709.551.615 und ist 8 Bytes groß.

---

Weil eine long long Variable 2 ^ 64 Bit haben darf?

Nein, 64 Bit und damit 2 ^ 64 Werte. 2 ^ 64 Bit wären ein bisschen arg viel.

mmh, ich glaub, du solltest dich mal mit Bits, Bytes und vorallem mit den Datentypen von C auseinandersetzen.

2 ^ 64 Bits wären 2 Zebibyte (wenn ich richtig gerechnet habe). Also eine Speichergröße enormer Ausmaßen, die wir wohl in unseren Lebzeiten nie erreichen werden ... denke ich aber Bill Gates hat sich ja auch mal enorm verschätzt ^^

Wir sind momentan bei etwa 16 GiB RAM für Serversysteme, das sind, wenn ich mich jetzt im Kopf nicht verrechnet habe, 2^37 Bit. Nach dem Mooreschen Gesetz, sofern es seine Gültigkeit behält, würden wir die 2^64 Bit in 45 bis 60 Jahren erreichen und das gedenke ich doch noch mitzuerleben.

Zitat:

---

Zitat von DFYX

Nein, 64 Bit und damit 2 ^ 64 Werte. 2 ^ 64 Bit wären ein bisschen arg viel.

---

Ja ein Denkfehler von mir. xD
8 Byte sind ja 8 mal 8 bit also 64 Bit, was einen Wert von 2 ^ 64 als Ziffer hat, hab ich jetzt verstanden
EDIT:
Aber eine Frage die sich mir anbei stellt: Wie wäre es möglich Ziffern darzustellen die größer als 2^64 sind? Muss man dafür mehrere Variablen nehmen und wie ließe sich sowas realisieren?

Es gibt dazu Implementationen von sogenannten Big Integer, gibt es glaube ich in Java nativ. Sonst kann man auch Float/double nehmen, wenn man mit der Ungenauigkeit leben kann.
Big Integer funktionieren in etwa so, dass du z.B. für jede Ziffer ein char nimmst und dann dich zurück in die Primarschule besinnst und dann alle Operationen selber implementierst. "Schriftlich" Addieren etc.

@Whiz-zarD:
2 Exbibyte meinst du ;)

@Mivey:
Vielleicht waere das interessant fuer dich. Habe ich zwar noch nie benutzt, aber ich denke das passt irgendwie zum Thema.

Soll kein 'Echopost' sein, habe nur vergessen abzuschicken -.-

Zitat:

---

Zitat von Drakes

Sonst kann man auch Float/double nehmen, wenn man mit der Ungenauigkeit leben kann.

---

Da hat man aber das Problem der Implementierung und der Einstellung des Compilers. z.B. der MMX Befehlssatz rechnet mit 64 Bits Genauigkeit, während der 387 Co-Prozessor mit einer Genauigkeit von 80 Bits rechnet und 64 Bit-Genauigkeit ausgibt.

Zitat:

---

Zitat von Brauni90

@Whiz-zarD:
2 Exbibyte meinst du ;)

---

Dann hab ich mich da irgendwo vertan ^^"

Zitat:

---

Zitat von Mivey

Aber eine Frage die sich mir anbei stellt: Wie wäre es möglich Ziffern darzustellen die größer als 2^64 sind? Muss man dafür mehrere Variablen nehmen und wie ließe sich sowas realisieren?

---

Irgendwann stößt du so oder so an die Grenzen des Machbaren. Was war noch gleich die größte Zahl die mit IEEE-754 machbar war? (irgendwas mit 20 Dezimalstellen oder so)
Jedenfalls wirst du nicht "unendlich" große Zahlen berechnen können.

Naja, wenn er seinen kompletten Arbeitsspeicher voll macht, kann er zumindest schonmal sehr große Zahlen speichern. Es gibt wesentlich mehr auf der Welt als nur unsigned long long int und IEEE-754.

Zitat:

---

Zitat von DFYX

Naja, wenn er seinen kompletten Arbeitsspeicher voll macht, kann er zumindest schonmal sehr große Zahlen speichern. Es gibt wesentlich mehr auf der Welt als nur unsigned long long int und IEEE-754.

---

Das will ich genauer wissen! Link oder so :)

Ein Beispiel wäre BigInteger, was Brauni90 ja schon gepostet hat. Das Konzept ist ganz leicht, auch wenn es mehrere unterschiedliche Ansätze gibt, die aber sehr ähnlich sind. Entweder du legst die Zahlen in Textform als Strings ab (dann kannst du sogar beliebig genaue Kommazahlen darstellen) oder als Byte-Array. Letzteres ist dann effektiv das gleiche, als hättest du normale long long long ... long ints. Theoretisch gehen Binary Coded Decimals auch, aber die sind beim Rechnen etwas unhandlich.

In beiden Fällen musst du natürlich alle Rechenoperationen selbst implementieren. Allerdings ist das gar nicht mal so schwer. Funktioniert wie schriftliches Rechnen in der Grundschule. Bei Addition und Subtraktion betrachtest du einfach jeweils ein Byte als eine Ziffer, verwendest die normalen Rechenoperationen und achtest auf den Übertrag. Zur Multiplikation empfehle ich das erste Kapitel von Prof. Peter Sanders' Algorithms and data structures: the basic toolbox (Google Books Link, das Kapitel kann man direkt online lesen) Wenn Bedarf besteht, kann ich dazu auch noch die Vorlesungsfolien raussuchen. Ich hatte das Glück, Algorithmen I bei Prof. Sanders zu haben. Der Mann ist wirklich kompetent.

Die Division könnte etwas schwieriger werden, ist aber auf jeden Fall auch machbar, solang man ausreichend Speicher hat.

Das hört sich verdammt intressant an o.o Werd mich mal jetzt gleich damit beschäftigen. Vom Vorlesungsstand bei mir hätte ich ehrlich gesagt selbst drauf kommen müssen (Ich sollte wohl mal wieder nacharbeiten).
Dabei nutze ich das Konzept auch um mehrere Werte in einem Int zu lagern .__.°

Dank Dir!

Erwarte aber nicht, dass deine Softwareimplementierung schnell sein wird. Besonders hinter Multiplikation und Division verbergen sich eine Unzahl an Rechenschritten, die in Software gelöst - je nach Größe der Zahl - viel Rechenleistung beanspruchen können. Theoretisch mag der Arbeitsspeicher das Limit darstellen, praktisch ist es aber die Laufzeit, denn du wirst kaum Wochen, Monate, oder mehr auf eine Berechnung warten wollen.

BCD-Arithmetik und Konsorten werden in der Regel nur im wissenschaftlichen, oder kaufmännischen Bereich benötigt. Außerhalb dieser Bereiche ist höchstens interessant zu wissen, dass es sowas gibt, oder wie es in der Theorie funktioniert, mehr nicht.

Mach doch mal die unnoetigen Header, und die Pause heraus ....

Für Fibonacci braucht man ja nicht viele Rechenarten... Haben wir damals im Programmieren-Kurs als Übung auch implementieren müssen, rauszufinden, wann die Fibonacci-Zaheln 80-stellig werden. Einfach die Zahlen als Byte-Array und die Addition dafür implementieren, ziemlich easy.

Zitat:

---

Zitat von Irian

Für Fibonacci braucht man ja nicht viele Rechenarten...

---

Die Fibonacci-Reihenfolge ist auch mehr ein Rekursives Problem, als ein Iteratives.
Per Rekursion wäre der Algorithmus ein zwei-Zeiler.

Zitat:

---

Zitat von Whiz-zarD

Per Rekursion wäre der Algorithmus ein zwei-Zeiler.

---

Und ein Speicherkiller. Bedenke, dass für jeden Rekursionsschritt neuer Speicher reserviert wird, der erst wieder freigegeben wird, wenn alle danach gestarteten Rekursionsschritte wieder beendet wurden. Grade, wenn man mit BigInteger arbeitet, wird das schnell böse.

Zitat:

---

Zitat von Whiz-zarD

Die Fibonacci-Reihenfolge ist auch mehr ein Rekursives Problem, als ein Iteratives.
Per Rekursion wäre der Algorithmus ein zwei-Zeiler.

---

Hatten das grad am Diesntag, Das Problem rekursiv zu bearbeiten ist echt ne Killer selbst für Großrechner (auf dem wir das probiert haben). Iterativ wäre hier echt besser, das dauert das keine Sekunde.

Edit:
Arg, jetzt erst seh ich dein Post DFYX >.<
Also Dito 8'D

Zitat:

---

Zitat von DFYX

Und ein Speicherkiller. Bedenke, dass für jeden Rekursionsschritt neuer Speicher reserviert wird, der erst wieder freigegeben wird, wenn alle danach gestarteten Rekursionsschritte wieder beendet wurden. Grade, wenn man mit BigInteger arbeitet, wird das schnell böse.

---

Sicherlich.
Dennoch ist und bleibt die Fibonacci-Folge ein Rekursives Gesetz. Obs nun besser wäre oder nicht, sei mal dahingestellt.

Das selbe trifft auch beim Floodfill-Algorithmus (Zum Füllen von Flächen) zu. Rekursiv nur ein paar Zeilen aber die Rekursionstiefe ist so enorm, dass selbst aktuelle Maschinen bei einem Bild von 500x500 Pixeln in die Knie gehen.

Das war so ne Falle in meiner Algorithmen&Datenstrukturen-Prüfung... Eine (versteckte) Fibonacci-Reihe möglichst schnell zu berechnen. Die Reihe mag ja rekursiv definiert sein, aber sie am Computer rekursiv zu berechnen ist so ziemlich die schlechteste Methode - nicht nur weil mehr Speicher gebraucht wird, sondern auch, weil diverse Schritte sehr oft wiederholt werden müssen. Typische Gefahr bei der Rekursion, es ist oft die eleganteste Möglichkeit, etwas zu definieren, aber nicht notwendigerweise die beste, ums zu implementieren.

Iterativ ist etwas besser, da steigt die Rechenzeit wenigstens nur linear an. So haben wir das damals in Programmieren gemacht.

Für die ganz ungeduldigen gibts auch einfach die Formel von Moivre-Binet :-)