Fibonacci numbers

[dleecurt]

Hello, I have a small problem, I am trying to write a program that
will calculate the Fibonacci number series, and I have the code
complete with one problem. I used a long in to store the numbers, and
when the numbers get too large it maxes out the int and I can't count
any higher. I am trying to use extremely large numbers, I would like
to use up to 10^50 or so. So my question is how do I do this? I'm just
learning the language and I can't think of any way around variable
storage limitations. I would appreciate any advice.
Lee ;-)

[Agent Mulder]

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

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<iostre am>
#include<algori thm>
#include<vector >
static ostream_iterato r<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%b ase);while((a/=base)!=0);}
LongInt&operato r()(LongInt&a)
{
carry=0;
v.resize(a.v.si ze());
transform(v.beg in(),v.end(),a. v.begin(),v.beg in(),carrychar) ;
if(carry)v.push _back(1);
v.swap(a.v);
return*this;
}};
ostream&operato r<<(ostream&a,c onst LongInt&b)
{
copy(b.v.rbegin (),b.v.rend(),o stream_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]

In article <bn**********@n ews1.tilbu1.nb. home.nl>,
mb************* ******@home.nl says...

[ ... ]

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<iostre am>
#include<algori thm>
#include<vector >
static ostream_iterato r<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.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Jerry Coffin]

In article <bn**********@n ews1.tilbu1.nb. home.nl>,
mb************* ******@home.nl says...

[ ... ]

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

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Karl Heinz Buchegger]

Agent Mulder wrote:

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.
--
Karl Heinz Buchegger
kb******@gascad .at

[Agent Mulder]

<Agent Mulder>

char&operator() (const char&a,const char&b) </>

<Karl Heinz Buchegger> 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 mb******@home.n l
#include<iostre am>
#include<algori thm>
#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()(cons t 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%b ase);while((a/=base)!=0);}
LongInt&operato r()(LongInt&a)
{
v.resize(a.v.si ze());
carry=0;
transform(v.beg in(),v.end(),a. v.begin(),v.beg in(),carrychar) ;
if(carry)v.push _back(1);
v.swap(a.v);
return*this;
}};

//operator<< outputs a LongInt object (to the screen)
ostream&operato r<<(ostream&a,c onst LongInt&b)
{
copy(b.v.rbegin (),b.v.rend(),o stream_iterator <int>(a));
return a;
}

//main. Note how LongInt(0) is forced cout<< to produce 0,1,1,2,3,5,8,1 3...
int main()
{
LongInt a(0);
LongInt b(1);
cout<<a<<'\n';
for(int c=0;c<20;c++)co ut<<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]

"Agent Mulder" <mb************ *******@home.nl > wrote in message news:bn******** **@news1.tilbu1 .nb.home.nl...

<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<iostre am>
#include<algori thm>
#include<vector >
static ostream_iterato r<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%b ase);while((a/=base)!=0);}
LongInt&operato r()(LongInt&a)
{
carry=0;
v.resize(a.v.si ze());
transform(v.beg in(),v.end(),a. v.begin(),v.beg in(),carrychar) ;
if(carry)v.push _back(1);
v.swap(a.v);
return*this;
}};
ostream&operato r<<(ostream&a,c onst LongInt&b)
{
copy(b.v.rbegin (),b.v.rend(),o stream_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()(cons t char&a,const char&b)
to
char operator()(cons t 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_bac k (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::operato r+ (const BigInt& rhs_i) const
{
BigInt ret;

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

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

u1.resize(max_s ize);
u2.resize(max_s ize);
ret.units_.resi ze(max_size);

ulong head = 0;
transform (u1.begin(), u1.end(), u2.begin(), ret.units_.begi n(), 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_.s ize () - 1); i > 0; i--)
{
os << ins_i.units_ [i] << setw (BASE - 1) << setfill ('0');
}
return os << ins_i.units_ [0];
}
// --------------
void BigInt::Set_Ful l_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_ [i] << "\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:al****@c onnect.to
http://mathforum.org/library/view/10978.html
news://news.gmane.org/gmane.comp.lang.c++.perfometer
=============== =============== =======

[Alex Vinokur]

"Alex Vinokur" <al****@bigfoot .com> wrote in message news:bn******** ****@ID-79865.news.uni-berlin.de...

[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_bac k (unit_i);
}

BigInt (BigInt lhs_i, BigInt rhs_i)
{
const ulong max_size = MAX_VALUE (lhs_i.units_.s ize (), rhs_i.units_.si ze ());

lhs_i.units_.re size(max_size);
rhs_i.units_.re size(max_size);
units_.resize(m ax_size);

head_s = 0;
transform (lhs_i.units_.b egin(), lhs_i.units_.en d(), rhs_i.units_.be gin(), units_.begin(), *this);

if (head_s) units_.push_bac k (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_.s ize () - 1); i > 0; i--)
{
os << ins_i.units_ [i] << setw (BASE - 1) << setfill ('0');
}
return os << ins_i.units_ [0];
}
// --------------
void BigInt::Set_Ful l_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_ [i] << "\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:al****@c onnect.to
http://mathforum.org/library/view/10978.html
news://news.gmane.org/gmane.comp.lang.c++.perfometer
=============== =============== =======

[fazavon]

you guys are making this to hard... i have this and it works great

#include "stdafx.h"
#include <iostream>
using namespace std;

unsigned long fibo(unsigned long n, unsigned long x)
{
long sum;
cout << x << " ";
sum=n + x;
if (n < 214748364725552 875423484564368 465463456756432 163748648675412 )
{
return sum + fibo(x,sum);
}
else
{
return x;
}
};

int main(int argc, char* argv[])
{
int y;
fibo(0,1);
cin >> y;
return 0;
}