CODEWITHSUNDEEP
java
Parallelflux
Parallelflux

Reputation: 51

Unexpected behavior when modifying Fibonacci Sequence Generator

I have been toying around with my program for Exercise 4.10, from the Art and Science of Java Chapter 4 Exercise 10. Here's my code:

import acm.program.*;

public class FibonacciSequenceModified extends ConsoleProgram{

public void run(){

    println("This program will display the numbers of the fibonacci sequence that are less than " +
            "10,000");
    int total=0;
    int x=0;
    int y=1;
    println("F0= "+ x);
    println("F1= "+ y);
    for (int num=2; num<=100; num++){
        total=x+y;
        if (total<10000){
        println("F" + num +"= " +total);
        x=y;
        y=total;
        }
    }


}
}

This program will work and F20=6765 is its last line. However, if I modified the code so that the first curly brace "}" is now before x=y; instead of after y=total;, the program goes bonkers and will display huge negative numbers past F20=6765. Can anyone explain to me what the code is trying to do with this simple alteration?

Upvotes: 4

Views: 302

Answers (3)

rgettman
rgettman

Reputation: 178303

If you move the } before x=y;, then you are in effect continuing to determine Fibonacci numbers past number 20, but only printing them out if they are less than 10,000. This continues to work until the numbers get so big that they overflow the int datatype you're using to calculate the numbers. The largest int possible is 231 - 1, and the 47th number passes that value. The result is that some of them will be negative because of this overflow. Those negative numbers are less than 10,000 so they are printed.

This behavior is seen more clearly when the if and associated braces are removed completely:

This program will display the numbers of the fibonacci sequence that are less than 10,000

F0= 0
F1= 1
F2= 1
F3= 2
F4= 3
F5= 5
F6= 8
...
F18= 2584
F19= 4181
F20= 6765
F21= 10946
F22= 17711
...
F44= 701408733
F45= 1134903170
F46= 1836311903
F47= -1323752223  <= First negative resulting from overflow.
F48= 512559680
F49= -811192543
F50= -298632863
...
F98= -90618175
F99= -889489150
F100= -980107325

The reason the code as you have it worked is that you only determined the next number if the total is less than 10,000, so you never calculated enough numbers high enough to overflow. Loops where num is 22 and above did nothing.

Once the total is greater than 10,000, you can keep the } before x=y; if you break out of the loop.

if (total<10000){
    System.out.println("F" + num +"= " +total);
}
else
{
    break;
}
x=y;
y=total;

As an aside, note that changing the datatypes of total, x, and y to long helps, but it only postpones the problem. This will overflow a long at the 93rd term.

F90= 2880067194370816120
F91= 4660046610375530309
F92= 7540113804746346429
F93= -6246583658587674878
F94= 1293530146158671551
F95= -4953053512429003327
F96= -3659523366270331776
F97= -8612576878699335103
F98= 6174643828739884737
F99= -2437933049959450366
F100= 3736710778780434371

BigIntegers would be able to store these huge numbers precisely.

Upvotes: 2

Sam I am says Reinstate Monica
Sam I am says Reinstate Monica

Reputation: 31204

That curly brace represents the end of the if block, which is preventing your loop for counting Fibonacci numbers after 10000 has been reached. The reason it needs to do this is because Fibonacci numbers grow exponentially, and will eventually be too big for a simple 32 bit int to store.

What is happening is interger overflow. that means that your ints are so big that they can't fit in 32 bits.

as an example, consider the largest 32 bit signed integer: 2,147,483,647

01111111111111111111111111111111

if you add 1 to it, it would become this:

10000000000000000000000000000000

That is smallest negative intger: 2,147,483,648 . your numbers are going beyond that. That's why you're seeing negatives

if you keep "adding" to that, eventually, you'll end up at the following:

11111111111111111111111111111111

That's -1 in Two's compliment representation. if you add 1 to that, you'll get this

100000000000000000000000000000000

you might notice, that there are more than 32 bits there. The most significant bit(the 1) will get truncated, and we're back to 0.

00000000000000000000000000000000

your fibbonacci numbers keep over-shooting this 32 bit limit, since the most significant bits are left off, the remaining bits aren't very meaningful, and that's why you're seeing random-looking numbers.

Upvotes: 2

Olavi Mustanoja
Olavi Mustanoja

Reputation: 2065

If you have the following code

int total = 0;
int x = 0;
int y = 1;
System.out.println("F0= "+ x);
System.out.println("F1= "+ y);
for (int num = 2; num <= 100; num++){
    total = x + y;

    if (total < 10000) {
        System.out.println("F" + num +"= " +total);
    }

    x = y;
    y = total;
}

What is happening is, the program succesfully calculates the fibonacchi numbers up to F46, but prints only numbers up to F20 due to the statement if (total < 10000) . . . (tested in ideone.com). The 47th fibonacchi number exceeds the maximum value of int, thus returning garbage, which is often seen as a negative number. Your program prints all such garbage because it's less than 10,000. The maximum value for int is 2^31 - 1, which is about 2 billion.

Upvotes: 0

Related Questions