Discuss Is this normal? in the C Programming forum on Dev Shed. Is this normal? C programming forum discussing all C derivatives, including C#, C++, Object-C, and even plain old vanilla C. These languages are low level languages, and used on projects such as device drivers, compilers, and even whole computer operating systems.
Posts: 142
Time spent in forums: 1 Day 6 h 21 m 2 sec
Reputation 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!
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.
Posts: 3,372
Time spent in forums: 1 Month 2 Weeks 3 Days 11 h 39 m 38 sec
Reputation Power: 383
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.