Fibonacci numbers

[Agent Mulder]

-----------------------
Algorithm-1 : See above
-----------------------
[1] 17.47 real, 17.16 user, 0.19 sys
[2] 17.44 real, 17.24 user, 0.15 sys
[3] 17.46 real, 17.19 user, 0.18 sys
[4] 17.36 real, 17.15 user, 0.13 sys
[5] 17.52 real, 17.22 user, 0.15 sys

--------------------------
Algorithm-2 : http://alexvn.freeservers.com/s1/fibonacci.html
--------------------------
[1] 9.26 real, 9.00 user, 0.19 sys
[2] 9.31 real, 9.06 user, 0.21 sys
[3] 9.38 real, 9.07 user, 0.24 sys
[4] 9.35 real, 9.06 user, 0.21 sys
[5] 9.33 real, 9.00 user, 0.27 sys

</>

Those are promissing results. Thank you, Alex!

Here is a functor-based Fibonacci generator. It is quicker than ever.
The bottleneck is in the output to the screen, that slows down the
program considerably. I guess this program can run 4 times faster than
it does now. If you want to impress us, fiddle with ios_base. Dietmar?

#include<iostream>
#include<algorithm>
#include<vector>
static ostream_iterator<int>out(cout);
static char base=10;
static char carry=0;
struct CarryChar
{
char&operator()(const char&a,const char&b)
{
char c=a+b+carry;
carry=0;
if(c>=base){c-=base;carry=1;}
return c;
}};
struct LongInt
{
CarryChar carrychar;
vector<char>v;
LongInt(char a){do v.push_back(a%base);while((a/=base)!=0);}
LongInt&operator()(LongInt&a)
{
carry=0;
v.resize(a.v.size());
transform(v.begin(),v.end(),a.v.begin(),v.begin(),carrychar);
if(carry)v.push_back(1);
v.swap(a.v);
return*this;
}};
ostream&operator<<(ostream&a,const LongInt&b)
{
copy(b.v.rbegin(),b.v.rend(),ostream_iterator<int>(a));
return a;
}
int main()
{
LongInt a(0);
LongInt b(1);
for(int c=0;c<5000;c++)cout<<a(b)<<'\n';
return 0;
}

 

[Jerry Coffin]

[ ... ]

Here is a functor-based Fibonacci generator. It is quicker than ever.

Right now, it looks to me mostly like proof that you use a (badly)
broken compiler.

The bottleneck is in the output to the screen, that slows down the
program considerably. I guess this program can run 4 times faster than
it does now. If you want to impress us, fiddle with ios_base. Dietmar?

#include<iostream>
#include<algorithm>
#include<vector>
static ostream_iterator<int>out(cout);

The compiler _should_ complain about 'cout' being an undeclared name (I
suspect you intended to use std::cout).

char&operator()(const char&a,const char&b)
{
char c=a+b+carry;
carry=0;
if(c>=base){c-=base;carry=1;}
return c;
}};

This returns a reference to a local variable, which almost inevitably
leads to undefined behavior.

[ ...]

int main()
{
LongInt a(0);
LongInt b(1);
for(int c=0;c<5000;c++)cout<<a(b)<<'\n';

And _this_ is about as counter-intuitive as anything could possibly be.

 

[Jerry Coffin]

[ ... ]

Here is a functor-based Fibonacci generator. It is quicker than ever.
The bottleneck is in the output to the screen, that slows down the
program considerably. I guess this program can run 4 times faster than
it does now. If you want to impress us, fiddle with ios_base. Dietmar?

Just for reference, I wrote up a short little Fibonacci number generator
using NTL. I then ran both it and your program (after fixing it) on my
machine, with the output re-directed to NUL (/dev/null for UNIX types)
to mostly remove the I/O from the picture.

The NTL program was approximately 4 times as fast as your's. If you
want to impress us, write some code that's correct and readable...

 

[Karl Heinz Buchegger]

struct CarryChar
{
char&operator()(const char&a,const char&b)

what is the point in passing a single character per reference?
Dito for the return value.

 

[Agent Mulder]

char&operator()(const char&a,const char&b)

</>

what is the point in passing a single character per reference?
Dito for the return value.

</>

No point. Just forgot to remove it. I did remove comment
and indentation, by accident. I put it back in, but remember

"to road to perdition is paved with good indentation"
---Andrei Alexandrescu



//fast Fibonacci generator for large numbers. Email to (e-mail address removed)
#include<iostream>
#include<algorithm>
#include<vector>

//global data base, carry. Used by CarryChar and LongInt
static char base=10;
static char carry=0;

//struct CarryChar is used as functor in the STL transform algorithm
struct CarryChar
{
char operator()(const char a,const char b)
{
char c=a+b+carry;
carry=0;
if(c>=base){c-=base;carry=1;}
return c;
}};

//global data carrychar, one instance of the above struct CarryChar
CarryChar carrychar;

//struct LongInt holds an expanding vector<char> and uses carrychar
struct LongInt
{
vector<char>v;
LongInt(char a){do v.push_back(a%base);while((a/=base)!=0);}
LongInt&operator()(LongInt&a)
{
v.resize(a.v.size());
carry=0;
transform(v.begin(),v.end(),a.v.begin(),v.begin(),carrychar);
if(carry)v.push_back(1);
v.swap(a.v);
return*this;
}};

//operator<< outputs a LongInt object (to the screen)
ostream&operator<<(ostream&a,const LongInt&b)
{
copy(b.v.rbegin(),b.v.rend(),ostream_iterator<int>(a));
return a;
}

//main. Note how LongInt(0) is forced cout<< to produce 0,1,1,2,3,5,8,13...
int main()
{
LongInt a(0);
LongInt b(1);
cout<<a<<'\n';
for(int c=0;c<20;c++)cout<<a(b)<<'\n';
return 0;
}

 

[Agent Mulder]

I hate to misspell a quote, so here once again:

"the road to perdition is paved with good indentation"
---Andrei Alexandrescu

-X

 

[Alex Vinokur]

-----------------------
Algorithm-1 : See above
-----------------------
[1] 17.47 real, 17.16 user, 0.19 sys
[2] 17.44 real, 17.24 user, 0.15 sys
[3] 17.46 real, 17.19 user, 0.18 sys
[4] 17.36 real, 17.15 user, 0.13 sys
[5] 17.52 real, 17.22 user, 0.15 sys

--------------------------
Algorithm-2 : http://alexvn.freeservers.com/s1/fibonacci.html
--------------------------
[1] 9.26 real, 9.00 user, 0.19 sys
[2] 9.31 real, 9.06 user, 0.21 sys
[3] 9.38 real, 9.07 user, 0.24 sys
[4] 9.35 real, 9.06 user, 0.21 sys
[5] 9.33 real, 9.00 user, 0.27 sys

</>

Those are promissing results. Thank you, Alex!

Thank you, Agent!

Here is a functor-based Fibonacci generator. It is quicker than ever.
The bottleneck is in the output to the screen, that slows down the
program considerably.

I think, one should measure getting only n-th Fibonacci number (not all Fibonacci number 1 until n)

I guess this program can run 4 times faster than
it does now. If you want to impress us, fiddle with ios_base. Dietmar?

// ###########################################
// Computing very long Fibonacci numbers : BEGIN
// Algorithm-1b
// ###########################################

#include<iostream>
#include<algorithm>
#include<vector>
static ostream_iterator<int>out(cout);
static char base=10;
static char carry=0;
struct CarryChar
{
char&operator()(const char&a,const char&b)
{
char c=a+b+carry;
carry=0;
if(c>=base){c-=base;carry=1;}
return c;
}};
struct LongInt
{
CarryChar carrychar;
vector<char>v;
LongInt(char a){do v.push_back(a%base);while((a/=base)!=0);}
LongInt&operator()(LongInt&a)
{
carry=0;
v.resize(a.v.size());
transform(v.begin(),v.end(),a.v.begin(),v.begin(),carrychar);
if(carry)v.push_back(1);
v.swap(a.v);
return*this;
}};
ostream&operator<<(ostream&a,const LongInt&b)
{
copy(b.v.rbegin(),b.v.rend(),ostream_iterator<int>(a));
return a;
}
int main()
{
LongInt a(0);
LongInt b(1);
for(int c=0;c<5000;c++)cout<<a(b)<<'\n';
return 0;
}

To get only n-th number I changed main() as following :
------ main ------
int main(int argc, char** argv)
{
assert (argc == 2);
LongInt a(0);
LongInt b(1);
const int number (atoi(argv[1]) - 1);
for (int c = 0 ; c < number; c++) a(b);
cout << a(b) << "\n";
return 0;
}
------------------

I also changed
char& operator()(const char&a,const char&b)
to
char operator()(const char&a,const char&b)
because of compilation warning : " warning: reference to local variable `c' returned" (GNU g++ 3.3.1)

Program above (with changes) is called Algorithm-1b

// ###########################################
// Computing very long Fibonacci numbers : END
// Algorithm-1b
// ###########################################



Here is Algorithm-2b.

// ###########################################
// Computing very long Fibonacci numbers : BEGIN
// Algorithm-2b
// ###########################################

#include <assert.h>
#include <string>
#include <sstream>
#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;


#define MAX_VALUE(x,y) ((x) > (y) ? (x) : (y))
#define ASSERT(x)
// #define ASSERT(x) assert(x)

#define MAX_UNIT_VALUE (ULONG_MAX >> 2)
#define BASE 10


typedef unsigned int uint;
typedef unsigned long ulong;

// ==============
class BigInt
// ==============
{
friend class Aux;
friend ostream& operator<< (ostream& o, const BigInt& ins_i);

private :
static ulong base_s;
vector<ulong> units_;

static void Set_Full_Base ();

const BigInt operator+ (const BigInt& rhs_i) const;

public :

BigInt () {}
BigInt (ulong unit_i)
{
if (base_s == 1) Set_Full_Base ();
ASSERT (unit_i < base_s);
units_.push_back (unit_i);
}
BigInt (const BigInt& lhs_i, const BigInt& rhs_i)
{
(*this) = lhs_i + rhs_i;
}
~BigInt () {}

};


// --------------
class Aux
{
private :
ulong& head;

public :
ulong operator() (ulong n1, ulong n2)
{
ulong value = n1 + n2 + head;
head = value/BigInt::base_s;
return (value%BigInt::base_s);
}

Aux (ulong& head_io) : head (head_io) {}
};



// --------------
inline const BigInt BigInt:perator+ (const BigInt& rhs_i) const
{
BigInt ret;

const ulong max_size = MAX_VALUE (units_.size (), rhs_i.units_.size ());

vector<ulong> u1 (units_);
vector<ulong> u2 (rhs_i.units_);

u1.resize(max_size);
u2.resize(max_size);
ret.units_.resize(max_size);

ulong head = 0;
transform (u1.begin(), u1.end(), u2.begin(), ret.units_.begin(), Aux (head));

if (head) ret.units_.push_back (head);

return ret;

}



// --------------
inline ostream& operator<< (ostream& os, const BigInt& ins_i)
{
ASSERT (!ins_i.units_.empty ());
for (ulong i = (ins_i.units_.size () - 1); i > 0; i--)
{
os << ins_i.units_ << setw (BASE - 1) << setfill ('0');
}
return os << ins_i.units_ [0];
}


// --------------
void BigInt::Set_Full_Base ()
{
ASSERT (base_s == 1);

// ------------------
for (ulong i = 1; i <= (BASE - 1); i++)
{
base_s *= BASE;

ASSERT (!(base_s >= MAX_UNIT_VALUE) || (base_s == 0));
ASSERT (BASE * ((base_s/BASE) + 1) < MAX_UNIT_VALUE);
ASSERT (base_s != 0);
}
}


// =====================
class Fibonacci
// =====================
{
private :
vector<BigInt> fibs_;
BigInt get_number (uint n_i = 0);

public :
void show_all () const;
void show_number () const;

Fibonacci (uint n_i = 0) { get_number (n_i); }
~Fibonacci () {}

};


// -----------------------
BigInt Fibonacci::get_number (uint n_i)
{
const uint cur_size = fibs_.size ();

for (uint i = cur_size; i <= n_i; i++)
{
switch (i)
{
case 0 :
fibs_.push_back (BigInt(0));
break;

case 1 :
if (fibs_.empty ()) fibs_.push_back (BigInt (0));
fibs_.push_back(BigInt (1));
break;

default :
fibs_.push_back (BigInt (get_number (i - 2), get_number (i - 1)));
break;
}
}

ASSERT (n_i < fibs_.size());
return fibs_ [n_i];

}


// -----------------------
void Fibonacci::show_all () const
{
ostringstream oss;

for (uint i = 0; i < fibs_.size (); i++)
{
oss << "Fib [" << i << "] = " << fibs_ << "\n";
}
cout << oss.str();
}


// -----------------------
void Fibonacci::show_number () const
{
ostringstream oss;

oss << "Fib [" << (fibs_.size() - 1) << "] = " << fibs_.back() << "\n";

cout << oss.str();
}


// -------------------
ulong BigInt::base_s (1);


// ==============================
#define ALL_FIBS "all"
#define ONE_FIB "th"

int main (int argc, char **argv)
{
string option;
if ((argc <= 2) || !(((option = argv[2]) == ALL_FIBS) || (option == ONE_FIB)))
{
cerr << "\tUSAGE : " << argv[0] << " " << "<N - number> " << ALL_FIBS << "|" << ONE_FIB << endl;
if (argc < 2) return 1;

cerr << "\t " << "-----------------------" << endl;
cerr << "\t " << setw(3) << std::left << ALL_FIBS << " - Fibonacci [0 - N]" << endl;
cerr << "\t " << setw(3) << std::left << ONE_FIB << " - Fibonacci [N]" << endl;
cerr << "\t " << "-----------------------" << endl;
return 2;
}

Fibonacci fib(atoi(argv[1]));
(option == ALL_FIBS) ? fib.show_all() : fib.show_number();

return 0;
}

// ###########################################
// Computing very long Fibonacci numbers : END
// Algorithm-2b
// ###########################################






// ###########################################
// Comparative performance : BEGIN
// ###########################################
=============================
Windows 2000 Professional
Intel(R) Celeron(R) CPU 1.70. GHz
CYGWIN_NT-5.0 1.5.4(0.94/3/2)
GNU g++ version 3.3.1 (cygming special)
GNU time 1.7
=============================

Complexity of two algorithms has been compared while computing Fibonacci-5000, Fibonacci-10000, Fibonacci-25000.

--------------
Algorithm-1b :
--------------

Fibonacci-5000
--------------
[1] 0.27 real, 0.25 user, 0.04 sys, 10704 max-resident
[2] 0.27 real, 0.25 user, 0.03 sys, 10704 max-resident
[3] 0.27 real, 0.25 user, 0.03 sys, 10704 max-resident
[4] 0.27 real, 0.25 user, 0.03 sys, 10704 max-resident
[5] 0.27 real, 0.26 user, 0.01 sys, 10704 max-resident


Fibonacci-10000
---------------
[1] 0.95 real, 0.94 user, 0.03 sys, 10736 max-resident
[2] 0.94 real, 0.92 user, 0.04 sys, 10736 max-resident
[3] 0.94 real, 0.92 user, 0.03 sys, 10736 max-resident
[4] 0.94 real, 0.92 user, 0.03 sys, 10736 max-resident
[5] 0.94 real, 0.92 user, 0.04 sys, 10736 max-resident


Fibonacci-25000
---------------
[1] 5.63 real, 5.61 user, 0.03 sys, 10800 max-resident
[2] 5.67 real, 5.64 user, 0.03 sys, 10800 max-resident
[3] 5.62 real, 5.59 user, 0.02 sys, 10800 max-resident
[4] 5.63 real, 5.60 user, 0.04 sys, 10800 max-resident
[5] 5.66 real, 5.62 user, 0.04 sys, 10800 max-resident




--------------
Algorithm-2b :
--------------

Fibonacci-5000
--------------
[1] 0.22 real, 0.20 user, 0.03 sys, 14960 max-resident
[2] 0.22 real, 0.20 user, 0.04 sys, 14960 max-resident
[3] 0.23 real, 0.20 user, 0.04 sys, 14960 max-resident
[4] 0.22 real, 0.20 user, 0.03 sys, 14960 max-resident
[5] 0.22 real, 0.19 user, 0.04 sys, 14960 max-resident


Fibonacci-10000
---------------
[1] 0.52 real, 0.50 user, 0.03 sys, 21552 max-resident
[2] 0.52 real, 0.49 user, 0.05 sys, 21552 max-resident
[3] 0.53 real, 0.51 user, 0.03 sys, 21552 max-resident
[4] 0.53 real, 0.50 user, 0.04 sys, 21552 max-resident
[5] 0.53 real, 0.50 user, 0.04 sys, 21552 max-resident


Fibonacci-25000
---------------
[1] 2.03 real, 2.00 user, 0.01 sys, 20144 max-resident
[2] 2.02 real, 1.97 user, 0.07 sys, 20144 max-resident
[3] 2.03 real, 1.98 user, 0.06 sys, 20144 max-resident
[4] 2.03 real, 1.98 user, 0.07 sys, 20144 max-resident
[5] 2.36 real, 2.31 user, 0.05 sys, 20144 max-resident


Note. max-resident is Maximum resident set size of the process during its lifetime, in Kilobytes.

// ###########################################
// Comparative performance : END
// ###########################################


--
=====================================
Alex Vinokur
mailto:[email protected]
http://mathforum.org/library/view/10978.html
news://news.gmane.org/gmane.comp.lang.c++.perfometer
=====================================

 

[Alex Vinokur]

[snip]

// ###########################################
// Computing very long Fibonacci numbers : BEGIN
// Algorithm-2b
// ###########################################

[snip]


Here is Algorithm-2c for computing very long Fibonacci numbers.

Algorithm-2c is an improved version of Algorithm-2b.

// #####################################
// Computing very long Fibonacci numbers
// Algorithm-2c
// BEGIN
// #####################################

#include <assert.h>
#include <string>
#include <sstream>
#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;


#define MAX_VALUE(x,y) ((x) > (y) ? (x) : (y))
#define ASSERT(x)
// #define ASSERT(x) assert(x)

#define MAX_UNIT_VALUE (ULONG_MAX >> 2)
#define BASE 10


typedef unsigned int uint;
typedef unsigned long ulong;

// ==============
class BigInt
// ==============
{
friend ostream& operator<< (ostream& o, const BigInt& ins_i);

private :
static ulong head_s;
static ulong base_s;
vector<ulong> units_;

static void Set_Full_Base ();


public :
BigInt (ulong unit_i)
{
if (base_s == 1) Set_Full_Base ();
ASSERT (unit_i < base_s);
units_.push_back (unit_i);
}

BigInt (BigInt lhs_i, BigInt rhs_i)
{
const ulong max_size = MAX_VALUE (lhs_i.units_.size (), rhs_i.units_.size ());

lhs_i.units_.resize(max_size);
rhs_i.units_.resize(max_size);
units_.resize(max_size);

head_s = 0;
transform (lhs_i.units_.begin(), lhs_i.units_.end(), rhs_i.units_.begin(), units_.begin(), *this);

if (head_s) units_.push_back (head_s);

}

ulong operator() (ulong n1, ulong n2)
{
ulong value = n1 + n2 + head_s;
head_s = value/base_s;
return (value%base_s);
}

};


// --------------
inline ostream& operator<< (ostream& os, const BigInt& ins_i)
{
ASSERT (!ins_i.units_.empty ());
for (ulong i = (ins_i.units_.size () - 1); i > 0; i--)
{
os << ins_i.units_ << setw (BASE - 1) << setfill ('0');
}
return os << ins_i.units_ [0];
}


// --------------
void BigInt::Set_Full_Base ()
{
ASSERT (base_s == 1);

// ------------------
for (ulong i = 1; i <= (BASE - 1); i++)
{
base_s *= BASE;

ASSERT (!(base_s >= MAX_UNIT_VALUE) || (base_s == 0));
ASSERT (BASE * ((base_s/BASE) + 1) < MAX_UNIT_VALUE);
ASSERT (base_s != 0);
}
}


// =====================
class Fibonacci
// =====================
{
private :
vector<BigInt> fibs_;
BigInt get_number (uint n_i = 0);

public :
void show_all () const;
void show_number () const;

Fibonacci (uint n_i = 0) { get_number (n_i); }
~Fibonacci () {}

};


// -----------------------
BigInt Fibonacci::get_number (uint n_i)
{
const uint cur_size = fibs_.size ();

for (uint i = cur_size; i <= n_i; i++)
{
switch (i)
{
case 0 :
fibs_.push_back (BigInt(0));
break;

case 1 :
if (fibs_.empty ()) fibs_.push_back (BigInt (0));
fibs_.push_back(BigInt (1));
break;

default :
fibs_.push_back (BigInt (get_number (i - 2), get_number (i - 1)));
break;
}
}

ASSERT (n_i < fibs_.size());
return fibs_ [n_i];

}


// -----------------------
void Fibonacci::show_all () const
{
ostringstream oss;

for (uint i = 0; i < fibs_.size (); i++)
{
oss << "Fib [" << i << "] = " << fibs_ << "\n";
}
cout << oss.str();
}


// -----------------------
void Fibonacci::show_number () const
{
ostringstream oss;

oss << "Fib [" << (fibs_.size() - 1) << "] = " << fibs_.back() << "\n";

cout << oss.str();
}


// -------------------
ulong BigInt::head_s (0);
ulong BigInt::base_s (1);


// ==============================
#define ALL_FIBS "all"
#define ONE_FIB "th"

int main (int argc, char **argv)
{
string option;
if ((argc <= 2) || !(((option = argv[2]) == ALL_FIBS) || (option == ONE_FIB)))
{
cerr << "\tUSAGE : " << argv[0] << " " << "<N - number> " << ALL_FIBS << "|" << ONE_FIB << endl;
if (argc < 2) return 1;

cerr << "\t " << "-----------------------" << endl;
cerr << "\t " << setw(3) << std::left << ALL_FIBS << " - Fibonacci [0 - N]" << endl;
cerr << "\t " << setw(3) << std::left << ONE_FIB << " - Fibonacci [N]" << endl;
cerr << "\t " << "-----------------------" << endl;
return 2;
}

Fibonacci fib(atoi(argv[1]));
(option == ALL_FIBS) ? fib.show_all() : fib.show_number();

return 0;
}


// #####################################
// END
// Algorithm-2c
// Computing very long Fibonacci numbers
// #####################################





// ################################
// Comparative performance : BEGIN
// ################################
=============================
Windows 2000 Professional
Intel(R) Celeron(R) CPU 1.70. GHz
CYGWIN_NT-5.0 1.5.4(0.94/3/2)
GNU g++ version 3.3.1 (cygming special)
GNU time 1.7
=============================


Complexity of two algorithms has been compared while computing
* Fibonacci-5000,
* Fibonacci-10000,
* Fibonacci-25000.
Note. Output has been redirected to a file.


------------
Algorithm-2b
------------

Fibonacci-5000
--------------
[1] 0.22 real, 0.20 user, 0.03 sys, 14960 max-resident
[2] 0.22 real, 0.22 user, 0.03 sys, 14960 max-resident
[3] 0.22 real, 0.22 user, 0.02 sys, 14960 max-resident
[4] 0.23 real, 0.20 user, 0.03 sys, 14960 max-resident
[5] 0.22 real, 0.20 user, 0.03 sys, 14960 max-resident


Fibonacci-10000
---------------
[1] 0.52 real, 0.50 user, 0.04 sys, 21552 max-resident
[2] 0.52 real, 0.49 user, 0.04 sys, 21552 max-resident
[3] 0.52 real, 0.50 user, 0.05 sys, 21552 max-resident
[4] 0.52 real, 0.51 user, 0.03 sys, 21552 max-resident
[5] 0.52 real, 0.51 user, 0.03 sys, 21552 max-resident


Fibonacci-25000
---------------
[1] 2.01 real, 1.94 user, 0.09 sys, 20144 max-resident
[2] 2.02 real, 1.97 user, 0.06 sys, 20144 max-resident
[3] 2.00 real, 1.96 user, 0.05 sys, 20144 max-resident
[4] 2.00 real, 1.91 user, 0.11 sys, 20144 max-resident
[5] 2.00 real, 1.96 user, 0.05 sys, 20144 max-resident



------------
Algorithm-2c
------------

Fibonacci-5000
--------------
[1] 0.19 real, 0.17 user, 0.03 sys, 12384 max-resident
[2] 0.20 real, 0.19 user, 0.03 sys, 12384 max-resident
[3] 0.19 real, 0.18 user, 0.02 sys, 12384 max-resident
[4] 0.19 real, 0.17 user, 0.04 sys, 12384 max-resident
[5] 0.20 real, 0.18 user, 0.03 sys, 12384 max-resident


Fibonacci-10000
---------------
[1] 0.46 real, 0.45 user, 0.03 sys, 21600 max-resident
[2] 0.46 real, 0.42 user, 0.05 sys, 21600 max-resident
[3] 0.46 real, 0.44 user, 0.03 sys, 21600 max-resident
[4] 0.47 real, 0.43 user, 0.04 sys, 21600 max-resident
[5] 0.46 real, 0.45 user, 0.03 sys, 21600 max-resident


Fibonacci-25000
---------------
[1] 1.91 real, 1.86 user, 0.05 sys, 12608 max-resident
[2] 1.92 real, 1.87 user, 0.07 sys, 12608 max-resident
[3] 1.91 real, 1.83 user, 0.09 sys, 12608 max-resident
[4] 1.91 real, 1.88 user, 0.05 sys, 12608 max-resident
[5] 1.91 real, 1.85 user, 0.07 sys, 12608 max-resident


// ##############################
// Comparative performance : END
// ##############################


--
=====================================
Alex Vinokur
mailto:[email protected]
http://mathforum.org/library/view/10978.html
news://news.gmane.org/gmane.comp.lang.c++.perfometer
=====================================

 

[yousafzai]

#include<iostream>
using namespace std;
int fibonoci(long double top,long double a,long double b,long double total);
void main()
{
long double top,a=0,b=1,total=1;
cout<<"top: ";
cin>>top;
cout<<"0\n";
cout<<fibonoci(top,a,b,total);
}
int fibonoci(long double top,long double a,long double b,long double total)
{
for(int i=0;i<top;i++)
{
cout<<total<<endl;
total=a+b;
a=b;
b=total;
}
return total;
}