Fibonacci overflow integer

[Daelerion]

Hey Leute 🙂

Meine Aufgabe ist es die n-te Stelle der Fibonacci Zahl zurückzugeben. Und das mit einem normalen Integer.

Wenn der Integer overflowt dann soll ich lediglich "-1" zurückgeben.


Mein bisheriger Code ist

public int fibonacci(int n) {
        
        int fib1 = 0;
        int fib2 = 1;
        int fib3 = 0;
        
        
            
        for (int i=1; i<n ; i++) {
            fib3=fib1 + fib2;
            fib1 = fib2;
            fib2 = fib3;
            
            if (fib2 > Integer.MAX_VALUE){
                fib2 = -1;
                break;
                
                
            }
            
          
        }
         return fib2;
        }

grade testet es mit mehreren Variablen durch und mir wird gesagt,
wenn ein zu hoher n-Wert angegeben wird und der Int overflowt dann wird keine(!) "-1"! zurückgegeben.
Was übersehe ich denn ?

 

[lennero]

if (fib2 > Integer.MAX_VALUE){

Was genau prüfst du hier?

 

[Daelerion]

Was genau prüfst du hier?

Ich versuche damit zu überprüfen ob das Ergebnis über dem Int max wert liegt, also overflowt.

Wenn der Integer overflowt dann soll ich lediglich "-1" zurückgeben.

 

[kneitzel]

Ein Integer kann nie größer sein als Integer.MAX_VALUE.

Was kommt denn raus, wenn Du fib3=fib1 + fib2; rechnest und es zu dem Overflow kommt?

Was für einen Wert hat fib3 beim Overflow?

Edit: Prüf doch sonst einfach einmal, was int test = Integer.MAX_VALUE + 1; ergibt. Dann musst Du nicht den Overflow ausprobieren bei Deinem Code....

 

[Daelerion]

Edit: Prüf doch sonst einfach einmal, was int test = Integer.MAX_VALUE + 1; ergibt. Dann musst Du nicht den Overflow ausprobieren bei Deinem Code....

Oh. Ja du hast Recht, bin ich doof. MAX + 1 = MIN value. Okay gut habe es gelöst indem ich die fib zu long gemacht habe :

public int fibonacci(int n) {
        
        long fib1 = 0;
        long fib2 = 1;
        long fib3 = 0;
        
        
        
            
        for (int i=1; i<n ; i++) {
            fib3=fib1 + fib2;
            fib1 = fib2;
            fib2 = fib3;
            
            if (fib2 > Integer.MAX_VALUE){
                fib2 = -1;
                break;
                
                
            }
            
          
        }
        int erg = (int)fib2;
         return erg;
        }
        
        
      
        
        
    }

Somit habe ich einen Int als Ausgabe, was Teild er Aufgabe ist, das hat mich whol zu sehr beschäftigt, dass ich nicht daran gedacht habe ein long zu nehmen um den Wert zu errechnen.
Danke dir !

 

[httpdigest]

überlege mal, wie du die Prüfung machen kannst, ohne long oder einen anderen Datentyp als int zu verwenden.

 

[kneitzel]

Wenn du die fib(n) mit fib(n+1) vergleichst: was kannst du dann sagen bezüglich der Größe? Was gilt da?

Und gilt das auch, wenn es zu dem Überlauf gekommen ist?

 

[Daelerion]

Oh also könnte ich theoretisch einfach prüfen, ob der int negativ ist, also

if (fib2 < 0){
fib2=-1;

}

Da ja wenn er overflowt ins negative geht. Somit brauche ich dort kein long

 

[Daelerion]

 public int fibonacci(int n) {
        
        int fib1 = 0;
        int fib2 = 1;
        int fib3 = 0;
        
        
        
            
        for (int i=1; i<n ; i++) {
            fib3=fib1 + fib2;
            fib1 = fib2;
            fib2 = fib3;
            
            if (fib2 < 0){
                fib2 = -1;
                break;
                
                
            }
            
          
        }
        
         return fib2;
        }

Ist somit mein Endergebnis, ohne loong zu verwenden 🙂
Danke für die Hinweise