Größte darstellbare Zahl

dprzon schrieb:

for(unsigned int i = sizeof(zahl)*8; i; i--)
  if(zahl & (1 << i)) {
    printf("Höhstes Bit ist %u\n",i);
    break;
  }

Das ist falsch. Du darfst bei einem x-Bit Typ nicht um x Bit schieben, sondern nur um x-1 Bit.

Und ja, Vertexwahn meinte bestimmt limits.h.

Taurin

Iterativ ist hier tatsächlich einfacher.
Überleg dir, was nach einem Überlauf passiert. Wie kannst du das überprüfen? Mit bits herumschubsen geht das bestimmt auch, aber einfacher wird dadurch bestimmt nicht.

dprzon

Stimmt, das mit der Schleife ist echt komisch...

Iterativ sieht es ja so aus, oder?

unsigned int fibonacci(int n)
{ int x=1, y = 1, i, sum;

    y = sum; }
  return y;
}

Nach einem Überlauf fängt er ja wieder erneut an oder?

Taurin

Nö, die Anzahl deiner Schleifendurchläufe hängt nur von i und n ab, und da läuft nix über. Oder was meinst du mit "neu anfangen"?
Welche Variable wird denn überlaufen, wenn dein n zu groß ist?

dprzon

y wird ja überlaufen. Und das ist nicht iterativ was ich gemacht hab eben ???

dprzon

Hab jetzt folgende Abfrage eingebaut in der for schleife:

if (y > UINT_MAX/i) [/b]
	  {
		printf("Fehler\n");
		return 0;
	  }

Jetzt habe ich die Bedingung geändert und eigentlich sieht jetzt alles gut aus bis auf eine "Kleinigkeit".

Meine neue Bedingung

if (sum > UINT_MAX-x)
      {
        printf("Fehler\n");
        return 0;
      }

Ab der Eingabe 47., also dass mir die 47. Fibonacci Zahl ausgegeben werden soll, kommt die Fehlermeldung. Also die letzte die ausgegeben werden kann, ist die 46.
Aber bei der Eingabe 46 kommt die Zahl -1323752223.
Warum kommt da eine negative??

Taurin

Erstmal: Klar, dein Programm ist iterativ (d.h. arbeitet mit einer Schleife)
Dann noch ein paar 'didaktische' Fragen:
Welchen Variablentyp hat sum? unsigned int oder int? Was passiert denn nach dem Überlauf?

dprzon

Taurin schrieb:

Erstmal: Klar, dein Programm ist iterativ (d.h. arbeitet mit einer Schleife)
Dann noch ein paar 'didaktische' Fragen:
Welchen Variablentyp hat sum? unsigned int oder int? Was passiert denn nach dem Überlauf?

unsigned int fibonacci(int n)
{ unsigned int x=1, y=1, i, sum=0;

  for (i=2; i<=n; i++)
  {
	  if (sum > UINT_MAX-x)
	  {
		printf("Fehler\n");
		return 0;
	  }

	.
        .
        .

Beim Überlauf wird ja ein Überlaufbit gesetzt. Also ist die "negative" Zahl schon der Überlauf.

Warum gibt er nicht schon da den Fehler aus?

**EDIT:
Ich glaube bzw. hoffe, dass ich den Teufel nach dem ganzen Rumprobieren heute gefunden habe...

Und zwar habe ich INT_MAX statt UINT_MAX in der Abfrage genommen. Jetzt wird der Fehler schon ab der Eingabe 47 ausgegeben.

**
Ist jetzt richtig so, oder?

Taurin

Das schaut doch ganz fein aus. Jetzt weißt du, für welche n deine Funktion funktioniert und für welche nicht. D.h. du brauchst deine Abfrage in der Schleife gar nicht mehr, sondern nur noch eine Abfrage *vor* der Schleife, ob du ein gültiges oder ein ungültiges n als Eingabe hast.

dprzon

Ja das stimmt schon. Muss es aber meinem Prof zeigen wie ich drauf gekommen bin...
Danke nochmal für die Tipps!