September 26th, 2012, 09:44 PM

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!
September 26th, 2012, 11:19 PM

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.
September 27th, 2012, 12:18 AM

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!
September 27th, 2012, 01:34 AM

> 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 n1 + 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
September 27th, 2012, 08:19 AM

To speed up Fibonacci calculations use memoizationin 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 nonrecursive 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 "antidiagonal" 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 "antidiagonal" 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!