Fibonacci is not doing the math properly

  • (2 Pages)
  • +
  • 1
  • 2

19 Replies - 587 Views - Last Post: 01 March 2018 - 02:22 PM Rate Topic: -----

#1 StudioUAC   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 14
  • Joined: 23-September 16

Fibonacci is not doing the math properly

Posted 21 February 2018 - 01:48 PM

i'm trying to create a program to calculate Fibonacci using recursion but at it's outputting is 1 calls 111

#include <iostream>
#include <time.h>

using namespace std;

long Fib(int n, long& count);
long NonFib(int n, long& count);

const int US_TO_SEC = 1000000;

int main() {
    int i = 1;
    int n = 1;
    clock_t start, stop, time;
    long count = 0;
    

   long fibTemp;
   long nonFibTemp;
   
   fibTemp = Fib(n, count);
   nonFibTemp = NonFib(n, count);
   
    
    
    
    
    
    start = clock();
    Fib(10, count );
    stop = clock();
    time = stop-start;
    
    
   cout << "Recursive version" << endl;
    for(i=1;i<=20;i++) {
       cout << "Fib(" << i << ") = " << fibTemp << " calls ";
       cout << count << endl;
    }
 cout << "That took " << time  << " microseconds or " << time/US_TO_SEC << " seconds." << endl;   
    
    
    
    
    
    
    cout << endl << "Non-recursive version" << endl;
    for(i=1;i<=20;i++) {
       cout << "Fib(" << i << ") = " << nonFibTemp << " loops ";
       cout << count << endl;
    }
    
 cout << "That took " << time  << " microseconds or " << time/US_TO_SEC << " seconds." << endl;
    
    

    return 0;
}


//recursive fibonacci function
long Fib(int n, long& count) {
 
   long returnValue;
   count++;
   
   // cout << n << "   "  <<  count << endl << endl;
 
   if (n == 1 or n == 2) {
      returnValue = 1;
      
   } else {
      returnValue = (Fib(n-1, count) + Fib(n-2, count));
       
   }
   
   

   
   
   return returnValue;
   
  
}






//non recursive fibonacci function
long NonFib(int n, long& count)
{
	long prev = -1;
	long result = 1;
	long sum;
	int i;
	count++;
	for(i = 0;i <= n;++ i)
	{
		sum = (result + prev);
		prev = result;
		result = sum;
	}
	
	return result;
}





i've tried all that i can and i'm not sure what else to do

Recursive version
Fib(1) = 1 calls 111
Fib(2) = 1 calls 111
Fib(3) = 1 calls 111
Fib(4) = 1 calls 111
Fib(5) = 1 calls 111
Fib(6) = 1 calls 111
Fib(7) = 1 calls 111
Fib(8) = 1 calls 111
Fib(9) = 1 calls 111
Fib(10) = 1 calls 111
Fib(11) = 1 calls 111
Fib(12) = 1 calls 111
Fib(13) = 1 calls 111
Fib(14) = 1 calls 111
Fib(15) = 1 calls 111
Fib(16) = 1 calls 111
Fib(17) = 1 calls 111
Fib(18) = 1 calls 111
Fib(19) = 1 calls 111
Fib(20) = 1 calls 111
That took 0 microseconds or 0 seconds.

Non-recursive version
Fib(1) = 1 loops 111
Fib(2) = 1 loops 111
Fib(3) = 1 loops 111
Fib(4) = 1 loops 111
Fib(5) = 1 loops 111
Fib(6) = 1 loops 111
Fib(7) = 1 loops 111
Fib(8) = 1 loops 111
Fib(9) = 1 loops 111
Fib(10) = 1 loops 111
Fib(11) = 1 loops 111
Fib(12) = 1 loops 111
Fib(13) = 1 loops 111
Fib(14) = 1 loops 111
Fib(15) = 1 loops 111
Fib(16) = 1 loops 111
Fib(17) = 1 loops 111
Fib(18) = 1 loops 111
Fib(19) = 1 loops 111
Fib(20) = 1 loops 111
That took 0 microseconds or 0 seconds.




Is This A Good Question/Topic? 0
  • +

Replies To: Fibonacci is not doing the math properly

#2 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6216
  • View blog
  • Posts: 21,452
  • Joined: 05-May 12

Re: Fibonacci is not doing the math properly

Posted 21 February 2018 - 02:01 PM

For the Fibonacci numbers, you are only ever outputting fibTemp and nonFibTemp which you only compute once on lines 21-22. You should compute them for each iteration within your loops.

As for the times, you do the some thing. You only compute the time once for the recursive version on lines 29-32. You don't seem to even try to time the iterative version.
Was This Post Helpful? 0
  • +
  • -

#3 StudioUAC   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 14
  • Joined: 23-September 16

Re: Fibonacci is not doing the math properly

Posted 21 February 2018 - 03:51 PM

I'm not sure how to do that.

This post has been edited by Skydiver: 21 February 2018 - 03:59 PM
Reason for edit:: Removed unnecessary quote. No need to quote the post above yours.

Was This Post Helpful? 0
  • +
  • -

#4 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6216
  • View blog
  • Posts: 21,452
  • Joined: 05-May 12

Re: Fibonacci is not doing the math properly

Posted 21 February 2018 - 04:03 PM

There's no need to quote the post above yours. Just use the big Reply button or the Fast Reply area.

You would need to re-arrange your code so that you are doing your computations, and recording the time each time through the loop.

Your current code:
compute fib

measure time to compute fib

loop 1 to 20:
    display previously computed fib

display previously measured time



What your code should look like:
loop 1 to 20:
    compute fib

display the time it took to execute that loop from 1 to 20


Was This Post Helpful? 0
  • +
  • -

#5 StudioUAC   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 14
  • Joined: 23-September 16

Re: Fibonacci is not doing the math properly

Posted 25 February 2018 - 01:39 PM

okay I was able to get the math to calculate properly from using your help. thank you. now my problem is that the count that keeps track and outputs which Fibonacci number is called

the output should look like this
Recursive version
Fib(1) = 1 calls 1
Fib(2) = 1 calls 1
Fib(3) = 2 calls 3
Fib(4) = 3 calls 5
Fib(5) = 5 calls 8
Fib(6) = 8 calls 13
Fib(7) = 13 calls 21
Fib(8) = 21 calls 34
....



but this is my actual output

Recursive version
Fib(1) = 1 calls 13530
Fib(2) = 1 calls 27060
Fib(3) = 2 calls 40592
Fib(4) = 3 calls 54126
Fib(5) = 5 calls 67664
Fib(6) = 8 calls 81208
Fib(7) = 13 calls 94762
Fib(8) = 21 calls 108332
Fib(9) = 34 calls 121928
Fib(10) = 55 calls 135566
...





I've been putting cout statments to check what the count is at certain places put every check i'm getting large numbers.




my code so far.

#include <iostream>
#include <time.h>

using namespace std;

long Fib(int n, long& count);
long NonFib(int n, long& count);


const int US_TO_SEC = 1000000;
const int MAX_FIB = 20;


int main() {
    
     long count = 0;  
     int i;
     clock_t start, stop, time;


 //cout <<  "COUNT CHECK  " << count << endl << endl;
    
    cout << "Recursive version" << endl;
    for(i=1;i<=MAX_FIB;i++) {
        
    long FibTemp = Fib(i, count);     
    start = clock();
    Fib(20, count);
    stop = clock();
    time = stop-start;
    
       cout << "Fib(" << i << ") = " << FibTemp << " calls ";
       cout << count << endl;
    }
    
     cout << "That took " << time  << " microseconds or " << time/US_TO_SEC << " seconds." << endl;  
    
  

    count = 0;
    
    

     cout << endl << "Non-recursive version" << endl;
      for(i=1;i<=MAX_FIB;i++) {
          
    long NonFibTemp = NonFib(i, count);     
    start = clock();
    Fib(20, count);
    stop = clock();
    time = stop-start; 
    
    
       cout << "Fib(" << i << ") = " << NonFibTemp << " calls ";
       cout << count << endl;
    }
    
     cout << "That took " << time  << " microseconds or " << time/US_TO_SEC << " seconds." << endl;
    
    return 0;
}
    

    

//recursive fibonacci function
long Fib(int n, long& count) {
   int returnValue;
   count++; 
   // handle the base case first;
   if (n == 1 or n == 2) {
       
      returnValue = 1;
   } else {
      
      returnValue = Fib(n-1, count) + Fib(n-2, count);
   }
   //cout <<  "COUNT CHECK  " << count << endl << endl;
   
   
   return returnValue;
}



//non recursive fibonacci function
long NonFib(int n, long& count)
{
	long prev = -1;
	long result = 1;
	long sum;
	int i;
	count++;
	for(i = 0;i <= n; i++)
	{
		sum = (result + prev);
		prev = result;
		result = sum;
      
    }
	
	return result;
}




Was This Post Helpful? 0
  • +
  • -

#6 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6216
  • View blog
  • Posts: 21,452
  • Joined: 05-May 12

Re: Fibonacci is not doing the math properly

Posted 25 February 2018 - 02:12 PM

Please don't open new threads about an existing code base. Merging threads...
Was This Post Helpful? 0
  • +
  • -

#7 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6216
  • View blog
  • Posts: 21,452
  • Joined: 05-May 12

Re: Fibonacci is not doing the math properly

Posted 25 February 2018 - 02:23 PM

That's likely because your count is being incremented both on line 26 and 28, as well as lines 47 and 49. On line 26 count get bumped up to the number of calls for Fib(i), and then incremented once more for Fib(20). Furthermore, you are not resetting the count for each time through the loop so you are getting the cummulative count of calls instead of just the number of calls needed for that one Fibonacci number.
Was This Post Helpful? 1
  • +
  • -

#8 StudioUAC   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 14
  • Joined: 23-September 16

Re: Fibonacci is not doing the math properly

Posted 25 February 2018 - 03:19 PM

so should i put a count = 0 inside the fib and nonfib loop functions?
Was This Post Helpful? 0
  • +
  • -

#9 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6216
  • View blog
  • Posts: 21,452
  • Joined: 05-May 12

Re: Fibonacci is not doing the math properly

Posted 25 February 2018 - 06:01 PM

That would be one of the changes, yes. The other is ask yourself why you are timing how long it takes to compute Fib(20) when it looks like the objective seems to be to time how long it takes to compute all the Fibonacci numbers from 1 to 20.
Was This Post Helpful? 0
  • +
  • -

#10 StudioUAC   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 14
  • Joined: 23-September 16

Re: Fibonacci is not doing the math properly

Posted 25 February 2018 - 06:24 PM

the fib(20) is there for debugging if i try to change it to anything else, i will get segmentation faults and since i'm compiling on putty from my home machine, it'll take too long to output and be killed.


so i tried putting the count = 0 into my loops in the fib function but all it's doing is changing count to 0 and that's what i'm outputting

#include <iostream>
#include <time.h>

using namespace std;

long Fib(int n, long& count);
long NonFib(int n);


const int US_TO_SEC = 1000000;
const int MAX_FIB = 20;


int main() {
    
     long count = 0;  
     int i, n;
     clock_t start, stop, time;


 
    
    cout << "Recursive version" << endl;
    for(i=1;i<=MAX_FIB;i++) {
        
    long FibTemp = Fib(i, count);
    count++;
    start = clock();
    Fib(MAX_FIB, count);
    count = 0;
    stop = clock();
    time = stop-start;
    //cout <<  "COUNT CHECK  " << count << endl << endl;
       cout << "Fib(" << i << ") = " << FibTemp << " calls ";
       cout << count << endl;
    }
    
  
    
     cout << "That took " << time  << " microseconds or " << time/US_TO_SEC << " seconds." << endl;  
    
  

   
    
    
     
     cout << endl << "Non-recursive version" << endl;
      for(i=1;i<=MAX_FIB;i++) {
          
    long NonFibTemp = NonFib(i);   
    count++;
    start = clock();
    Fib(MAX_FIB, count);
    stop = clock();
    time = stop-start; 
    
    
       cout << "Fib(" << i << ") = " << NonFibTemp << " calls ";
       cout << count << endl;
    }
    
     cout << "That took " << time  << " microseconds or " << time/US_TO_SEC << " seconds." << endl;
    
    return 0;
}
    

    

//recursive fibonacci function
long Fib(int n, long& count) {
   int returnValue;
   
   if (n == 1 or n == 2) {
      count++; 
      returnValue = 1;
      count = 0;
   } else {
      count++;
      returnValue = Fib(n-1, count) + Fib(n-2, count);
    count = 0;
       
}
   
//cout <<  " LONG FIB COUNT CHECK  " << count << endl << endl;
//count = 0;
   return returnValue;
}



//non recursive fibonacci function
long NonFib(int n)
{   
	long prev = -1;
	long result = 1;
	long sum;
	int i;
	
	for(i = 0;i <= n; i++)
	{
		sum = (result + prev);
		prev = result;
		result = sum;
        //count++; 
    }
    //count = 0;
	return result;
}






and output

Recursive version
Fib(1) = 1 calls 0
Fib(2) = 1 calls 0
Fib(3) = 2 calls 0
Fib(4) = 3 calls 0
Fib(5) = 5 calls 0
Fib(6) = 8 calls 0
Fib(7) = 13 calls 0
....


Was This Post Helpful? 0
  • +
  • -

#11 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6216
  • View blog
  • Posts: 21,452
  • Joined: 05-May 12

Re: Fibonacci is not doing the math properly

Posted 25 February 2018 - 09:15 PM

I'll be blunt. You are just throwing code at the screen trying to see what sticks, without analyzing what you are doing.

Are getting segmentation fault when you change that Fib(20) to Fib(19)? How about Fib(1)? How about if you comment out that call all together?

Of course your output would show a count of zero after you set it to zero. Why would you expect it not be the value that you set it to?

Again, take a look at what time you are measuring. If you indented your code properly/consistently it will be more obvious as to what is happening.
Was This Post Helpful? 1
  • +
  • -

#12 StudioUAC   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 14
  • Joined: 23-September 16

Re: Fibonacci is not doing the math properly

Posted 28 February 2018 - 02:53 PM

okay i was able to get the count for the recursive and nonrecursive counts to work

//non recursive fibonacci function
long NonFib(int n, long& count)
{   
	long prev = -1;
	long result = 1;
	long sum;
	int i;
	//count = 0;
    
	for(i = 0;i <= n; i++)
	{
		sum = (result + prev);
		prev = result;
		result = sum;
        count++; 
    }
    
    //
	return result;
}




my last problem is that the nonrecursive is printing out 1 once more than is should

Non-recursive version
Fib(1) = 1 loops 0
Fib(2) = 1 loops 0
Fib(3) = 1 loops 1  <---this one
Fib(4) = 2 loops 2
Fib(5) = 3 loops 3
Fib(6) = 5 loops 4
Fib(7) = 8 loops 5
Fib(8) = 13 loops 6
Fib(9) = 21 loops 7
Fib(10) = 34 loops 8
.......


Was This Post Helpful? 0
  • +
  • -

#13 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6216
  • View blog
  • Posts: 21,452
  • Joined: 05-May 12

Re: Fibonacci is not doing the math properly

Posted 28 February 2018 - 03:28 PM

Can you show us your updated main()?

The reason why I ask, is because it looks like you are "cheating" the count. Consider the case when you call NonFib(1). Your count should be 2, not 0 as you are displaying.

Why 2?

Because:
When you call NonFib(1), you'll have n == 1. So you'll effectively have the following code:
for(int i = 0; i <= n; i++)
{
    :
    count++
}



This will loop at least twice. Assuming that count was initialized to 0:
i      count
0      1
1      2


Was This Post Helpful? 0
  • +
  • -

#14 StudioUAC   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 14
  • Joined: 23-September 16

Re: Fibonacci is not doing the math properly

Posted 28 February 2018 - 04:26 PM

sure


int main() {
    
     long count;  
     int i, n;
     


 
    
    cout << "Recursive version" << endl;
    for(i=1;i<=MAX_FIB;i++) {
    count = 0;
        
        
    long FibTemp = Fib(i, count);
    
    
  
    //cout <<  "COUNT CHECK  " << count << endl << endl;
       cout << "Fib(" << i << ") = " << FibTemp << " calls ";
       cout << count << endl;
       }

   // Timer();
  

   
    
    
     
     cout << endl << "Non-recursive version" << endl;
      for(i=1;i<=MAX_FIB;i++) {
     
          count = 0;
     long NonFibTemp = NonFib(i, count);   
    
    
       cout << "Fib(" << i << ") = " << NonFibTemp << " loops ";
       cout << count << endl;
    }
    
   // Timer();

    
    return 0;
}
    

   
   
   
   


Was This Post Helpful? 0
  • +
  • -

#15 CTphpnwb   User is offline

  • D.I.C Lover
  • member icon

Reputation: 3795
  • View blog
  • Posts: 13,738
  • Joined: 08-August 08

Re: Fibonacci is not doing the math properly

Posted 28 February 2018 - 04:48 PM

Your output has "loops" but your code has "calls". Something is wrong here.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2