Optimisation

This is a discussion on Optimisation within the A Brief History of Cprogramming.com forums, part of the Community Boards category; I was fooling around with a fibonacci program whereby a recursive call is used. Code: #include <stdio.h> long fibonacci(long); int ...

  1. #1
    Registered User EvenFlow's Avatar
    Join Date
    Oct 2001
    Posts
    422

    Optimisation

    I was fooling around with a fibonacci program whereby a recursive call is used.

    Code:
    #include <stdio.h>
    
    long fibonacci(long);
    
    int main (void)
    {
    
    	long result, number;
    
    	printf("Fibonacci Program\n\n");
    	printf("Enter an integer please: ");
    	scanf("%d", &number);
    
    	result = fibonacci(number);
    
    	printf("Fibonacci %ld = %ld\n", number, result);
    	return 0;
    }
    
    long fibonacci(long n)
    {
    	if (n == 0 || n == 1)
    		return n;
    
    	else
    		return fibonacci(n - 1) + fibonacci(n - 2);
    
    }
    This program does its job for any integer from 1 - 26, without slowing down. The number of recursive calls that get executed to calculate the nth fibonacci number is on the order of 2n. Say you entered 20 - this would require 220 calls (about a million or so).

    Interestingly enough, I ran this on one of the computers at university (1GHz Pentiums). Entering in 40 it still took quite some time to process (at least 10-12 seconds by my count).

    I guess it is easy to see that even though most modern CPUs are incredibly fast, it is interesting to see that no matter how fast they are, a program such as this (or any that isn't optimised) still runs slowly. Hence my point - optimising code is still important and shouldn't be neglected.
    Last edited by EvenFlow; 10-29-2001 at 06:06 AM.
    Ramble on...

  2. #2
    zen
    zen is offline
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    Hence my point - optimising code is still important and shouldn't be neglected.
    Neither should planning, if you wanted to do it quickly for a high number you wouldn't use recursion .
    zen

  3. #3
    Registered User EvenFlow's Avatar
    Join Date
    Oct 2001
    Posts
    422
    I was deliberately using recursion to demonstrate that fact - i.e. a better method could have been used, and that is what is slowing down the program.
    Ramble on...

  4. #4
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    There is a difference between optimizing and starting with horribly inefficient algorithms. Using O(2^N) algorithms does not mandate the need for optimization. One can write fairly efficient fibonacci code without breaking out a profiler and assembler.
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  5. #5
    Registered User EvenFlow's Avatar
    Join Date
    Oct 2001
    Posts
    422
    Guess I could've used a better example couldn't I? But thanks for pointing that out ss.
    Ramble on...

  6. #6
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    There's nothing wrong recursion it's that
    you are recalculating every value so many times.

    Code:
    int f(int n, int a, int b, int num)
    {
           if (n == num)
                     return b;
           
           return f(n+1, b, a+b, num);
    }
    
    int fib(int num)
    {
             if (num <= 2) return 1;
    
             return f(0, 1, 2, num-3);
    }
    I would expect to be much faster than the other recursive routine.
    A really good optmizing c compiler would be able to optimize the function calls out and do jumps.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Hello!a simple optimisation required!
    By chottachatri in forum C Programming
    Replies: 10
    Last Post: 10-19-2008, 07:06 AM
  2. passing std::vector and optimisation
    By l2u in forum C++ Programming
    Replies: 10
    Last Post: 07-03-2008, 11:01 AM
  3. Benchmarking and Optimisation Q's
    By studiesrule in forum C++ Programming
    Replies: 11
    Last Post: 10-19-2006, 07:57 AM
  4. Optimisation of reading from file
    By bc2005 in forum C Programming
    Replies: 2
    Last Post: 01-15-2006, 04:26 AM
  5. Optimisation
    By weever in forum C Programming
    Replies: 6
    Last Post: 01-26-2002, 05:41 AM

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