Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

[C++] Computing very long Fibonacci numbers

29 views
Skip to first unread message

Alex Vinokur

unread,
Oct 19, 2003, 6:23:43 AM10/19/03
to
// ###########################################
// [C++] Computing very long Fibonacci numbers
// ###########################################

#include <assert.h>
#include <string>
#include <sstream>
#include <vector>
#include <iostream>
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 BigInt operator+ (const BigInt& lhs_i, const BigInt& rhs_i);

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

public :

BigInt () {}
BigInt (ulong unit_i)
{
ASSERT (unit_i < base_s);
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 () {}

static void Set_Full_Base ();
string getstr_value () const;
};


// --------------
inline BigInt operator+ (const BigInt & lhs_i, const BigInt& rhs_i)
{
BigInt ret;

const ulong max_size = MAX_VALUE (lhs_i.units_.size (), rhs_i.units_.size ());
ulong value;
ulong head = 0;

for (ulong i = 0; i < max_size; i++)
{
ASSERT (head < MAX_UNIT_VALUE);

value = ((i < lhs_i.units_.size ()) ? lhs_i.units_ [i] : 0)
+ ((i < rhs_i.units_.size ()) ? rhs_i.units_ [i] : 0)
+ head;

ret.units_.push_back(value%(lhs_i.base_s));

ASSERT (ret.units_ [ret.units_.size () - 1] < lhs_i.base_s);

head = value/(lhs_i.base_s);

}

ASSERT (ret.units_.size () == max_size);

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

return ret;

}


// --------------
string BigInt::getstr_value () const
{
ostringstream oss;

ASSERT (!units_.empty ());

for (ulong i = (units_.size () - 1); i > 0; i--) oss << units_ [i];
oss << units_ [0];

return oss.str();
}


// --------------
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_one (int n_i = 0);

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

Fibonacci (int n_i = 0) { get_one (n_i); }
~Fibonacci () {}

};


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

ASSERT (n_i >= 0);

for (int 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_one (i - 2), get_one (i - 1)));
break;
}
}

return fibs_ [n_i];

}


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

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


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

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

cout << oss.str();
}


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


// ==============================
#define ALL 'a'
#define ONE 'n'

int main (int argc, char **argv)
{
char ch;

if ((argc <= 2) || !(((ch = argv[2][0])== ALL) || (ch == ONE)))
{
cerr << "\tUSAGE : " << argv[0] << " " << "<N - number> " << ALL << "|" << ONE << endl;
if (argc < 2) return 1;
cerr << "\t " << "------------------------" << endl;
cerr << "\t " << ALL << " - Fibonacci [0 - " << atoi(argv[1]) << "]" << endl;
cerr << "\t " << ONE << " - Fibonacci [" << atoi(argv[1]) << "]" << endl;
cerr << "\t " << "------------------------" << endl;
return 2;
}

BigInt::Set_Full_Base ();
Fibonacci fib(atoi(argv[1]));
(ch == ALL) ? fib.show_all() : fib.show_number();

return 0;
}


--
=====================================
Alex Vinokur
mailto:ale...@connect.to
http://mathforum.org/library/view/10978.html
news://news.gmane.org/gmane.comp.lang.c++.perfometer
=====================================

Alex Vinokur

unread,
Oct 19, 2003, 2:38:41 PM10/19/03
to

"Alex Vinokur" <ale...@bigfoot.com> wrote in message news:bmtoqa$pt6bk$1...@ID-79865.news.uni-berlin.de...

> // ###########################################
> // [C++] Computing very long Fibonacci numbers
> // ###########################################
>
[snip]

Sorry, the algorithm in the original message (http://groups.google.com/groups?selm=bmtoqa%24pt6bk%241%40ID-79865.news.uni-berlin.de)
contains bug.

Valid algorithm can be seen at http://alexvn.freeservers.com/s1/fibonacci.html

Alex Vinokur

unread,
Oct 20, 2003, 5:28:18 AM10/20/03
to

"Alex Vinokur" <ale...@bigfoot.com> wrote in message news:bmulob$r6176$1...@ID-79865.news.uni-berlin.de...

>
> "Alex Vinokur" <ale...@bigfoot.com> wrote in message news:bmtoqa$pt6bk$1...@ID-79865.news.uni-berlin.de...
> > // ###########################################
> > // [C++] Computing very long Fibonacci numbers
> > // ###########################################
> >
> [snip]
>
> Sorry, the algorithm in the original message
(http://groups.google.com/groups?selm=bmtoqa%24pt6bk%241%40ID-79865.news.uni-berlin.de)
> contains bug.
>
[snip]

Here is updated version of the algorithm.

// ###########################################
// [C++] Computing very long Fibonacci numbers
// ###########################################

#include <assert.h>


#include <string>
#include <sstream>
#include <vector>
#include <iostream>

#include <iomanip>
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 BigInt operator+ (const BigInt& lhs_i, const BigInt& rhs_i);

friend ostream& operator<< (ostream& o, const BigInt& instance_i);

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

static void Set_Full_Base ();

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 () {}

};


// --------------
inline BigInt operator+ (const BigInt & lhs_i, const BigInt& rhs_i)
{
BigInt ret;

const ulong max_size = MAX_VALUE (lhs_i.units_.size (), rhs_i.units_.size ());
ulong value;
ulong head = 0;

for (ulong i = 0; i < max_size; i++)
{
ASSERT (head < MAX_UNIT_VALUE);

value = ((i < lhs_i.units_.size ()) ? lhs_i.units_ [i] : 0)
+ ((i < rhs_i.units_.size ()) ? rhs_i.units_ [i] : 0)
+ head;

ret.units_.push_back(value%(lhs_i.base_s));

ASSERT (ret.units_ [ret.units_.size () - 1] < lhs_i.base_s);

head = value/(lhs_i.base_s);
}

ASSERT (ret.units_.size () == max_size);

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_ [i]
<< 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_ [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;
}


Alex Vinokur

unread,
Oct 25, 2003, 5:37:29 AM10/25/03
to
// ###########################################
// [C++] Computing very long Fibonacci numbers
// Version 2.2
// -------------------------------------------
// Created by Alex Vinokur
// http://up.to/alexvn
// ###########################################

#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::operator+ (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));

Alex Vinokur

unread,
Oct 25, 2003, 5:38:38 AM10/25/03
to
// ###########################################
// [C++] Computing very long Fibonacci numbers
// Version 2.3

// -------------------------------------------
// Created by Alex Vinokur
// http://up.to/alexvn
// ###########################################

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

};

};

}

cout << oss.str();
}


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

Alex Vinokur

unread,
Oct 27, 2003, 7:33:12 AM10/27/03
to
// ###########################################
// [C++] Computing very long Fibonacci numbers
// Version 2.4

// -------------------------------------------
// Created by Alex Vinokur
// http://up.to/alexvn
// ###########################################

#include <stdlib.h>


#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 BASE1 10
#define BASE2 1000000000 // BASE1 ** (BASE1 - 1)

#if (BASE2 >= MAX_UNIT_VALUE)
#error Compilation Error-1 : (BASE2 >= MAX_UNIT_VALUE)
#endif

#if (!(BASE1 * (BASE2/BASE1 + 1) < MAX_UNIT_VALUE))
#error Compilation Error-2 : (!(BASE1 * (BASE2/BASE1 + 1) < MAX_UNIT_VALUE))
#endif


typedef unsigned int uint;
typedef unsigned long ulong;

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

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

public :
BigInt (ulong unit_i)
{
ASSERT (unit_i < BASE2);
units_.push_back (unit_i);
}

BigInt (BigInt big1_i, BigInt big2_i)
{
const ulong max_size = MAX_VALUE (big1_i.units_.size (), big2_i.units_.size ());

big1_i.units_.resize(max_size);
big2_i.units_.resize(max_size);
units_.resize(max_size);

head_s = 0;
transform (big1_i.units_.begin(), big1_i.units_.end(), big2_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/BASE2;
return (value%BASE2);
}

};


// --------------
inline ostream& operator<< (ostream& os, const BigInt& ins_i)
{
ASSERT (!ins_i.units_.empty ());

for (ulong i = (ins_i.units_.size () - 1); i; --i)
{
os << ins_i.units_ [i] << setw (BASE1 - 1) << setfill ('0');
}
return os << ins_i.units_ [0];
}


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

public :
void show_all_numbers () const;
void show_last_number () const;
void show_number (ulong n_i);

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_numbers () const
{
ostringstream oss;

for (uint i = 0; i < fibs_.size (); ++i)


{
oss << "Fib [" << i << "] = " << fibs_ [i] << "\n";
}
cout << oss.str();
}


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

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

cout << oss.str();
}

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

if (!(n_i < fibs_.size())) get_number (n_i);

oss << "Fib [" << n_i << "] = " << fibs_[n_i] << "\n";

cout << oss.str();
}

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

// ==============================
#define ALL_FIBS "all"

#define TH_FIB "th"
#define SOME_FIBS "some"
#define RAND_FIBS "rand"

#define MAX_RAND_FIB 25000

// ---------------------
void usage (char **argv)
{
cerr << "USAGE : "
<< endl

<< " "
<< argv[0]
<< " "
<< ALL_FIBS
<< " <N> ---> Fibonacci [0 - N]"
<< endl

<< " "
<< argv[0]
<< " "
<< TH_FIB
<< " <N> ---> Fibonacci [N]"
<< endl

<< " "
<< argv[0]
<< " "
<< SOME_FIBS
<< " <N1> [<N2> ...] ---> Fibonacci [N1], Fibonacci [N2], ..."
<< endl

<< " "
<< argv[0]
<< " "
<< RAND_FIBS << " <K> ---> K random Fibonacci numbers ( < "
<< MAX_RAND_FIB << " )"
<< endl;
}


// ---------------------
string check (int argc, char **argv)
{
if (argc < 3) return string();

const string str (argv[1]);
if (
(str == ALL_FIBS)
||
(str == TH_FIB)
||
(str == SOME_FIBS)
||
(str == RAND_FIBS)
)
{
return str;
}
return string();

}


// ---------------------


int main (int argc, char **argv)
{

const string option (check (argc, argv));
if (option.empty())
{
usage (argv);
return 1;
}

const uint N = atoi (argv[2]);

if (option == ALL_FIBS) Fibonacci(N).show_all_numbers();
if (option == TH_FIB) Fibonacci(N).show_last_number();

if (option == RAND_FIBS)
{
Fibonacci fib;
for (uint i = 0; i < N; i++) fib.show_number (rand()%MAX_RAND_FIB);
}

if (option == SOME_FIBS)
{
Fibonacci fib;
for (int i = 2; i < argc; i++) fib.show_number (atoi(argv[i]));

Alex Vinokur

unread,
Oct 29, 2003, 12:11:24 AM10/29/03
to
// ###########################################
// [C++] Computing very long Fibonacci numbers
// Version 2.5

// -------------------------------------------
// Created by Alex Vinokur
// http://up.to/alexvn
// ###########################################

#include <stdlib.h>


#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 BASE1 10
#define BASE2 1000000000 // BASE1 ** (BASE1 - 1)

#if (BASE2 >= MAX_UNIT_VALUE)
#error Compilation Error-1 : (BASE2 >= MAX_UNIT_VALUE)
#endif

#if (!(BASE1 * (BASE2/BASE1 + 1) < MAX_UNIT_VALUE))
#error Compilation Error-2 : (!(BASE1 * (BASE2/BASE1 + 1) < MAX_UNIT_VALUE))
#endif

typedef unsigned int uint;
typedef unsigned long ulong;

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

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

public :


BigInt (ulong unit_i)
{
ASSERT (unit_i < BASE2);
units_.push_back (unit_i);
}

BigInt (BigInt big1_i, BigInt big2_i)
{
const ulong max_size = MAX_VALUE (big1_i.units_.size (), big2_i.units_.size ());

big1_i.units_.resize(max_size);
big2_i.units_.resize(max_size);
units_.resize(max_size);

head_s = 0;
transform (big1_i.units_.begin(), big1_i.units_.end(), big2_i.units_.begin(), units_.begin(), *this);

if (head_s) units_.push_back (head_s);

}

ulong operator() (const ulong n1, const ulong n2)
{
const ulong value = n1 + n2 + head_s;


head_s = value/BASE2;
return (value%BASE2);
}

};


// --------------
inline ostream& operator<< (ostream& os, const BigInt& ins_i)
{
ASSERT (!ins_i.units_.empty ());

for (ulong i = (ins_i.units_.size () - 1); i; --i)
{

os << ins_i.units_ [i] << setw (BASE1 - 1) << setfill ('0');
}
return os << ins_i.units_ [0];
}


// ============
class Fibonacci
// ============


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

public :


void show_all_numbers () const;
void show_last_number () const;
void show_number (ulong n_i);

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_numbers () const
{
ostringstream oss;

for (uint i = 0; i < fibs_.size (); ++i)


{
oss << "Fib [" << i << "] = " << fibs_ [i] << "\n";
}
cout << oss.str();
}


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

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

cout << oss.str();
}

// -----------------------


void Fibonacci::show_number (ulong n_i)
{
ostringstream oss;

if (!(n_i < fibs_.size())) get_number (n_i);

oss << "Fib [" << n_i << "] = " << fibs_[n_i] << "\n";

cout << oss.str();
}

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


// ==============================
#define ALL_FIBS "all"

#define TH_FIB "th"
#define SOME_FIBS "some"
#define RAND_FIBS "rand"

#define MAX_RAND_FIB 25000

#define SETW1 4

// ---------------------
void usage (char **argv)
{
cerr << "USAGE : "
<< endl

<< " "
<< argv[0]
<< " "
<< setw (SETW1)
<< std::left
<< ALL_FIBS
<< " <N> ---> Fibonacci [0 - N]"
<< endl

<< " "
<< argv[0]
<< " "
<< std::left
<< setw (SETW1)


<< TH_FIB
<< " <N> ---> Fibonacci [N]"
<< endl

<< " "
<< argv[0]
<< " "
<< std::left
<< setw (SETW1)


<< SOME_FIBS
<< " <N1> [<N2> ...] ---> Fibonacci [N1], Fibonacci [N2], ..."
<< endl

<< " "
<< argv[0]
<< " "
<< std::left
<< setw (SETW1)
<< RAND_FIBS
<< " <K> [<M>] ---> K random Fibonacci numbers ( < M; Default = "
<< MAX_RAND_FIB
<< " )"
<< endl;
}


// ---------------------
string check (int argc, char **argv)
{
if (argc < 3) return string();

const string str (argv[1]);
if (
(str == ALL_FIBS)
||
(str == TH_FIB)
||
(str == SOME_FIBS)
||
(str == RAND_FIBS)
)
{
return str;
}
return string();

}


// ---------------------


int main (int argc, char **argv)
{

const string option (check (argc, argv));
if (option.empty())
{
usage (argv);
return 1;
}

const uint N = atoi (argv[2]);

if (option == ALL_FIBS)
{
Fibonacci fib(N);
fib.show_all_numbers();
}

if (option == TH_FIB)
{
Fibonacci fib(N);
fib.show_last_number();
}

if (option == SOME_FIBS)
{
Fibonacci fib;
for (int i = 2; i < argc; i++) fib.show_number (atoi(argv[i]));
}

if (option == RAND_FIBS)
{
const int max_rand_fib = (argc == 3) ? MAX_RAND_FIB : atoi (argv[3]);
Fibonacci fib;
for (uint i = 0; i < N; i++) fib.show_number (rand()%max_rand_fib);

Alex Vinokur

unread,
Nov 3, 2003, 12:04:45 AM11/3/03
to
// ###########################################
// [C++] Computing very long Fibonacci numbers
// Version 2.5.1 (with performance test)

// -------------------------------------------
// Created by Alex Vinokur
// http://up.to/alexvn
// ###########################################

#include <cstdlib>
#include <cassert>

big1_i.units_.resize(max_size);
big2_i.units_.resize(max_size);
units_.resize(max_size);

if (head_s) units_.push_back (head_s);

}

};

};

}

cout << oss.str();
}

cout << oss.str();
}

#define MAX_RAND_FIB 25000

#define SETW1 4

}


// ---------------------
#include <time.h>


int main (int argc, char **argv)
{
const string option (check (argc, argv));
if (option.empty())
{
usage (argv);
return 1;
}

const uint N = atoi (argv[2]);

const clock_t clock_start = clock();
assert (clock_start != clock_t (-1));

if (option == ALL_FIBS)
{
Fibonacci fib(N);
fib.show_all_numbers();
}

if (option == TH_FIB)
{
Fibonacci fib(N);
fib.show_last_number();
}

if (option == SOME_FIBS)
{
Fibonacci fib;
for (int i = 2; i < argc; i++) fib.show_number (atoi(argv[i]));
}

if (option == RAND_FIBS)
{
const int max_rand_fib = (argc == 3) ? MAX_RAND_FIB : atoi (argv[3]);
Fibonacci fib;
for (uint i = 0; i < N; i++) fib.show_number (rand()%max_rand_fib);
}

const clock_t clock_end = clock();
assert (clock_end != clock_t (-1));

cerr << "CPU time used : " << (double (clock_end - clock_start)/CLOCKS_PER_SEC) << " sec" << endl;

0 new messages