DaniWeb Forum Index > Software Development > C++

C++ RSS

fibonacci

Thread Solved

•

Join Date: Jun 2006

Posts: 1,169

Reputation: Duki has a spectacular aura about

Solved Threads: 9

Duki

Offline

Veteran Poster

Re: fibonacci

#11

Oct 25th, 2007

Oh, ok. so changing the array to static solved everything. It's still really slow, compared to this one:

 Help with Code Tags 
 c++ Syntax (Toggle Plain Text) 
#include <ctime>
#include <iostream>
using namespace std ;
 
int main ( )
{
    int n ;
 
    cout << "Enter number of elements:  " << flush ;
    cin >> n ;
 
    int * fibArray = new int[ n ] ;
 
    clock_t start ;
    clock_t end ;
 
    cout << "Beginning timer..." << endl ;
    start = clock() ;
 
    fibArray[ 0 ] = 1 ;
    fibArray[ 1 ] = 1 ;
 
    for ( int i = 2 ; i < n ; i++ )
        fibArray[ i ] = fibArray[ i - 1 ] + fibArray[ i - 2 ] ;
 
    for ( int j = 0 ; j < n ; j++ )
    cout << fibArray[j] << "\t" ;
 
    cout << endl ;
 
    end = clock() ;
    //cout.precision(1000) ;
    cout << "\nThe calculation took " << showpoint <<( double ( end ) - start ) / CLOCKS_PER_SEC << " seconds.\n" ;
 
    cout << "\n\n-- Done --\n\n" ;
 
    cout << endl ;
 
    return 0 ;
}
#include <ctime>
#include <iostream>
using namespace std ;

int main ( )
{
    int n ;

    cout << "Enter number of elements:  " << flush ;
    cin >> n ;

    int * fibArray = new int[ n ] ;

    clock_t start ;
    clock_t end ;

    cout << "Beginning timer..." << endl ;
    start = clock() ;

    fibArray[ 0 ] = 1 ;
    fibArray[ 1 ] = 1 ;

    for ( int i = 2 ; i < n ; i++ )
        fibArray[ i ] = fibArray[ i - 1 ] + fibArray[ i - 2 ] ;

    for ( int j = 0 ; j < n ; j++ )
    cout << fibArray[j] << "\t" ;

    cout << endl ;

    end = clock() ;
    //cout.precision(1000) ;
    cout << "\nThe calculation took " << showpoint <<( double ( end ) - start ) / CLOCKS_PER_SEC << " seconds.\n" ;

    cout << "\n\n-- Done --\n\n" ;

    cout << endl ;

    return 0 ;
}

But that was expected; we get extra credit for programming both and timing the two.
I'm still frustrated that I can't do static int fibArray [ n ] instead of 25, or some other constant value.

Last edited by Duki; Oct 25th, 2007 at 2:24 pm.

It is practically impossible to teach good programming style to students that have had prior exposure to Basic; as potential programmers they are mentally mutilated beyond hope of regeneration.

-Edsger Dijkstra

•

Join Date: Oct 2007

Posts: 62

Reputation: Ptolemy is an unknown quantity at this point

Solved Threads: 8

Ptolemy

Offline

Junior Poster in Training

Re: fibonacci

#12

Oct 25th, 2007

>so changing the array to static solved everything.
No, changing the array to static and actually using the values you've cached solved everything. If you don't to the latter, your code won't be any faster than the usual recursive solution.

>It's still really slow, compared to this one
Your function might be slow, but mine is a hair faster in my tests than the code you're referring to. I've included a little test below.

>I'm still frustrated that I can't do static int fibArray [ n ]
>instead of 25, or some other constant value.
A better alternative is to pass a buffer to the function rather than use a static or global array. I've made that change in the test below.

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include <ctime>
#include <iostream>
 
using namespace std;
 
int fib ( int fibArray[], int n )
{
  if ( n <= 1 )
    return 1;
  else {
    fibArray[0] = 1;
    fibArray[1] = 1;
 
    for ( int i = 2 ; i <= n ; i++ ) {
      if ( fibArray[i] == 0 )
        fibArray[i] = ( fib ( fibArray, n - 1 )
        + ( fib ( fibArray, n - 2 ) ) );
    }
  }
 
  return fibArray[n];
}
 
int main()
{
  int n;
 
  cout << "Enter number of elements:  ";
  cin >> n;
 
  int * fibArray = new int[n];
 
  clock_t start;
 
  cout << "Beginning timer..." << endl;
  start = clock();
 
  fibArray[ 0 ] = 1;
  fibArray[ 1 ] = 1;
 
  for ( int i = 2 ; i < n ; i++ )
    fibArray[ i ] = fibArray[ i - 1 ] + fibArray[ i - 2 ];
 
  for ( int j = 0 ; j < n ; j++ )
    cout << fibArray[j] << "\t";
  cout << '\n';
 
  cout << "\nThe calculation took " << showpoint
    <<( double ( clock() ) - start ) / CLOCKS_PER_SEC << " seconds.\n";
  cout << "\n\n-- Done --\n\n";
 
  // Reset the array so that previous results don't make fib faster
  for ( int i = 0; i < n; i++ )
    fibArray[i] = 0;
 
  cout << "Beginning timer..." << endl;
  start = clock();
 
  for ( int j = 0 ; j < n ; j++ )
    cout << fib ( fibArray, j ) << "\t";
  cout << '\n';
 
  cout << "\nThe calculation took " << showpoint
    <<( double ( clock() ) - start ) / CLOCKS_PER_SEC << " seconds.\n";
  cout << "\n\n-- Done --\n\n";
 
  return 0;
}
#include <ctime>
#include <iostream>

using namespace std;

int fib ( int fibArray[], int n )
{
  if ( n <= 1 )
    return 1;
  else {
    fibArray[0] = 1;
    fibArray[1] = 1;

    for ( int i = 2 ; i <= n ; i++ ) {
      if ( fibArray[i] == 0 )
        fibArray[i] = ( fib ( fibArray, n - 1 )
        + ( fib ( fibArray, n - 2 ) ) );
    }
  }

  return fibArray[n];
}

int main()
{
  int n;

  cout << "Enter number of elements:  ";
  cin >> n;

  int * fibArray = new int[n];

  clock_t start;

  cout << "Beginning timer..." << endl;
  start = clock();

  fibArray[ 0 ] = 1;
  fibArray[ 1 ] = 1;

  for ( int i = 2 ; i < n ; i++ )
    fibArray[ i ] = fibArray[ i - 1 ] + fibArray[ i - 2 ];

  for ( int j = 0 ; j < n ; j++ )
    cout << fibArray[j] << "\t";
  cout << '\n';

  cout << "\nThe calculation took " << showpoint
    <<( double ( clock() ) - start ) / CLOCKS_PER_SEC << " seconds.\n";
  cout << "\n\n-- Done --\n\n";

  // Reset the array so that previous results don't make fib faster
  for ( int i = 0; i < n; i++ )
    fibArray[i] = 0;

  cout << "Beginning timer..." << endl;
  start = clock();

  for ( int j = 0 ; j < n ; j++ )
    cout << fib ( fibArray, j ) << "\t";
  cout << '\n';

  cout << "\nThe calculation took " << showpoint
    <<( double ( clock() ) - start ) / CLOCKS_PER_SEC << " seconds.\n";
  cout << "\n\n-- Done --\n\n";

  return 0;
}