Thread: Is this normal?

    #1
  1. The bad and the ugly...
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2007
    Location
    Oz... No??? Neverland then?
    Posts
    142
    Rep Power
    0

    Is this normal?


    Code:
    #include <stdio.h>
    
    #define MAXCHAR 256
    
    long long fibonacci(int n);
    	
    void main(void)
    	{
    		int n = 0;
    		int x = 0;
    		
    		//declaration variables
    		FILE *filename; //input filename handle
    		char *fname = NULL;
    		int n = 0; //used for prompting user for size of Fibonacci series
    		fname = (char *)malloc(MAXCHAR * sizeof(char)); //allocate memory for size of filename (char = 1 bit)
    		
    		//
    		//prompt user for file name and continue to do so until a valid file name is given
    		printf("Enter file name: ");
    		scanf("%s", fname);
    		
    		//filename is just the handle to that file. have to go through filename for IO operation
    		filename = fopen(fname, "w"); 
    		
    		//promt user for size of Fibonacci series
    		printf("Enter the size of the Fibonacci series to calculate: ");
    		scanf("%d", &n);
    		
    		//print series to cmd prompt
    		for (x; x <= n; x++)
    			printf("%lld ", fibonacci(x));
    			
    			
    	}
    	
    long long fibonacci(int n)
    	{
    		//special case
    		if (n == 0)
    			{
    				return 0;
    			}
    		//special case	
    		else if (n == 2 || n == 1)
    			{
    				return 1;
    			}
    		//recursive algorithm to return sum of previous 2 numbers in series	
    		else
    			{
    				return fibonacci(n - 1) + fibonacci(n - 2);
    			}
    	}
    Obviously I haven't implemented my fprintf( ) yet, but just printing to cmd prompt, if i choose n = 45 or something, it starts to take a while to calculate and print the numbers haha. Is this my cpu working its *** off to come up with the numbers? Is this normal?

    I haven't tried n = 3453456 yet because I'm downloading LoL and don't anything to crash...
    "Life is not a journey with the intent on arriving at the finish line in a pretty and well preserved body. But rather to skid in broadside, totally worn out, thoroughly used up and loudly proclaiming, "Wow! What a ride!" -Anonymous
    Halo! || Diablo 2 LOD Modding || OLGA's BACK!
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,385
    Rep Power
    1871
    Well your recursive fibonacci function is horribly inefficient.

    If you count how many times the function is called for working out each answer, it looks like this!
    Code:
    fib(0)=0 (calls=1)
    fib(1)=1 (calls=1)
    fib(2)=1 (calls=1)
    fib(3)=2 (calls=3)
    fib(4)=3 (calls=5)
    fib(5)=5 (calls=9)
    fib(6)=8 (calls=15)
    fib(7)=13 (calls=25)
    fib(8)=21 (calls=41)
    fib(9)=34 (calls=67)
    fib(10)=55 (calls=109)
    fib(11)=89 (calls=177)
    fib(12)=144 (calls=287)
    fib(13)=233 (calls=465)
    fib(14)=377 (calls=753)
    fib(15)=610 (calls=1219)
    fib(16)=987 (calls=1973)
    fib(17)=1597 (calls=3193)
    fib(18)=2584 (calls=5167)
    fib(19)=4181 (calls=8361)
    fib(20)=6765 (calls=13529)
    Here is a very simple loop which is much more efficient.
    Code:
    long long int f2(int n) {
        long long int result = 0;
        long long int previous = 1;
        int i;
        for ( i = 0 ; i < n ; i++ ) {
            long long int next = result + previous;
            previous = result;
            result = next;
        }
        return result;
    }

    > I haven't tried n = 3453456 yet because I'm downloading LoL and don't anything to crash...
    You're only going to get up to about 90! before being hit with rounding errors.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  4. #3
  5. The bad and the ugly...
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2007
    Location
    Oz... No??? Neverland then?
    Posts
    142
    Rep Power
    0
    haha thats really cool. how do you know how many times it's calling the function? a debugger?


    and is recursion usually inefficient? or is it just this case? what makes it so inefficient?

    ~Tim
    "Life is not a journey with the intent on arriving at the finish line in a pretty and well preserved body. But rather to skid in broadside, totally worn out, thoroughly used up and loudly proclaiming, "Wow! What a ride!" -Anonymous
    Halo! || Diablo 2 LOD Modding || OLGA's BACK!
  6. #4
  7. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,385
    Rep Power
    1871
    > how do you know how many times it's calling the function? a debugger?
    A crude hack.
    Code:
    int count = 0;
    void foo ( ) {
        count++;
    }
    > and is recursion usually inefficient? or is it just this case? what makes it so inefficient?
    This
    return fibonacci(n - 1) + fibonacci(n - 2);

    Which you could also write as
    return n-1 + fibonacci(n - 2) + fibonacci(n - 2);

    It's basically working out the entire answer twice (as you can see from the counts).

    Comments on this post

    • b49P23TIvg disagrees : formula n-1 + fibonacci(n - 2) + fibonacci(n - 2); is incorrect
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  8. #5
  9. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,851
    Rep Power
    481
    To speed up Fibonacci calculations use memoization---in other words, store the values as you compute them, when you need a term first look it up. If it's there you're done. If not, compute the term and stash it.

    Salem's non-recursive f2 is quite good.

    Don Knuth may have figured out still another method.

    And, of course, there's the matrix multiplication method which runs in O(log(n)) time.

    See tition's posts, or look up at mathworld, or in the online handbook of integer sequences.

    In j, executable Iverson notation now available for Android and IPhone
    Code:
       mp    NB. matrix product
    $:~ :(+/ .*)
       
       F     NB. (Fib(2) Fib(1)) ,: (Fib(1) Fib(0))
    1 1
    1 0
    
       NB. The "anti-diagonal" is Fib(1), Fib(2), ........................................... Fib(16)
       <"2 F mp^:(<16) F    NB. creeping solution
    ┌───┬───┬───┬───┬───┬────┬─────┬─────┬─────┬─────┬──────┬───────┬───────┬───────┬───────┬────────┐
    │1 1│2 1│3 2│5 3│8 5│13 8│21 13│34 21│55 34│89 55│144 89│233 144│377 233│610 377│987 610│1597 987│
    │1 0│1 1│2 1│3 2│5 3│ 8 5│13  8│21 13│34 21│55 34│ 89 55│144  89│233 144│377 233│610 377│ 987 610│
    └───┴───┴───┴───┴───┴────┴─────┴─────┴─────┴─────┴──────┴───────┴───────┴───────┴───────┴────────┘
       NB. The "anti-diagonal" is Fib(1), Fib(2), Fib(4), Fib(8), Fib(16) {see agreement with above}, Fib(32 = 2^5)
       <"2 mp^:(<6) F       NB. high matrix powers
    ┌───┬───┬───┬─────┬────────┬───────────────┐
    │1 1│2 1│5 3│34 21│1597 987│3524578 2178309│
    │1 0│1 1│3 2│21 13│ 987 610│2178309 1346269│
    └───┴───┴───┴─────┴────────┴───────────────┘
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo