// ############################################
// =============================
// Very Large Fibonacci Numbers
// =============================
//
// AUTHOR : Alex Vinokur
// alexvn@go.to, alexv@hitechclub.com
// http://up.to/alexvn
//
// 2002-12-05
//
// #############################################
// ------------
// FILE : fib.h
// ------------
#ifndef __fib_H
#define __fib_H
// ###===###===###===###===###===###===###===###===###===###
#include <assert.h>
#include <string>
#include <sstream>
#include <vector>
#include <iostream>
#include <iomanip>
#include <bits/ios_base.h>
using namespace std;
// #######################################################
// ##### PART#1 : TYPEDEFs & DEFINES & CONSTANTS #########
// #######################################################
#define MAX_VALUE(x,y) ((x) > (y) ? (x) : (y))
#define ASSERT(x) assert (x)
#define INFO_MESSAGE
typedef unsigned int uint;
typedef unsigned long ulong;
const ulong Max_Unit_Value_CNS = (ULONG_MAX >> 2);
const uint INFO_period_CNS = 10000;
static const string UNITS_Delimeter_CNS = "";
// #######################################################
// ##### PART#2 : DECLARATIONS ###########################
// #######################################################
template <uint EXPO, uint UNIT_BASE>
class ClassDesirableLongInt;
template <uint EXPO, uint UNIT_BASE>
ClassDesirableLongInt<EXPO, UNIT_BASE> operator+ (
const ClassDesirableLongInt<EXPO, UNIT_BASE>&left_i,
const ClassDesirableLongInt<EXPO, UNIT_BASE>&right_i
);
// #######################################################
// ##### PART#3 : The ClassDesirableLongInt class ########
// #######################################################
// #############################
template <uint EXPO, uint UNIT_BASE>
class ClassDesirableLongInt
{
template <uint E1, uint U1>
friend ClassDesirableLongInt<E1, U1> operator+ (
const ClassDesirableLongInt<E1, U1>& left_i,
const ClassDesirableLongInt<E1, U1>& right_i
);
private :
ulong full_base_;
vector <ulong> vector_unit_;
public :
ClassDesirableLongInt ();
ClassDesirableLongInt (ulong unit_value_i);
ClassDesirableLongInt (
const ClassDesirableLongInt<EXPO, UNIT_BASE>& left_i,
const ClassDesirableLongInt<EXPO, UNIT_BASE>& right_i
);
~ClassDesirableLongInt () {}
void set_full_base ();
string getValueComment (ios_base& show_base_i (ios_base&)) const;
string getStrValue (ios_base& show_base_i (ios_base&)) const;
string getAllInfo (ios_base& show_base_i (ios_base&)) const;
uint getSize (ios_base& show_base_i (ios_base&)) const;
static uint getSize_S (const string& strValue_i);
uint getTotalUnits () const {return vector_unit_.size ();}
};
// =====================
template <uint EXPO, uint UNIT_BASE>
ClassDesirableLongInt<EXPO, UNIT_BASE> operator+ (
const ClassDesirableLongInt<EXPO, UNIT_BASE>&left_i,
const ClassDesirableLongInt<EXPO, UNIT_BASE>&right_i
)
{
ClassDesirableLongInt<EXPO, UNIT_BASE> ret_ClassDesirableLongInt_Value;
const ulong max_size_CNS = MAX_VALUE (
left_i.vector_unit_.size (),
right_i.vector_unit_.size ()
);
ulong cur_big_value;
ulong head = 0;
for (ulong theIndex = 0; theIndex < max_size_CNS; theIndex++)
{
ASSERT (head < Max_Unit_Value_CNS);
cur_big_value =
(
(theIndex < left_i.vector_unit_.size ()) ?
left_i.vector_unit_ [theIndex] : 0
)
+
(
(theIndex < right_i.vector_unit_.size ()) ?
right_i.vector_unit_ [theIndex] : 0
)
+
head;
// ------------------------
ret_ClassDesirableLongInt_Value.vector_unit_.push_back(cur_big_value%(left_i.full_base_));
ASSERT (
ret_ClassDesirableLongInt_Value.vector_unit_
[ret_ClassDesirableLongInt_Value.vector_unit_.size () - 1]
<
left_i.full_base_
);
// ------------------------
head = cur_big_value/(left_i.full_base_);
} // for (ulong theIndex = 0;
ASSERT (ret_ClassDesirableLongInt_Value.vector_unit_.size () == max_size_CNS);
if (head)
{
ret_ClassDesirableLongInt_Value.vector_unit_.push_back (head);
}
return ret_ClassDesirableLongInt_Value;
} // ClassDesirableLongInt<EXPO, UNIT_BASE> operator+
// =====================
// Constructor-0
template <uint EXPO, uint UNIT_BASE>
ClassDesirableLongInt<EXPO, UNIT_BASE>::ClassDesirableLongInt ()
{
set_full_base ();
}
// =====================
// Constructor-1
template <uint EXPO, uint UNIT_BASE>
ClassDesirableLongInt<EXPO, UNIT_BASE>::ClassDesirableLongInt (
ulong unit_value_i
)
{
set_full_base ();
if (!(unit_value_i < full_base_))
{
cout << "FATAL ERROR : Number Value = "
<< unit_value_i
<< " (too big)"
<< "; It must be less "
<< full_base_
<< "; "
<< __FILE__
<< ", #"
<< __LINE__
<< endl;
exit (1);
}
ASSERT (unit_value_i < full_base_);
vector_unit_.push_back (unit_value_i);
}
// =====================
// Constructor-2
template <uint EXPO, uint UNIT_BASE>
ClassDesirableLongInt<EXPO, UNIT_BASE>::ClassDesirableLongInt (
const ClassDesirableLongInt<EXPO, UNIT_BASE>&left_i,
const ClassDesirableLongInt<EXPO, UNIT_BASE>&right_i
)
{
set_full_base ();
(*this) = left_i + right_i;
}
// =====================
template <uint EXPO, uint UNIT_BASE>
string ClassDesirableLongInt<EXPO, UNIT_BASE>::getStrValue (
ios_base& show_base_i(ios_base&)
) const
{
string ret_Value;
ostringstream oss;
ASSERT ((show_base_i == dec) || (show_base_i == hex) || (show_base_i == oct));
// ------------
if (!vector_unit_.empty ())
{
for (ulong theIndex = (vector_unit_.size () - 1);
theIndex > 0;
theIndex--
)
{
oss << show_base_i;
oss << vector_unit_ [theIndex];
oss << UNITS_Delimeter_CNS;
oss << setw (EXPO) << setfill ('0');
}
oss << show_base_i;
oss << vector_unit_ [0];
}
else
{
oss << "NoValue";
}
// ------------
oss << dec;
oss << ends;
ret_Value = oss.str();
return ret_Value;
}
// =====================
template <uint EXPO, uint UNIT_BASE>
string ClassDesirableLongInt<EXPO, UNIT_BASE>::getAllInfo (
ios_base& show_base_i (ios_base&)
) const
{
string ret_Value;
ostringstream oss;
string stringValue (getStrValue(show_base_i));
oss << stringValue;
oss << ";";
oss << "\t Size = ";
oss << getSize_S (stringValue);
oss << getValueComment (show_base_i);
oss << ends;
ret_Value = oss.str();
return ret_Value;
}
// =====================
template <uint EXPO, uint UNIT_BASE>
uint ClassDesirableLongInt<EXPO, UNIT_BASE>::getSize (
ios_base& show_base_i(ios_base&)
) const
{
return getSize_S (getStrValue (show_base_i));
}
// =====================
// static
template <uint EXPO, uint UNIT_BASE>
uint ClassDesirableLongInt<EXPO, UNIT_BASE>::getSize_S (
const string& strValue_i
)
{
int counter = 0;
string::size_type ret_index;
string cur_substr = strValue_i;
if (!UNITS_Delimeter_CNS.empty ())
{
while (!((ret_index = cur_substr.find (UNITS_Delimeter_CNS)) == string::npos))
{
counter++;
cur_substr = cur_substr.substr (ret_index + 1);
} // while
}
return (strValue_i.size () - counter*UNITS_Delimeter_CNS.size ());
}
// =====================
template <uint EXPO, uint UNIT_BASE>
string ClassDesirableLongInt<EXPO, UNIT_BASE>::getValueComment (
ios_base& show_base_i(ios_base&)
) const
{
string ret_Value;
ASSERT ((show_base_i == dec) || (show_base_i == hex) || (show_base_i == oct));
ret_Value += " (";
if (show_base_i == hex) ret_Value += "hex";
if (show_base_i == oct) ret_Value += "oct";
if (show_base_i == dec) ret_Value += "dec";
ret_Value += " digits)";
return ret_Value;
}
// =====================
template <uint EXPO, uint UNIT_BASE>
void ClassDesirableLongInt<EXPO, UNIT_BASE>::set_full_base ()
{
ASSERT (EXPO > 1);
ASSERT ((UNIT_BASE == 8) || (UNIT_BASE == 10) || (UNIT_BASE == 16));
// ------------------
full_base_ = 1;
for (ulong theIndex = 1; theIndex <= EXPO; theIndex++)
{
full_base_ *= UNIT_BASE;
if ((full_base_ >= Max_Unit_Value_CNS) || (full_base_ == 0))
{
cout << "FATAL ERROR : EXPO Value = "
<< EXPO
<< " (too big)"
<< "; It must be less "
<< theIndex
<< " (Note! UNIT_BASE == "
<< UNIT_BASE
<< ")"
<< __FILE__
<< ", #"
<< __LINE__
<< endl;
exit (1);
}
ASSERT (UNIT_BASE * ((full_base_/UNIT_BASE) + 1) < Max_Unit_Value_CNS);
ASSERT (full_base_ != 0);
}
}
// #######################################################
// ##### PART#4 : The ClassTemplateFibonacci class #######
// #######################################################
// =====================
template <uint EXPO, uint UNIT_BASE>
class ClassTemplateFibonacci
{
private :
vector< ClassDesirableLongInt<EXPO, UNIT_BASE> > fib_vector_;
protected :
ClassTemplateFibonacci (int n_i = 0);
public :
string getAllNumbers (ios_base& show_base_i (ios_base&)) const;
string getAllSizes (ios_base& show_base_i (ios_base&)) const;
virtual ClassDesirableLongInt<EXPO, UNIT_BASE> getFibNumber(int n_i = 0);
virtual ~ClassTemplateFibonacci () {}
};
// -----------------------
// Constructor
template <uint EXPO, uint UNIT_BASE>
ClassTemplateFibonacci<EXPO, UNIT_BASE>::ClassTemplateFibonacci (int n_i)
{
getFibNumber (n_i);
}
// -----------------------
template <uint EXPO, uint UNIT_BASE>
ClassDesirableLongInt<EXPO, UNIT_BASE> ClassTemplateFibonacci<EXPO, UNIT_BASE>::getFibNumber (int n_i)
{
const uint cur_size = fib_vector_.size ();
// ------------------
if (n_i < 0)
{
cout << "FATAL ERROR : n = "
<< n_i
<< "; "
<< __FILE__
<< ", #"
<< __LINE__
<< endl;
exit (1);
}
for (uint i = cur_size; i <= n_i; i++)
{
switch (i)
{
case 0 :
fib_vector_.push_back (ClassDesirableLongInt<EXPO, UNIT_BASE>(0));
break;
case 1 :
if (fib_vector_.empty ())
{
fib_vector_.push_back (ClassDesirableLongInt<EXPO, UNIT_BASE> (0));
}
fib_vector_.push_back(ClassDesirableLongInt<EXPO, UNIT_BASE> (1));
break;
default :
fib_vector_.push_back (
ClassDesirableLongInt<EXPO, UNIT_BASE> (
getFibNumber (i - 2),
getFibNumber (i - 1)
//fib_vector_ [i - 2],
//fib_vector_ [i - 1]
)
);
break;
} // switch (n_i)
// ------------------
#ifdef INFO_MESSAGE
if ((i%INFO_period_CNS == 0) & (i > 0))
{
cerr << "INFO"
<< " ("
<< __FILE__
<< ", #"
<< __LINE__
<< ")"
<< " : "
<< " Fib#"
<< i
<< " computed; Total Units = "
<< fib_vector_ [fib_vector_.size () - 1].getTotalUnits ()
<< endl;
}
#endif
// ------------------
} // for (int i = cur_size; i <= n_i; i++)
return fib_vector_ [n_i];
} // ulong ClassTemplateFibonacci::getFibNumber (int n_i)
// -----------------------
template <uint EXPO, uint UNIT_BASE>
string ClassTemplateFibonacci<EXPO, UNIT_BASE>::getAllNumbers (
ios_base& show_base_i (ios_base&)
) const
{
string ret_Value;
ostringstream oss;
for (uint i = 0; i < fib_vector_.size (); i++)
{
oss << "Fib ["
<< i
<< "] = "
<< fib_vector_ [i].getAllInfo (show_base_i)
<< endl;
}
oss << ends;
ret_Value = oss.str();
return ret_Value;
} // string ClassTemplateFibonacci::getAllNumbers () const
// -----------------------
template <uint EXPO, uint UNIT_BASE>
string ClassTemplateFibonacci<EXPO, UNIT_BASE>::getAllSizes (
ios_base& show_base_i (ios_base&)
) const
{
string ret_Value;
ostringstream oss;
for (uint i = 0; i < fib_vector_.size (); i++)
{
oss << "Fib [" << i << "] : Size is\t "
<< fib_vector_ [i].getSize (show_base_i)
<< fib_vector_ [i].getValueComment (show_base_i)
<< endl;
}
oss << ends;
ret_Value = oss.str();
return ret_Value;
} // string ClassTemplateFibonacci::getAllSizes () const
// #######################################################
// ##### PART#5 : The ClassTemplateOneFibonacci class ####
// #######################################################
// =====================
template <uint EXPO, uint UNIT_BASE>
class ClassTemplateOneFibonacci : public ClassTemplateFibonacci<EXPO, UNIT_BASE>
{
private :
protected :
ClassTemplateOneFibonacci (int n_i = 0) :
ClassTemplateFibonacci<EXPO, UNIT_BASE> (n_i) {}
public :
ClassDesirableLongInt<EXPO, UNIT_BASE> getFibNumber (int n_i = 0);
~ClassTemplateOneFibonacci () {} };
// -----------------------
template <uint EXPO, uint UNIT_BASE>
ClassDesirableLongInt<EXPO, UNIT_BASE> ClassTemplateOneFibonacci<EXPO,
UNIT_BASE>::getFibNumber (int n_i)
{
vector < ClassDesirableLongInt<EXPO, UNIT_BASE> > one_vector_;
one_vector_.push_back (ClassDesirableLongInt<EXPO, UNIT_BASE> (0));
one_vector_.push_back (ClassDesirableLongInt<EXPO, UNIT_BASE> (1));
one_vector_.push_back (ClassDesirableLongInt<EXPO, UNIT_BASE> (0));
// ========================
if (n_i < 0)
{
cout << "FATAL ERROR : n = "
<< n_i
<< "; "
<< __FILE__
<< ", #"
<< __LINE__
<< endl;
exit (1);
}
// ------------------
for (int theIndex = 0; theIndex < n_i; theIndex++)
{
one_vector_.erase (one_vector_.begin ());;
one_vector_.push_back (one_vector_ [0] + one_vector_ [1]);
#ifdef INFO_MESSAGE
if ((theIndex%INFO_period_CNS == 0) & (theIndex > 0))
{
cerr << "INFO"
<< " ("
<< __FILE__
<< ", #"
<< __LINE__
<< ")"
<< " : "
<< " Fib#"
<< theIndex
<< " computed; Total Units = "
<< one_vector_ [2].getTotalUnits ()
<< endl;
}
#endif
}
// ------------------
return one_vector_ [2];
} // ulong ClassTemplateOneFibonacci::getFibNumber (int n_i)
// #######################################################
// ##### PART#6 : The ClassDecUnitFibonacci class ########
// #######################################################
// =====================
template <uint EXPO>
class ClassDecUnitFibonacci : public ClassTemplateFibonacci <EXPO, 10>
{
public :
ClassDecUnitFibonacci (int n_i = 0) :
ClassTemplateFibonacci<EXPO, 10> (n_i) {}
~ClassDecUnitFibonacci () {}
};
// ==========================
typedef ClassDecUnitFibonacci<9> ClassFibonacci;
// ==========================
// #######################################################
// ##### PART#7 : The ClassDecUnitOneFibonacci class #####
// #######################################################
// =====================
template <uint EXPO>
class ClassDecUnitOneFibonacci : public ClassTemplateOneFibonacci <EXPO, 10>
{
public :
ClassDecUnitOneFibonacci (int n_i = 0) :
ClassTemplateOneFibonacci<EXPO, 10> (n_i) {}
~ClassDecUnitOneFibonacci () {}
};
// ==========================
typedef ClassDecUnitOneFibonacci<9> ClassOneFibonacci;
// ==========================
// #######################################################
// ##### PART#8 : The ClassHexUnitFibonacci class ########
// #######################################################
// =====================
template <uint EXPO>
class ClassHexUnitFibonacci : public ClassTemplateFibonacci <EXPO, 16>
{
public :
ClassHexUnitFibonacci (int n_i = 0) :
ClassTemplateFibonacci<EXPO, 16> (n_i) {}
~ClassHexUnitFibonacci () {}
};
// #######################################################
// ##### PART#9 : The ClassHexUnitOneFibonacci class #####
// #######################################################
// =====================
template <uint EXPO> class ClassHexUnitOneFibonacci : public ClassTemplateOneFibonacci <EXPO, 16>
{
public :
ClassHexUnitOneFibonacci (int n_i = 0) :
ClassTemplateOneFibonacci<EXPO, 16> (n_i) {}
~ClassHexUnitOneFibonacci () {}
};
// #######################################################
// ##### PART#10 : FUNCTIONS #############################
// #######################################################
bool stringIsDigit (const string& string_i);
bool stringIsNonDigit (const string& string_i);
void printAllFib (
ulong n_i,
bool size_only_i = false,
const string& msg_i = string (),
ios_base& show_base_i (ios_base&) = dec
);
void printOneFib (
ulong n_i,
const string& msg_i = string (),
ios_base& show_base_i (ios_base&) = dec
);
void printSomeFib (
const vector<ulong>& vect_i,
const string& msg_i = string (),
ios_base& show_base_i (ios_base&) = dec
);
int mainFib (int argc, char **argv);
// ###===###===###===###===###===###===###===###===###===###
#endif // __fib_H
// ############ END OF FILE ############
