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