Error with Fibonacci code generation

This is a discussion on Error with Fibonacci code generation within the C++ Programming forums, part of the General Programming Boards category; While i compile and run the code, there's negative value that not suppose to be appear. Code: #include<conio.h> #include<stdio.h> int ...

  1. #1
    Registered User
    Join Date
    Oct 2009
    Posts
    3

    Error with Fibonacci code generation

    While i compile and run the code, there's negative value that not suppose to be appear.

    Code:
    #include<conio.h>
    #include<stdio.h>
    
    int n=0;
    Fib(int n);
    
    void main()
    {
    	clrscr();
    	int seriesSize = 35;
    	int looper;
    	printf("Print a Fibonacci series.\n");
    	for (looper=0;looper<seriesSize;looper++)
    	{	Fib(looper);
    	printf("%d",Fib(looper));
    	printf("\n");
    	}
    
    	getch();
    }
    
    Fib(int n)
    {
    	int x;
    	if (n==0)
    		x = 0;
    	else if (n==1)
    		x = 1;
    	else
    		x=Fib(int(n-1))+Fib(int(n-2));
    	return (x);
    }

    Any idea?

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Your integer type is probably too small. Check sizeof(int). Perhaps long would be more suitable: you'll need at least 4-byte integers, or perhaps use the double data type.

    Your code fixed for standard compliance:

    Code:
    //#include<conio.h>
    #include<stdio.h>
    
    int n=0;
    int Fib(int n);
    
    int /*void*/ main(void)
    {
        //clrscr();
        int seriesSize = 35;
        int looper;
        printf("Print a Fibonacci series.\n");
        for (looper=0;looper<seriesSize;looper++)
        {
            Fib(looper);
            printf("%d",Fib(looper));
            printf("\n");
        }
    
        //getch();
        return 0;
    }
    
    int Fib(int n)
    {
        int x;
        if (n==0)
            x = 0;
        else if (n==1)
            x = 1;
        else
            x=Fib(int(n-1))+Fib(int(n-2));
        return (x);
    }
    Although it is nice and recursive, it is a truly horrible way to compute these numbers performance-wise (computing the last two values takes visible time): if I'm not mistaken, the number of times it recurses for each number forms a fibonacci sequence of its own. For example, to calculate Fib(10), Fib(10) is called once, Fib(9) is called once, Fib(8) is called twice, Fib(7) is called 3 times, Fib(6) is called 5 times, Fib(5) 8 times etc. If I'm not mistaken it takes 9,227,464 iterations / function calls to calculate Fib(34) with this method. Compare that to looping 34 times!
    Last edited by anon; 10-03-2009 at 06:45 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Registered User
    Join Date
    Oct 2009
    Posts
    3
    Ok, now i've try assign long type to it, and a little formatting for it show nicely.
    But, stil no luck. The output still the same.(but the formatting works!!)

    Code:
    #include<conio.h>
    #include<stdio.h>
    
    int n=0;
    long Fib(int n);
    
    void main()
    {
    	clrscr();
    	int seriesSize = 35;
    	printf("Print a Fibonacci series.\n");
    	for (int looper=0;looper<seriesSize;looper++)
    	{
    		if (looper %5)
    			printf(", %8ld",Fib(looper));
    		else
    			printf("\n%8ld",Fib(looper));
    	}
    
    	getch();
    }
    
    long Fib(int n)
    {
    	int x;
    	if (n==0)
    		x = 0;
    	else if (n==1)
    		x = 1;
    	else
    		x=Fib(int(n-1))+Fib(int(n-2));
    	return (x);
    }
    And i haven't learn about double type. = =
    Am i mistaken?

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I'm afraid we can't reproduce the error, since it has to do with integer overflow which doesn't occur if the integer type is at least 4 bytes. You must have a 16-bit compiler with 2-byte int's and long's. The range of those is too small to represent the larger results.

    A double is a floating point type and it should have enough precision to represent the values in your program exactly. Just change all the longs into doubles and use the "%8.0f" format flag.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    Registered User
    Join Date
    Oct 2009
    Posts
    3
    I don't know whether my compiler is 16-bit based or not.
    I'm using an ancient Turbo C++, run on windows Vista 32bit, since it's used in my university (for years i think .)
    Any compiler suits me?

    ps: Still error with double type. I think the compiler's does matter.

  6. #6
    The larch
    Join Date
    May 2006
    Posts
    3,573
    This is how you can view the size of int (or any other type)

    Code:
    #include <stdio.h>
    
    int main(void)
    {
        printf("%d\n", sizeof(int));
        return 0;
    }
    Post your version with the double type. If you are still seeing negative numbers, it means you must be still using an int somewhere in the calculations.

    You could also complain that the compiler is too ancient for computing so big Fibonacci numbers.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Proposal: Code colouring
    By Perspective in forum A Brief History of Cprogramming.com
    Replies: 28
    Last Post: 05-14-2007, 08:23 AM
  2. Values changing without reason?
    By subtled in forum C Programming
    Replies: 2
    Last Post: 04-19-2007, 11:20 AM
  3. Obfuscated Code Contest
    By Stack Overflow in forum Contests Board
    Replies: 51
    Last Post: 01-21-2005, 04:17 PM
  4. Updated sound engine code
    By VirtualAce in forum Game Programming
    Replies: 8
    Last Post: 11-18-2004, 12:38 PM
  5. Interface Question
    By smog890 in forum C Programming
    Replies: 11
    Last Post: 06-03-2002, 06:06 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21