PDA

View Full Version : Optimisation



EvenFlow
10-29-2001, 07:03 AM
I was fooling around with a fibonacci program whereby a recursive call is used.



#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.

zen
10-29-2001, 07:46 AM
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 :).

EvenFlow
10-29-2001, 07:51 AM
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.

SilentStrike
10-29-2001, 09:36 AM
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.

EvenFlow
10-29-2001, 08:57 PM
Guess I could've used a better example couldn't I? But thanks for pointing that out ss.

Nick
10-29-2001, 10:14 PM
There's nothing wrong recursion it's that
you are recalculating every value so many times.



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.