 cdruGo ColtsPremium,MVM
join:2003-05-14
Fort Wayne, IN
kudos:7 | reply to cplusnoob
Re: Please help me understand this functionsaid by cplusnoob :I'll do some more research I guess. I have caught on really quick to everything up to this point and I just want to make sure I understand what the code is doing and not just copy / paste it. There's 3 common ways (maybe more) that actually solve the calculation. Each one has their advantages and disadvantages.
The simplest/quickest algorithm to implement is the recursive algorithm that you're working with now. It's also the least efficient. The same function is called multiple times with the same value, and the extensive pushing and popping to the call stack kills the performance.
An improved algorithm instead of recursively starting at n and working there way down to 1. Instead it performs a definite loop from 1 to n, adding as it goes. It's still has to iterate over all n levels, but saves considerably due to the stack not growing very rapidly.
static int fib(int n)
{
int u = 0;
int v = 1;
int i, t;
for (i = 2; i <= n; i++)
{
t = u + v;
u = v;
v = t;
}
return v;
}
The fastest performance is just O(1), and reduces the computation to a single line of code.
static int fib(int n)
{
return (int)((1 / Math.Sqrt(5)) * (Math.Pow(((1 + Math.Sqrt(5)) / 2), n) - Math.Pow(((1 - Math.Sqrt(5)) / 2), n)));
}
Calling the function recursively, for n = 1 to 50, run time was 946708 milliseconds. (over 15 minutes). Running for the same sample size, the other two functions did not even register 1 ms. I had to up the sample size to 1 to 10000 where looping was 274 ms and the single line function was 53 ms. |
davePremium,MVM
join:2000-05-04
not in ohio
kudos:8 | I would assume the whole point of the OP's code is that it's an exercise in understanding recursive activation, since (as you say) it's not a sensible approach to use otherwise. |
cdruGo ColtsPremium,MVM
join:2003-05-14
Fort Wayne, IN
kudos:7 | said by dave:I would assume the whole point of the OP's code is that it's an exercise in understanding recursive activation, since (as you say) it's not a sensible approach to use otherwise.
I would presume that too. But its one of the classic problems that are tackled multiple different ways showing that there's more then one method to tackle a problem, and that there are advantages and disadvantages for each method. |
