1 // ###########################################
2 // [C++] Computing very long Fibonacci numbers
3 // Version 2.5.1 (with performance test)
4 // -------------------------------------------
5 // Created by Alex Vinokur
7 // ###########################################
9 // http://groups.google.com/groups?selm=bo4nls%2417vfq6%241%40ID-79865.news.uni-berlin.de
23 #define MAX_VALUE(x,y) ((x) > (y) ? (x) : (y))
25 // #define ASSERT(x) assert(x)
28 #define MAX_UNIT_VALUE (ULONG_MAX >> 2)
30 #define BASE2 1000000000 // BASE1 ** (BASE1 - 1)
32 #if (BASE2 >= MAX_UNIT_VALUE)
33 #error Compilation Error-1 : (BASE2 >= MAX_UNIT_VALUE)
36 #if (!(BASE1 * (BASE2/BASE1 + 1) < MAX_UNIT_VALUE))
37 #error Compilation Error-2 : (!(BASE1 * (BASE2/BASE1 + 1) < MAX_UNIT_VALUE))
41 typedef unsigned int uint;
42 typedef unsigned long ulong;
48 friend ostream& operator<< (ostream& os, const BigInt& ins_i);
57 ASSERT (unit_i < BASE2);
58 units_.push_back (unit_i);
61 BigInt (BigInt big1_i, BigInt big2_i)
63 const ulong max_size = MAX_VALUE (big1_i.units_.size (), big2_i.units_.size ());
65 big1_i.units_.resize(max_size);
66 big2_i.units_.resize(max_size);
67 units_.resize(max_size);
70 transform (big1_i.units_.begin(), big1_i.units_.end(), big2_i.units_.begin(), units_.begin(), *this);
72 if (head_s) units_.push_back (head_s);
76 ulong operator() (const ulong n1, const ulong n2)
78 const ulong value = n1 + n2 + head_s;
86 inline ostream& operator<< (ostream& os, const BigInt& ins_i)
88 ASSERT (!ins_i.units_.empty ());
89 for (ulong i = (ins_i.units_.size () - 1); i; --i)
91 os << ins_i.units_ [i] << setw (BASE1 - 1) << setfill ('0');
92 } return os << ins_i.units_ [0];
101 vector<BigInt> fibs_;
102 BigInt get_number (uint n_i = 0);
105 void show_all_numbers () const;
106 void show_last_number () const;
107 void show_number (ulong n_i);
109 Fibonacci (uint n_i = 0) { get_number (n_i); }
115 // -----------------------
116 BigInt Fibonacci::get_number (uint n_i)
118 fibs_.reserve(n_i + 1);
119 const uint cur_size = fibs_.size ();
121 for (uint i = cur_size; i <= n_i; ++i)
126 fibs_.push_back (BigInt(0));
130 if (fibs_.empty ()) fibs_.push_back (BigInt (0));
131 fibs_.push_back(BigInt (1));
135 fibs_.push_back (BigInt (get_number (i - 2), get_number (i - 1)));
140 ASSERT (n_i < fibs_.size());
146 // -----------------------
147 void Fibonacci::show_all_numbers () const
151 for (uint i = 0; i < fibs_.size (); ++i)
153 oss << "Fib [" << i << "] = " << fibs_ [i] << "\n";
158 // -----------------------
159 void Fibonacci::show_last_number () const
163 oss << "Fib [" << (fibs_.size() - 1) << "] = " << fibs_.back() << "\n";
170 // -----------------------
171 void Fibonacci::show_number (ulong n_i)
175 if (!(n_i < fibs_.size())) get_number (n_i);
177 oss << "Fib [" << n_i << "] = " << fibs_[n_i] << "\n";
182 // -------------------
183 ulong BigInt::head_s (0);
188 // ==============================
189 #define ALL_FIBS "all"
191 #define SOME_FIBS "some"
192 #define RAND_FIBS "rand"
194 #define MAX_RAND_FIB 25000
198 // ---------------------
199 void usage (char **argv)
211 << " <N> ---> Fibonacci [0 - N]"
220 << " <N> ---> Fibonacci [N]"
229 << " <N1> [<N2> ...] ---> Fibonacci [N1], Fibonacci [N2], ..."
238 << " <K> [<M>] ---> K random Fibonacci numbers ( < M; Default = "
245 // ---------------------
246 string check (int argc, char **argv)
248 if (argc < 3) return string();
250 const string str (argv[1]);
268 // ---------------------
270 int main (int argc, char **argv)
272 string option (check (argc, argv));
274 if (option.empty()) {
278 #ifdef SMALL_PROBLEM_SIZE
287 if (option == ALL_FIBS)
290 fib.show_all_numbers();
293 if (option == TH_FIB)
296 fib.show_last_number();
299 if (option == SOME_FIBS)
302 for (int i = 2; i < argc; i++) fib.show_number (atoi(argv[i]));
305 if (option == RAND_FIBS)
307 const int max_rand_fib = (argc == 3) ? MAX_RAND_FIB : atoi (argv[3]);
309 for (uint i = 0; i < N; i++) fib.show_number (rand()%max_rand_fib);