C Programming
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
User Name:
Password:
Remember me

The Shed is going Social! Join us on FaceBook and Twitter and chime in on the conversation.

Go Back   Dev Shed ForumsProgramming LanguagesC Programming

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Rate Thread Display Modes
 
Unread Dev Shed Forums Sponsor:
  #1  
Old September 26th, 2012, 09:44 PM
ChokolAwt's Avatar
ChokolAwt ChokolAwt is offline
The bad and the ugly...
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Jan 2007
Location: Oz... No??? Neverland then?
Posts: 142 ChokolAwt Negative: is most likely a SPAMMER and a traitor to the cause. 
Time spent in forums: 1 Day 6 h 21 m 2 sec
Reputation Power: 0
Send a message via ICQ to ChokolAwt Send a message via AIM to ChokolAwt
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!

Reply With Quote
  #2  
Old September 26th, 2012, 11:19 PM
salem's Avatar
salem salem is offline
Contributed User
Click here for more information
 
Join Date: Jun 2005
Posts: 3,839 salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)  Folding Points: 153 Folding Title: Novice Folder
Time spent in forums: 2 Months 3 Weeks 2 Days 19 h 1 m 4 sec
Reputation Power: 1774
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.
__________________
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper

Reply With Quote
  #3  
Old September 27th, 2012, 12:18 AM
ChokolAwt's Avatar
ChokolAwt ChokolAwt is offline
The bad and the ugly...
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Jan 2007
Location: Oz... No??? Neverland then?
Posts: 142 ChokolAwt Negative: is most likely a SPAMMER and a traitor to the cause. 
Time spent in forums: 1 Day 6 h 21 m 2 sec
Reputation Power: 0
Send a message via ICQ to ChokolAwt Send a message via AIM to ChokolAwt
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

Reply With Quote
  #4  
Old September 27th, 2012, 01:34 AM
salem's Avatar
salem salem is offline
Contributed User
Click here for more information
 
Join Date: Jun 2005
Posts: 3,839 salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)salem User rank is General 12nd Grade (Above 100000 Reputation Level)  Folding Points: 153 Folding Title: Novice Folder
Time spent in forums: 2 Months 3 Weeks 2 Days 19 h 1 m 4 sec
Reputation Power: 1774
> 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 n-1 + 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
b49P23TIvg disagrees: formula n-1 + fibonacci(n - 2) + fibonacci(n - 2); is incorrect

Reply With Quote
  #5  
Old September 27th, 2012, 08:19 AM
b49P23TIvg's Avatar
b49P23TIvg b49P23TIvg is offline
Contributing User
Dev Shed Loyal (3000 - 3499 posts)
 
Join Date: Aug 2011
Posts: 3,372 b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level)b49P23TIvg User rank is Major (30000 - 40000 Reputation Level) 
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.

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 "anti-diagonal" 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 "anti-diagonal" 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!

Reply With Quote
Reply

Viewing: Dev Shed ForumsProgramming LanguagesC Programming > Is this normal?

Developer Shed Advertisers and Affiliates



Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump

Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 


Powered by: vBulletin Version 3.0.5
Copyright ©2000 - 2013, Jelsoft Enterprises Ltd.

© 2003-2013 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap