Add JetStream to PerformanceTests
[WebKit-https.git] / PerformanceTests / JetStream / simple / bigfib.cpp
1 // ###########################################
2 // [C++] Computing very long Fibonacci numbers
3 //       Version 2.5.1 (with performance test)
4 // -------------------------------------------
5 // Created by Alex Vinokur
6 // http://up.to/alexvn
7 // ###########################################
8
9 // http://groups.google.com/groups?selm=bo4nls%2417vfq6%241%40ID-79865.news.uni-berlin.de
10
11 #include <climits>
12 #include <cstdlib>
13 #include <cassert>
14 #include <string>
15 #include <sstream>
16 #include <vector>
17 #include <iostream>
18 #include <iomanip>
19 #include <algorithm>
20 using namespace std;
21
22
23 #define MAX_VALUE(x,y)  ((x) > (y) ? (x) : (y))
24 #define ASSERT(x)
25 // #define ASSERT(x)    assert(x)
26
27
28 #define MAX_UNIT_VALUE  (ULONG_MAX >> 2)
29 #define BASE1  10
30 #define BASE2  1000000000   // BASE1 ** (BASE1 - 1)
31
32 #if (BASE2 >= MAX_UNIT_VALUE)
33 #error Compilation Error-1 : (BASE2 >= MAX_UNIT_VALUE)
34 #endif
35
36 #if (!(BASE1 * (BASE2/BASE1 + 1) < MAX_UNIT_VALUE))
37 #error Compilation Error-2 : (!(BASE1 * (BASE2/BASE1 + 1) < MAX_UNIT_VALUE))
38 #endif
39
40
41 typedef unsigned int  uint;
42 typedef unsigned long ulong;
43
44 // =========
45 class BigInt
46 // =========
47 {
48 friend ostream& operator<< (ostream& os, const BigInt& ins_i);
49
50   private :
51     static ulong  head_s;
52     vector<ulong> units_;
53
54   public :
55     BigInt (ulong unit_i)
56     {
57       ASSERT (unit_i < BASE2);
58       units_.push_back (unit_i);
59     }
60
61     BigInt (BigInt big1_i, BigInt big2_i)
62     {
63       const ulong max_size = MAX_VALUE (big1_i.units_.size (), big2_i.units_.size ());
64
65       big1_i.units_.resize(max_size);
66       big2_i.units_.resize(max_size);
67       units_.resize(max_size);
68
69       head_s = 0;
70       transform (big1_i.units_.begin(), big1_i.units_.end(), big2_i.units_.begin(), units_.begin(), *this);
71
72       if (head_s) units_.push_back (head_s);
73
74     }
75
76     ulong operator() (const ulong n1, const ulong n2)
77     {
78       const ulong value = n1 + n2 + head_s;
79       head_s = value/BASE2;
80       return (value%BASE2);
81     } 
82 };
83
84
85 // --------------
86 inline ostream& operator<< (ostream& os, const BigInt& ins_i)
87 {
88   ASSERT (!ins_i.units_.empty ());
89   for (ulong i = (ins_i.units_.size () - 1); i; --i)
90   {
91     os << ins_i.units_ [i] << setw (BASE1 - 1) << setfill ('0');
92   } return os << ins_i.units_ [0];
93 }
94
95
96 // ============
97 class Fibonacci
98 // ============
99 {
100   private :
101     vector<BigInt>   fibs_;
102     BigInt           get_number (uint n_i = 0);
103
104   public :
105     void             show_all_numbers () const;
106     void             show_last_number () const;
107     void             show_number (ulong n_i);
108
109     Fibonacci (uint n_i = 0) { get_number (n_i); }
110     ~Fibonacci () {}
111
112 };
113
114
115 // -----------------------
116 BigInt Fibonacci::get_number (uint n_i)
117 {
118 fibs_.reserve(n_i + 1);
119 const uint cur_size = fibs_.size ();
120
121   for (uint i = cur_size; i <= n_i; ++i)
122   {
123     switch (i)
124     {
125       case 0 :
126         fibs_.push_back (BigInt(0));
127         break;
128
129       case 1 :
130         if (fibs_.empty ()) fibs_.push_back (BigInt (0));
131         fibs_.push_back(BigInt (1));
132         break;
133
134       default :
135         fibs_.push_back (BigInt (get_number (i - 2), get_number (i - 1)));
136         break;
137     }
138   }
139
140   ASSERT (n_i < fibs_.size());
141   return fibs_ [n_i];
142
143 }
144
145
146 // -----------------------
147 void Fibonacci::show_all_numbers () const
148 {
149 ostringstream   oss;
150
151   for (uint i = 0; i < fibs_.size (); ++i)
152   {
153     oss << "Fib [" << i << "] = " << fibs_ [i] << "\n";
154   } cout << oss.str();
155 }
156
157
158 // -----------------------
159 void Fibonacci::show_last_number () const
160 {
161 ostringstream   oss;
162
163   oss << "Fib [" << (fibs_.size() - 1) << "] = " << fibs_.back() << "\n";
164
165   cout << oss.str();
166 }
167
168
169
170 // -----------------------
171 void Fibonacci::show_number (ulong n_i)
172 {
173 ostringstream   oss;
174
175   if (!(n_i < fibs_.size())) get_number (n_i);
176
177   oss << "Fib [" << n_i << "] = " << fibs_[n_i] << "\n";
178
179   cout << oss.str();
180 }
181
182 // -------------------
183 ulong BigInt::head_s (0);
184
185
186
187
188 // ==============================
189 #define ALL_FIBS  "all"
190 #define TH_FIB    "th"
191 #define SOME_FIBS "some"
192 #define RAND_FIBS "rand"
193
194 #define MAX_RAND_FIB   25000
195
196 #define SETW1      4
197
198 // ---------------------
199 void usage (char **argv)
200 {
201   argv[0] = "bigfib";
202   cerr << "USAGE : "
203        << endl
204
205        << "  "
206        << argv[0]
207        << " "
208        << setw (SETW1)
209        << std::left
210        << ALL_FIBS
211        << " <N>              ---> Fibonacci [0 - N]"
212        << endl
213
214        << "  "
215        << argv[0]
216        << " "
217        << std::left
218        << setw (SETW1)
219        << TH_FIB
220        << " <N>              ---> Fibonacci [N]"
221        << endl
222
223        << "  "
224        << argv[0]
225        << " "
226        << std::left
227        << setw (SETW1)
228        << SOME_FIBS
229        << " <N1> [<N2> ...]  ---> Fibonacci [N1], Fibonacci [N2], ..."
230        << endl
231
232        << "  "
233        << argv[0]
234        << " "
235        << std::left
236        << setw (SETW1)
237        << RAND_FIBS
238        << " <K>  [<M>]       ---> K random Fibonacci numbers ( < M; Default = "
239        << MAX_RAND_FIB
240        << " )"
241        << endl;
242 }
243
244
245 // ---------------------
246 string check (int argc, char **argv)
247 {
248   if (argc < 3) return string();
249
250 const string str (argv[1]);
251   if (
252        (str == ALL_FIBS)
253        ||
254        (str == TH_FIB)
255        ||
256        (str == SOME_FIBS)
257        ||
258        (str == RAND_FIBS)
259      )
260   {
261     return str;
262   }
263   return string();
264
265 }
266
267
268 // ---------------------
269
270 int main (int argc, char **argv)
271 {
272   string option (check (argc, argv));
273   uint N;
274   if (option.empty()) {
275     // usage (argv);
276     // return 1;
277     option = TH_FIB;
278 #ifdef SMALL_PROBLEM_SIZE
279     N = 15000;
280 #else
281     N = 50000;
282 #endif
283   } else {
284     N = atoi (argv[2]);
285   }
286
287   if (option == ALL_FIBS)
288   {
289     Fibonacci fib(N);
290     fib.show_all_numbers();
291   }
292
293   if (option == TH_FIB)
294   {
295     Fibonacci fib(N);
296     fib.show_last_number();
297   }
298
299   if (option == SOME_FIBS)
300   {
301     Fibonacci fib;
302     for (int i = 2; i < argc; i++) fib.show_number (atoi(argv[i]));
303   }
304
305   if (option == RAND_FIBS)
306   {
307     const int max_rand_fib = (argc == 3) ? MAX_RAND_FIB : atoi (argv[3]);
308     Fibonacci fib;
309     for (uint i = 0; i < N; i++) fib.show_number (rand()%max_rand_fib);
310   }
311
312   return 0;
313 }
314
315
316