[C++] Computing very long Fibonacci numbers
Alex Vinokur
// [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
"Alex Vinokur" <ale...@bigfoot.com> wrote in message news:bmtoqa$pt6bk$1...@ID-79865.news.uni-berlin.de...
> // ###########################################
> // [C++] Computing very long Fibonacci numbers
> // ###########################################
>
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
"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.
>
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
// [C++] Computing very long Fibonacci numbers
// -------------------------------------------
// 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
// [C++] Computing very long Fibonacci numbers
// -------------------------------------------
// 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
// [C++] Computing very long Fibonacci numbers
// -------------------------------------------
// 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
// [C++] Computing very long Fibonacci numbers
// -------------------------------------------
// 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
// [C++] Computing very long Fibonacci numbers
// -------------------------------------------
// 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;