Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

Groups keyboard shortcuts have been updated

Dismiss

See shortcuts

Computing very long Fibonacci numbers

4 views

Skip to first unread message

Alex Vinokur

unread,

Dec 12, 2001, 7:59:36 AM12/12/01

-------------------------------------
Computing very long Fibonacci numbers
-------------------------------------
Language : C++
--------------------------------

1. Algorithm is based on using STL-vector.

2. Algorithm was used to compute Fibonacci[5,000,000] :
http://groups.google.com/groups?selm=an_466658577

http://library.wolfram.com/mathgroup/archive/1999/Apr/msg00296.html

http://groups.google.com/groups?selm=7fn3g7%248f3%241%40nnrp1.dejanews.com

http://library.wolfram.com/mathgroup/archive/1999/Apr/msg00435.html

====================================================
gpp : GNU C++ version 2.95.3 20010315/djgpp (release) (djgpp)
compiled by GNU C version 2.95.3 20010315/djgpp (release).
Windows98
====================================================

====================================================
============== List Of Program Files ===============

The algorithm contains the following files :
1. fib.h template classes
2. fib.c auxiliary functions
3. main.c main program
====================================================

#########################################################
=== File #1 of 3 : fib.h ================================
------------------- C++ code : BEGIN --------------------

// ==============================================================
//
// Copyright (c) 1999-2001 by Alex Vinokur. This work and all works
// derived from it may be copied and modified without any
// restrictions other than that a copy of this copyright notice
// must be included in any copy of this work or any derived work.
//
// ==============================================================
static char id_h[] = "@(#)Author ## "__FILE__" ::: Alex Vinokur";

// ##############################################################
// =============================
// Very Large Fibonacci Numbers
// =============================
//
// FILE : fib.h
//
// AUTHOR : Alex Vinokur
//
// DESCRIPTION :
// Template classes :
// - ClassDesirableLongInt
// - ClassTemplateFibonacci
// - ClassTemplateOneFibonacci
// - ClassDecUnitFibonacci
// - ClassDecUnitOneFibonacci
// - ClassHexUnitFibonacci
// - ClassHexUnitOneFibonacci
//
// DATE VERSION
// ---- -------
// Apr-22-1999 AVF 1.0
// Dec-12-2001 AVF 1.1
//
// ##############################################################

#ifndef __fib_H
#define __fib_H

//###===###===###===###===###===###===###===###===###===###

#include <assert.h>
#include <string>
#include <strstream>
#include <vector>
#include <iomanip>

//#######################################################
//##### 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& show_base_i (ios&)) const;
string getStrValue (ios& show_base_i (ios&)) const;
string getAllInfo (ios& show_base_i (ios&)) const;
uint getSize (ios& show_base_i (ios&)) 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& show_base_i(ios&)
) const
{
string ret_Value;
strstream tmp_strstream;

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--
)
{
tmp_strstream << show_base_i;
tmp_strstream << vector_unit_ [theIndex];
tmp_strstream << UNITS_Delimeter_CNS;
tmp_strstream << setw (EXPO) << setfill ('0');
}
tmp_strstream << show_base_i;
tmp_strstream << vector_unit_ [0];
}
else
{
tmp_strstream << "NoValue";
}

//====================================
//====================================
tmp_strstream << dec;
tmp_strstream << ends;
ret_Value = tmp_strstream.str(); tmp_strstream.rdbuf()->freeze (0);
return ret_Value;
}

//=====================
template <uint EXPO, uint UNIT_BASE>
string ClassDesirableLongInt<EXPO, UNIT_BASE>::getAllInfo (
ios& show_base_i (ios&)
) const
{
string ret_Value;
strstream tmp_strstream;
string stringValue = getStrValue(show_base_i);

tmp_strstream << stringValue;
tmp_strstream << ";";

tmp_strstream << "\t Size = ";
tmp_strstream << getSize_S (stringValue);
tmp_strstream << getValueComment (show_base_i);
tmp_strstream << ends;

ret_Value = tmp_strstream.str(); tmp_strstream.rdbuf()->freeze (0);

return ret_Value;
}

//=====================
template <uint EXPO, uint UNIT_BASE>
uint ClassDesirableLongInt<EXPO, UNIT_BASE>::getSize (
ios& show_base_i(ios&)
) 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& show_base_i(ios&)
) 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& show_base_i (ios&)) const;
string getAllSizes (ios& show_base_i (ios&)) 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#"
<< __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& show_base_i (ios&)
) const
{
string ret_Value;
strstream tmp_strstream;

for (uint i = 0; i < fib_vector_.size (); i++)
{
tmp_strstream << "Fib ["
<< i
<< "] = "
<< fib_vector_ [i].getAllInfo (show_base_i)
<< endl;
}
tmp_strstream << ends;
ret_Value = tmp_strstream.str(); tmp_strstream.rdbuf()->freeze (0);
//==========
return ret_Value;
} // string ClassTemplateFibonacci::getAllNumbers () const

//-----------------------
template <uint EXPO, uint UNIT_BASE>
string ClassTemplateFibonacci<EXPO, UNIT_BASE>::getAllSizes (
ios& show_base_i (ios&)
) const
{
string ret_Value;
strstream tmp_strstream;

for (uint i = 0; i < fib_vector_.size (); i++)
{
tmp_strstream << "Fib [" << i << "] : Size is\t "
<< fib_vector_ [i].getSize (show_base_i)
<< fib_vector_ [i].getValueComment (show_base_i)
<< endl;
}
tmp_strstream << ends;
ret_Value = tmp_strstream.str(); tmp_strstream.rdbuf()->freeze (0);
//==========
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#"
<< __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& show_base_i (ios&) = dec
);

void printOneFib (
ulong n_i,
const string& msg_i = string (),
ios& show_base_i (ios&) = dec
);

void printSomeFib (
const vector<ulong>& vect_i,
const string& msg_i = string (),
ios& show_base_i (ios&) = dec
);

int mainFib (int argc, char **argv);

//###===###===###===###===###===###===###===###===###===###
#endif // __fib_H

//###################################################
//############ END OF FILE ##########################
//###################################################

------------------- C++ code : END ----------------------
=== File #1 of 3 : fib.h ================================

#########################################################
=== File #2 of 3 : fib.c ================================

------------------- C++ code : BEGIN --------------------
// ==============================================================
//
// Copyright (c) 1999-2001 by Alex Vinokur. This work and all works
// derived from it may be copied and modified without any
// restrictions other than that a copy of this copyright notice
// must be included in any copy of this work or any derived work.
//
// ==============================================================
static char id[] = "@(#)Author ## "__FILE__" ::: Alex Vinokur";

// ##############################################################
// =============================
// Very Large Fibonacci Numbers
// =============================
//
// FILE : fib.c
//
// AUTHOR : Alex Vinokur
//
// DESCRIPTION :
// Functions :
// - stringIsNonnegativeNumber
// - printAllFib
// - printOneFib
// - printSomeFib
// - printErrorUsageMessage
// - argv_check
// - mainFib
//
// DATE VERSION
// ---- -------
// Apr-22-1999 AVF 1.0
// Dec-12-2001 AVF 1.1
//
// ##############################################################

#include "fib.h"

//###################################################
//############ CONSTANTS ############################
//###################################################
static const string all_num_option_CNS = "--all-num";
static const string size_only_option_CNS = "--size-only";

//###################################################
//############ FUNCTION #############################
//###################################################

//#####################################################
bool stringIsNonnegativeNumber (const string& string_i)
{
ASSERT (!string_i.empty ());
for (ulong theIndex= 0; theIndex < string_i.size (); theIndex++)
{
if (!isdigit (string_i [theIndex]))
{
return false;
}
}
return true;
} // bool stringIsNonnegativeNumber (const string& string_i)

//#####################################################
void printAllFib (
ulong n_i,
bool sizes_only_i,
const string& msg_i,
ios& show_base_i (ios&)
)
{
string print_string;
strstream tmp_strstream;
if (!msg_i.empty())
{
tmp_strstream << endl;
tmp_strstream << "################################" << endl;
tmp_strstream << "###" << "\t" << msg_i << endl;
tmp_strstream << "################################" << endl;
}

if (!sizes_only_i)
{
tmp_strstream << ClassFibonacci (n_i).getAllNumbers (show_base_i);
}
else
{
tmp_strstream << ClassFibonacci (n_i).getAllSizes (show_base_i);
}

tmp_strstream << endl;
tmp_strstream << ends;

print_string = tmp_strstream.str(); tmp_strstream.rdbuf()->freeze (0);

cout << print_string;

} // printAllFib

//#####################################################
void printOneFib (
ulong n_i,
const string& msg_i,
ios& show_base_i (ios&)
)
{
string print_string;
strstream tmp_strstream;
if (!msg_i.empty())
{
tmp_strstream << endl;
tmp_strstream << "################################" << endl;
tmp_strstream << "###" << "\t" << msg_i << endl;
tmp_strstream << "################################" << endl;
}
ClassOneFibonacci f1;

tmp_strstream << ""
<< "Fib#"
<< n_i
<< "\t = "
<< f1.getFibNumber (n_i).getAllInfo (show_base_i)
<< endl;
tmp_strstream << endl;
tmp_strstream << ends;

print_string = tmp_strstream.str(); tmp_strstream.rdbuf()->freeze (0);

cout << print_string;

} // printOneFib

//#####################################################
void printSomeFib (
const vector<ulong>& vect_i,
const string& msg_i,
ios& show_base_i (ios&)
)
{
string print_string;
strstream tmp_strstream;

if (!msg_i.empty())
{
tmp_strstream << endl;
tmp_strstream << "################################" << endl;
tmp_strstream << "###" << "\t" << msg_i << endl;
tmp_strstream << "################################" << endl;
}
ClassFibonacci f1;

for (uint theIndex = 0; theIndex < vect_i.size (); theIndex++)
{
tmp_strstream << ""
<< "Fib#"
<< vect_i [theIndex]
<< "\t = "
<< f1.getFibNumber (vect_i [theIndex]).getAllInfo(show_base_i)
<< endl;
} // for (uint theIndex = 0;

tmp_strstream << endl;

//====================
tmp_strstream << ends;

print_string = tmp_strstream.str(); tmp_strstream.rdbuf()->freeze (0);

cout << print_string;
} // printSomeFib

//#####################################################
//#####################################################
//#####################################################
void printErrorUsageMessage (
int argc,
char **argv
)
{
cout << endl
<< "FATAR ERROR!"
<< endl
<< "============"
<< endl
<< "USAGE : "
<< argv[0]
<< " "
<< all_num_option_CNS
<< " <nonnegative number>"
<< " ["
<< size_only_option_CNS
<< "]"
<< endl
<< " : "
<< argv[0]
<< " <nonnegative number> [<nonnegative number> [<nonnegative
number>] ...]"
<< endl;
}

//#####################################################
bool argv_check (
int argc,
char **argv,
ulong cur_index_i,
ulong& cur_numberValue_o
)
{

//============================
ASSERT (argc >= 2);
ASSERT (cur_index_i >= 1);

//============================
if (!stringIsNonnegativeNumber (string (argv[cur_index_i])))
{
printErrorUsageMessage (argc, argv);
cout << endl
<< "NOT NONNEGATIVE NUMBER : "
<< "argv ["
<< cur_index_i
<< "] = "
<< argv [cur_index_i]
<< endl;
return false;
}

cur_numberValue_o = strtoul (argv[cur_index_i], (char**)NULL, 10);
if (cur_numberValue_o == ULONG_MAX)
{
cout << endl
<< "FATAR ERROR!"
<< endl
<< "============"
<< endl
<< "TOO LARGE VALUE : "
<< "argv ["
<< cur_index_i
<< "] = "
<< argv [cur_index_i]
<< endl;
return false;
}
//=====================
return true;
} // bool argv_check (ulong cur_index_i)

//#####################################################
int mainFib (int argc, char **argv)
{

ulong cur_numberValue;
ulong cur_index;
vector<ulong> vect;
bool size_only_flag = false;

for (int i = 0; i < argc; i++)
{
if (argv[i] == size_only_option_CNS)
{
size_only_flag = true;
}
}

switch (argc)
{
case 0 :
assert (0);
break;

case 1 :
printErrorUsageMessage (argc, argv);
exit (1);
break; // unused

case 2 :
cur_index = 1;
if (!argv_check (argc, argv, cur_index, cur_numberValue))
{
exit (1);
}
printOneFib (cur_numberValue);
break;

case 3 :
case 4 :
if (argv [1] == all_num_option_CNS)
{
if (argc == 4)
{
if (!(argv [3] == size_only_option_CNS))
{
printErrorUsageMessage (argc, argv);
exit (1);
}
}

cur_index = 2;
if (!argv_check (argc, argv, cur_index, cur_numberValue))
{
exit (1);
}
printAllFib (cur_numberValue, size_only_flag);
break;
}

default :
for (int theIndex = 1; theIndex < argc; theIndex++)
{
cur_index = theIndex;
if (!argv_check (argc, argv, cur_index, cur_numberValue))
{
exit (1);
}
vect.push_back (cur_numberValue);
}
printSomeFib (vect);
break;

} // switch (argc)

//=================
return 0;
//=================
} // int mainFib (int argc, char **argv)

//###################################################
//############ END OF FILE ##########################
//###################################################

------------------- C++ code : END ----------------------
=== File #2 of 3 : fib.c ================================

#########################################################
=== File #3 of 3 : main.c ===============================
------------------- C++ code : BEGIN --------------------

// ##############################################################
// =============================
// Very Large Fibonacci Numbers
// =============================
//
// FILE : main.c
//
// AUTHOR : Alex Vinokur
//
// DESCRIPTION : Main program
//
// DATE VERSION
// ---- -------
// Apr-22-1999 AVF 1.0
// Dec-12-2001 AVF 1.1
//
// ##############################################################

#include "fib.h"

//###################################################
//###################################################
//###################################################
//==============================
int main (int argc, char **argv)
{
return mainFib (argc, argv);
}

//###################################################
//############ END OF FILE ##########################
//###################################################

------------------- C++ code : END ----------------------
=== File #3 of 3 : main.c ===============================

--------------- Running (sample) : BEGIN ----------------

> a.exe 12
Fib#12 = 144; Size = 3 (dec digits)

> a.exe 7 35 12 93 5
Fib#7 = 13; Size = 2 (dec digits)
Fib#35 = 9227465; Size = 7 (dec digits)
Fib#12 = 144; Size = 3 (dec digits)
Fib#93 = 12200160415121876738; Size = 20 (dec digits)
Fib#5 = 5; Size = 1 (dec digits)

> a.exe --all-num 12
Fib [0] = 0; Size = 1 (dec digits)
Fib [1] = 1; Size = 1 (dec digits)
Fib [2] = 1; Size = 1 (dec digits)
Fib [3] = 2; Size = 1 (dec digits)
Fib [4] = 3; Size = 1 (dec digits)
Fib [5] = 5; Size = 1 (dec digits)
Fib [6] = 8; Size = 1 (dec digits)
Fib [7] = 13; Size = 2 (dec digits)
Fib [8] = 21; Size = 2 (dec digits)
Fib [9] = 34; Size = 2 (dec digits)
Fib [10] = 55; Size = 2 (dec digits)
Fib [11] = 89; Size = 2 (dec digits)
Fib [12] = 144; Size = 3 (dec digits)

> a.exe --all-num 12 --size-only
Fib [0] : Size is 1 (dec digits)
Fib [1] : Size is 1 (dec digits)
Fib [2] : Size is 1 (dec digits)
Fib [3] : Size is 1 (dec digits)
Fib [4] : Size is 1 (dec digits)
Fib [5] : Size is 1 (dec digits)
Fib [6] : Size is 1 (dec digits)
Fib [7] : Size is 2 (dec digits)
Fib [8] : Size is 2 (dec digits)
Fib [9] : Size is 2 (dec digits)
Fib [10] : Size is 2 (dec digits)
Fib [11] : Size is 2 (dec digits)
Fib [12] : Size is 3 (dec digits)

--------------- Running (sample) : END ------------------

===========================
Alex Vinokur
mailto:ale...@bigfoot.com
mailto:ale...@dr.com
http://up.to/alexvn
http://go.to/alexv_math
===========================

0 new messages