Fibonacci is not doing the math properly

  • (2 Pages)
  • +
  • 1
  • 2

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

#16 StudioUAC  Icon 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:54 PM

the recursive function, i'm keeping track how many time it's called. the non recursive function i'm keeping track how many times it loops.
Was This Post Helpful? 0
  • +
  • -

#17 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 6110
  • View blog
  • Posts: 21,027
  • Joined: 05-May 12

Re: Fibonacci is not doing the math properly

Posted 28 February 2018 - 06:20 PM

This is the output I got with that main() from post #14.
Non-recursive version
Fib(1) = 1 loops 2
Fib(2) = 1 loops 3
Fib(3) = 2 loops 4
Fib(4) = 3 loops 5
Fib(5) = 5 loops 6
Fib(6) = 8 loops 7
Fib(7) = 13 loops 8
Fib(8) = 21 loops 9
Fib(9) = 34 loops 10
Fib(10) = 55 loops 11
Fib(11) = 89 loops 12
Fib(12) = 144 loops 13
Fib(13) = 233 loops 14
Fib(14) = 377 loops 15
Fib(15) = 610 loops 16
Fib(16) = 987 loops 17
Fib(17) = 1597 loops 18
Fib(18) = 2584 loops 19
Fib(19) = 4181 loops 20
Fib(20) = 6765 loops 21



Are you sure that you are compiling and running the right code?
Was This Post Helpful? 0
  • +
  • -

#18 StudioUAC  Icon 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 - 08:55 PM

this is my latest code. i compiled it and ran it on cpp.sh

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

using namespace std;

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

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


int main() {
    
     long count;  
     int i;
     


 
    
    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;
}
    

   
   
   
   
   
   
   

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

   return returnValue;
}



//non recursive fibonacci function
long NonFib(int n, long& count)
{   
	long prev = 0;
	long result = 1;
	long sum;
	int i;

   
    
    
	for(i = 3; i <=n; i++)
	{
        
        sum = (result + prev);
		prev = result;
        result = sum;
        count++;
    }
     
    
	return result;
}






void Timer(){
    
clock_t start, stop, time;
long count;

start = clock();
Fib(50,count);
stop = clock();
time = stop-start;
cout << "That took " << time  << " microseconds or " << time/US_TO_SEC << " seconds." << endl;
    
 return;   
}






this was my output

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 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

Non-recursive version
Fib(1) = 1 loops 0
Fib(2) = 1 loops 0
Fib(3) = 1 loops 1       
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
Fib(11) = 55 loops 9
Fib(12) = 89 loops 10
Fib(13) = 144 loops 11
Fib(14) = 233 loops 12
Fib(15) = 377 loops 13
Fib(16) = 610 loops 14
Fib(17) = 987 loops 15
Fib(18) = 1597 loops 16
Fib(19) = 2584 loops 17
Fib(20) = 4181 loops 18


Was This Post Helpful? 0
  • +
  • -

#19 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 6110
  • View blog
  • Posts: 21,027
  • Joined: 05-May 12

Re: Fibonacci is not doing the math properly

Posted 01 March 2018 - 10:26 AM

Looks like your iterative version is not computing the right Fibonacci number.
Was This Post Helpful? 0
  • +
  • -

#20 StudioUAC  Icon 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 01 March 2018 - 02:22 PM

i got it to work now

i had to convert it with dos2unix and change the long prev = 0; to a 1
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2