Fibonacci [5,000,000] contains 1044938 decimal digits
Alex Vinokur
Several large Fibonacci numbers were calculated using only
the well-known explicit formula:
Fib (0) = 0, Fib (1) = 1,
Fib (n) = Fib (n-1) + Fib (n-2), n >= 2
All the (decimal) digits of these numbers were obtained.
It was using the EXPLICIT Fibonacci formula and
computing ALL the large Fibonacci numbers digits
that were set as an object.
Using just EXPLICIT Fibonacci formula is not an imperative requirement.
But to get ALL digits of the large Fibonacci number is very advisable one.
//============================================================
In order to compute above-mentioned Fibonacci numbers
the special class titled DesirableLongInt was defined.
The are two versions of this class :
- first one based on the STL vector class
(vector<unsigned long int>);
- second one based on the STL basic_string class
(basic_string<unsigned long int>).
DesirableLongInt number contains as many digits as it requires
(at least 1,000,000 decimal digits). There is no need to think
of the calculation precision beforehand.
The bc utility (arbitrary precision arithmetic language) was also
used to calculate the Fibonacci numbers.
//============================================================
Here are the experiment results
Comparative table.
================================================================
| | About Fib [n] |
| |----------------------------------------------------|
| Index n | Decimal | Calculation time (hh:mm:ss) |
| | Digits |-----------------------------------------|
| | | DesirableLongInt | bc utility |
| | |----------------------------| |
| | | vector | basic_string | |
|--------------------------------------------------------------|
| 100000 | 20899 | 1:08.30 | 1:33.94 | 1:39.40 |
| 500000 | 104494 | 26:38.46 | 38:41.73 | 40:21.01 |
| 1000000 | 208988 | 1:42:43.78 | 2:35:08.71 | 2:39:51.56 |
| 5000000 | 1044938 | 43:00:17.66 | 63:34:31.07 | None |
================================================================
Conclusion. Although Fib[5,000,000] was calculated,
these methods are unacceptable to calculate Fib [1,000,000+]
because it takes too long time.
The question is, if is there any EXPLICIT method
that calculates ALL digits Fib [5,000,000+] and
takes acceptable time?
//============================================================
What was Fib [5,000,000] calculated for?
Here are some reasons.
A) It is always helpful to know what are the limits of
*our+computer* possibilities.
B) About Fib [5,000,000] itself. What to do with it?
The things needless today become necessary earlier
than we suppose.
C) About the methods of the large Fibonacci numbers calculation.
The (successful or unsuccessful) approach intended
to solve one problem are quite often adopted & adapted
to solve another ones.
D) So-called (n+1)-th reason, i.e., incomprehensible today.
Sometimes such reason is made known in the course of time.
Sometimes it isn't.
//============================================================
//#########################################################
//------------------- Compiler & System ------------------
g++ -v : gcc version egcs-2.91.57 19980901
(egcs-1.1 release)
uname -a : SunOS <nodename> 5.6 Generic_105181-11
sun4u sparc SUNW,Ultra-60-09
psrinfo -v : -> The sparc processor operates at 360 MHz
//---------------------------------------------------------
Thanks,
Alex
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Paul Lutus
digits Fib [5,000,000+] and takes acceptable time? >>
Yes, a trivial method. You compute the entire sequence of numbers and store
each result as the sequence proceeds. The individual numbers are computed
quickly, and are available for use in the computation of the successive
terms. This obviously requires a lot of storage.
--
Paul Lutus
www.arachnoid.com
Alex Vinokur wrote in message <7f4ffu$6dj$1...@nnrp1.dejanews.com>...
<snip>
Sunil Rao
>Several large Fibonacci numbers were calculated using only
>the well-known explicit formula:
> Fib (0) = 0, Fib (1) = 1,
> Fib (n) = Fib (n-1) + Fib (n-2), n >= 2
>All the (decimal) digits of these numbers were obtained.
>
>It was using the EXPLICIT Fibonacci formula and
> computing ALL the large Fibonacci numbers digits
>that were set as an object.
>Using just EXPLICIT Fibonacci formula is not an imperative requirement.
>But to get ALL digits of the large Fibonacci number is very advisable one.
Can you post your code? And what do you mean by "explicit" formula? I
mean, what's the point of using the formula you've quoted above directly
instead of a loop using the same classes?
--
{ Sunil Rao }
"Is there any light more becoming than that, low and richly tinted, that comes
subdued through the mists of sunshine?"
-- J Sheridan Le Fanu
Michel Pitermann
> << The question is, if is there any EXPLICIT method that calculates ALL
> digits Fib [5,000,000+] and takes acceptable time? >>
>
> Yes, a trivial method. You compute the entire sequence of numbers and store
> each result as the sequence proceeds. The individual numbers are computed
> quickly, and are available for use in the computation of the successive
> terms. This obviously requires a lot of storage.
I did not follow the begining of this thread, but if only Fib(5,000,000) is
needed, why storing each result? You just have to keep the last 2 numbers.
In Fib [5,000,000+], what does "+" mean? It may be the answer to my question.
Best regards,
pit
--
Michel Pitermann, Department of Psychology, Queen's University,
Kingston, Ontario, Canada K7L 3N6. mpi...@psyc.queensu.ca
Tel: +1 - 613 - 533 6000 ext 75754 Fax: +1 - 613 - 533 2499
Inflatable Pinata
[|> that calculates ALL digits Fib [5,000,000+] and
[|> takes acceptable time?
Yes. I don't remember the exact formula, but it's something like
n n
1+sqrt(5) 1-sqrt(5)
Fn = ( --------- ) - ( --------- )
2 2
Your mileage may vary.
It's a trick you can learn in (?)combinatorics. Any recurrent series can
be expressed as the power of a specific matrix. Get the (?)eigenvalues of
the matrix and you express it as a simple polynomial.
Obviously I'm blanking out (or repressing?) on the details, but I do
remember doing this, and the Lucas series, and a few others. Your
friendly, neighbourhood maths professor should be able to help.
--
Fe mhats enearha esma; iufue dolha soentrides odoem esri.
Fe bhuearai osraha esma; iufue auaen bhuearai shahem essa.
CACS: http://homestead.dejanews.com/user.smjames/index.html
text: http://www.geocities.com/SoHo/Studios/5079/index.html
Megagilby's inflatable fantasy joy-toy and pinata.
Sven
calculation of how long this should take:
1044938 decimal digits converted to binary would take 433902 bytes
(424K).
One addition operation on a number of that magnitude should take 108476
x 32-bit ADD operations. This can be carried out at a rate of about 800
per second (360 MHz, 4 clocks per ADD, address increment, loop) - don't
worry, we can add more fudge factor later.
5,000,000 additions of this type would thus take under 2 hours.
Now we don't really need to add this size numbers each time - probably
on average, half that size.
Conversion back to base 10 could be carried out thousands of times
faster than your printer can keep up - thus insignificant overhead.
So, is under one hour acceptable? Certainly much better than the 43 or
63 hours...
And all the while, the amount of memory required would be under 1 meg.
I suspect if you post this problem to comp.lang.asm.x86 you might get a
contest going for the fastest program.
And this problem being important to you, it's well worth looking beyond
the bc utility and instead going for a customized solution which
capitalizes on your processor's strengths.
Sven
Paul Lutus
He had been using the classic closed-form solution for *one* Fibonaccci
number, the one based on the Golden Ratio, but had been applying it to all
of them. Not the most efficient way to go.
--
Paul Lutus
www.arachnoid.com
Michel Pitermann wrote in message
<1hu2uhw...@ebbinghaus.psyc.QueensU.CA>...
>"Paul Lutus" <nos...@nosite.com> writes:
>
>> << The question is, if is there any EXPLICIT method that calculates ALL
>> digits Fib [5,000,000+] and takes acceptable time? >>
>>
Gregory Fetting
<smjames-1504...@ppp-206-170-24-126.sntc01.pacbell.net>,
smj...@my-dejanews.com (Inflatable Pinata) wrote:
>[|>The question is, if is there any EXPLICIT method
>[|> that calculates ALL digits Fib [5,000,000+] and
>[|> takes acceptable time?
>
>Yes. I don't remember the exact formula, but it's something like
>
> n n
> 1+sqrt(5) 1-sqrt(5)
>Fn = ( --------- ) - ( --------- )
> 2 2
>
>Your mileage may vary.
>
>It's a trick you can learn in (?)combinatorics. Any recurrent series can
>be expressed as the power of a specific matrix. Get the (?)eigenvalues of
>the matrix and you express it as a simple polynomial.
>
>Obviously I'm blanking out (or repressing?) on the details, but I do
>remember doing this, and the Lucas series, and a few others. Your
>friendly, neighbourhood maths professor should be able to help.
Yes, you are close with your above polynomial. I just recently studied
such formulas in my Discrete Structures class and we happened to solve the
Fib. Series explicatly.
Basically, the fibonacci series breaks down nto a linear, homogeneous
second-order recurrence relation. All such relations can be rewritten as a
simple polynomial.
Ie, the basic form for this type of relation in its recursive form is as
follows:
a = c a + c a
n 1 n-1 2 n-2
For the fib series, it is simply
a = a + a
n n-1 n-2
This form can always be rewritten as an explicit formula of the form
n n
a = b r + d r
n 1 2
Where r1 and r2 are the rates of growth, and b and d are the weights of
each rate.
Having just worked through the conversion as a homework exercise, it
turned out that the Fibonacci series can be rewritten as follows:
1 1+sqrt(5) (n+1) 1-sqrt(5) (n+1)
f = -------- * [ ( --------- ) - ( --------- ) ]
n sqrt (5) 2 2
Try it out, it does work! Hope this helps...
Gregory Fetting
John Rixon
: Having just worked through the conversion as a homework exercise, it
: turned out that the Fibonacci series can be rewritten as follows:
: 1 1+sqrt(5) (n+1) 1-sqrt(5) (n+1)
: f = -------- * [ ( --------- ) - ( --------- ) ]
: n sqrt (5) 2 2
: Try it out, it does work! Hope this helps...
Here is a nicer way of working out a term:
/* logN fibonacci */
unsigned long fib(int n)
{
unsigned long a=0, b=1, x=0, y=1, t;
while (n)
if (n%2) t=x, x=a*x+b*y, y=b*t+a*y+b*y, n--;
else t=a, a=a*a+b*b, b=2*t*b+b*b, n/=2;
return x;
}
--
John Rixon
jo...@areti.com
Alex Vinokur
Sunil Rao <suni...@ic.ac.uk> wrote:
> Alex Vinokur <alexande...@telrad.co.il> wrote, and I reply...
> >Several large Fibonacci numbers were calculated using only
> >the well-known explicit formula:
> And what do you mean by "explicit" formula?
Fib (0) = 0, Fib (1) = 1,
Fib (n) = Fib (n-1) + Fib (n-2), n >= 2
Alex Vinokur
Michel Pitermann <mpi...@ebbinghaus.psyc.QueensU.CA> wrote:
[snip]
> I did not follow the begining of this thread, but if only Fib(5,000,000) is
> needed, why storing each result? You just have to keep the last 2 numbers.
> In Fib [5,000,000+], what does "+" mean?
[snip]
Thanks,
Alex Vinokur
Sunil Rao <suni...@ic.ac.uk> wrote:
> Alex Vinokur <alexande...@telrad.co.il> wrote, and I reply...
> >Several large Fibonacci numbers were calculated using only
> >the well-known explicit formula:
> > Fib (n) = Fib (n-1) + Fib (n-2), n >= 2
> Can you post your code?
Hi,
Main idea of the algorithm was shown in thread titled
"What's wrong with this code? Recursion Question!"
in comp.lang.c++.
(Please see messages posted by Alex Vinokur, Clark Dorman)
The link is :
Alex Vinokur
Sunil Rao <suni...@ic.ac.uk> wrote:
> Alex Vinokur <alexande...@telrad.co.il> wrote, and I reply...
> >Several large Fibonacci numbers were calculated using only
> >the well-known explicit formula:
> > Fib (0) = 0, Fib (1) = 1,
> > Fib (n) = Fib (n-1) + Fib (n-2), n >= 2
> >All the (decimal) digits of these numbers were obtained.
> >
> > computing ALL the large Fibonacci numbers digits
> >that were set as an object.
> >Using just EXPLICIT Fibonacci formula is not an imperative requirement.
> >But to get ALL digits of the large Fibonacci number is very advisable one.
>
[snip]
Hi,
Yes, I can.
Here is one.
Alex
#########################################################
=== File #1 of 3 : fib_class_of_alex_vinokur.H ==========
------------------- C++ code : BEGIN --------------------
// ==============================================================
//
// Copyright (c) 1999 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_class_of_alex_vinokur.H
//
// AUTHOR : Alex Vinokur
//
// DESCRIPTION :
// Template classes :
// - avDesirableLongInt
// - avClassTemplateFibonacci
// - avClassTemplateOneFibonacci
// - avClassDecUnitFibonacci
// - avClassDecUnitOneFibonacci
// - avClassHexUnitFibonacci
// - avClassHexUnitOneFibonacci
//
// DATE VERSION
// ---- -------
// Apr-22-1999 AVF 1.0
//
// ##############################################################
#ifndef __fib_class_of_alex_vinokur_H
#define __fib_class_of_alex_vinokur_H
//###===###===###===###===###===###===###===###===###===###
#include <assert.h>
#include <string>
#include <strstream>
#include <vector>
#include <iomanip.h>
//#######################################################
//##### PART#1 : DEFINES & CONSTANTS ####################
//#######################################################
#define MAX_VALUE(x,y) ((x) > (y) ? (x) : (y))
#define ASSERT(x) assert (x)
#define INFO_MESSAGE
const long unsigned int Max_Unit_Value_CNS = (ULONG_MAX >> 2);
const unsigned int INFO_period_CNS = 10000;
static const string UNITS_Delimeter_CNS = "";
//#######################################################
//##### PART#2 : DECLARATIONS ###########################
//#######################################################
template <unsigned int EXPO, unsigned int UNIT_BASE>
class avDesirableLongInt;
template <unsigned int EXPO, unsigned int UNIT_BASE>
avDesirableLongInt<EXPO, UNIT_BASE> operator+ (
const avDesirableLongInt<EXPO, UNIT_BASE>&
left_i,
const avDesirableLongInt<EXPO, UNIT_BASE>&
right_i
);
//#######################################################
//##### PART#3 : The avDesirableLongInt class ###########
//#######################################################
//#############################
template <unsigned int EXPO, unsigned int UNIT_BASE>
class avDesirableLongInt
{
template <unsigned int EXPO, unsigned int UNIT_BASE>
friend avDesirableLongInt<EXPO, UNIT_BASE> operator+ (
const avDesirableLongInt<EXPO,
UNIT_BASE>& left_i,
const avDesirableLongInt<EXPO,
UNIT_BASE>& right_i
);
private :
long unsigned int full_base_;
vector <long unsigned int> vector_unit_;
public : avDesirableLongInt (); avDesirableLongInt (long unsigned int
unit_value_i); avDesirableLongInt ( const avDesirableLongInt<EXPO,
UNIT_BASE>& left_i, const avDesirableLongInt<EXPO, UNIT_BASE>& right_i );
~avDesirableLongInt () {} 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; unsigned
int getSize (ios& show_base_i (ios&)) const; static unsigned int getSize_S
(const string& strValue_i); unsigned int getTotalUnits () const {return
vector_unit_.size ();} };
//=====================
template <unsigned int EXPO, unsigned int UNIT_BASE>
avDesirableLongInt<EXPO, UNIT_BASE> operator+ (
const avDesirableLongInt<EXPO, UNIT_BASE>&
left_i,
const avDesirableLongInt<EXPO, UNIT_BASE>&
right_i
)
{
avDesirableLongInt<EXPO, UNIT_BASE> ret_avDesirableLongInt_Value;
const long unsigned int max_size_CNS = MAX_VALUE (
left_i.vector_unit_.size (),
right_i.vector_unit_.size ()
);
long unsigned cur_big_value;
long unsigned int head = 0;
for (long unsigned int 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_avDesirableLongInt_Value.vector_unit_.push_back
(cur_big_value%(left_i.full_base_));
ASSERT (ret_avDesirableLongInt_Value.vector_unit_
[ret_avDesirableLongInt_Value.vector_unit_.size () - 1] < left_i.full_base_);
//------------------------
head = cur_big_value/(left_i.full_base_);
} // for (long unsigned int theIndex = 0; theIndex < max_size_CNS;
theIndex++
ASSERT (ret_avDesirableLongInt_Value.vector_unit_.size () ==
max_size_CNS);
if (head)
{
ret_avDesirableLongInt_Value.vector_unit_.push_back (head);
}
//======================
return ret_avDesirableLongInt_Value;
//======================
} // avDesirableLongInt<EXPO, UNIT_BASE> operator+
//=====================
// Constructor-0
template <unsigned int EXPO, unsigned int UNIT_BASE>
avDesirableLongInt<EXPO, UNIT_BASE>::avDesirableLongInt ()
{
set_full_base ();
}
//=====================
// Constructor-1
template <unsigned int EXPO, unsigned int UNIT_BASE>
avDesirableLongInt<EXPO, UNIT_BASE>::avDesirableLongInt (long unsigned int
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 <unsigned int EXPO, unsigned int UNIT_BASE>
avDesirableLongInt<EXPO, UNIT_BASE>::avDesirableLongInt (
const avDesirableLongInt<EXPO, UNIT_BASE>&
left_i,
const avDesirableLongInt<EXPO, UNIT_BASE>&
right_i
)
{
set_full_base ();
(*this) = left_i + right_i;
}
//=====================
template <unsigned int EXPO, unsigned int UNIT_BASE>
string avDesirableLongInt<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 (long unsigned int 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 <unsigned int EXPO, unsigned int UNIT_BASE>
string avDesirableLongInt<EXPO, UNIT_BASE>::getAllInfo (ios& show_base_i
(ios&)) const { string ret_Value; string stringValue = getStrValue
(show_base_i); strstream tmp_strstream;
tmp_strstream << stringValue;
tmp_strstream << "; 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 <unsigned int EXPO, unsigned int UNIT_BASE>
unsigned int avDesirableLongInt<EXPO, UNIT_BASE>::getSize (ios& show_base_i
(ios&)) const
{
return getSize_S (getStrValue (show_base_i));
}
//===================== // static template <unsigned int EXPO, unsigned int
UNIT_BASE> unsigned int avDesirableLongInt<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 <unsigned int EXPO, unsigned int UNIT_BASE>
string avDesirableLongInt<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 <unsigned int EXPO, unsigned int UNIT_BASE>
void avDesirableLongInt<EXPO, UNIT_BASE>::set_full_base ()
{
ASSERT (EXPO > 1);
ASSERT ((UNIT_BASE == 8) || (UNIT_BASE == 10) || (UNIT_BASE == 16));
//==================
full_base_ = 1;
for (long unsigned int 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 avClassTemplateFibonacci class #####
//#######################################################
//#############################
//=====================
template <unsigned int EXPO, unsigned int UNIT_BASE>
class avClassTemplateFibonacci
{
private :
vector< avDesirableLongInt<EXPO, UNIT_BASE> > fib_vector_;
protected :
avClassTemplateFibonacci (int n_i = 0);
public :
string getAllNumbers (ios& show_base_i (ios&)) const;
virtual avDesirableLongInt<EXPO, UNIT_BASE> getFibNumber
(int n_i = 0);
virtual ~avClassTemplateFibonacci () {}
};
//-----------------------
// Constructor
template <unsigned int EXPO, unsigned int UNIT_BASE>
avClassTemplateFibonacci<EXPO, UNIT_BASE>::avClassTemplateFibonacci (int n_i)
{
getFibNumber (n_i);
}
//-----------------------
template <unsigned int EXPO, unsigned int UNIT_BASE>
avDesirableLongInt<EXPO, UNIT_BASE> avClassTemplateFibonacci<EXPO,
UNIT_BASE>::getFibNumber (int n_i)
{
const unsigned int cur_size = fib_vector_.size ();
//========================
if (n_i < 0)
{
cout << "FATAL ERROR : n = "
<< n_i
<< "; "
<< __FILE__
<< ", #"
<< __LINE__
<< endl;
exit (1);
}
for (unsigned int i = cur_size; i <= (unsigned int) n_i; i++) { switch
(i) { case 0 : fib_vector_.push_back (avDesirableLongInt<EXPO, UNIT_BASE>
(0)); break;
case 1 : if (fib_vector_.empty ()) { fib_vector_.push_back
(avDesirableLongInt<EXPO, UNIT_BASE> (0)); } fib_vector_.push_back
(avDesirableLongInt<EXPO, UNIT_BASE> (1)); break;
default :
fib_vector_.push_back (
avDesirableLongInt<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))
{
cout << "INFO"
<< " ("
<< __FILE__
<< ", Line#"
<< __LINE__
<< ")"
<< " : "
<< " Fib#"
<< i
<< " calculated; 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];
} // long unsigned int avClassTemplateFibonacci::getFibNumber (int n_i)
//-----------------------
template <unsigned int EXPO, unsigned int UNIT_BASE>
string avClassTemplateFibonacci<EXPO, UNIT_BASE>::getAllNumbers (ios&
show_base_i (ios&)) const
{
string ret_Value;
strstream tmp_strstream;
for (unsigned int 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 avClassTemplateFibonacci::getAllNumbers () const
//#######################################################
//##### PART#5 : The avClassTemplateOneFibonacci class ##
//#######################################################
//#############################
//=====================
template <unsigned int EXPO, unsigned int UNIT_BASE>
class avClassTemplateOneFibonacci : public avClassTemplateFibonacci<EXPO,
UNIT_BASE>
{
private :
protected :
avClassTemplateOneFibonacci (int n_i = 0) :
avClassTemplateFibonacci (n_i) {}
public : avDesirableLongInt<EXPO, UNIT_BASE> getFibNumber (int n_i = 0);
~avClassTemplateOneFibonacci () {} };
//-----------------------
template <unsigned int EXPO, unsigned int UNIT_BASE>
avDesirableLongInt<EXPO, UNIT_BASE> avClassTemplateOneFibonacci<EXPO,
UNIT_BASE>::getFibNumber (int n_i)
{
vector < avDesirableLongInt<EXPO, UNIT_BASE> > one_vector_;
one_vector_.push_back (avDesirableLongInt<EXPO, UNIT_BASE> (0));
one_vector_.push_back (avDesirableLongInt<EXPO, UNIT_BASE> (1));
one_vector_.push_back (avDesirableLongInt<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))
{
cout << "INFO"
<< " ("
<< __FILE__
<< ", Line#"
<< __LINE__
<< ")"
<< " : "
<< " Fib#"
<< theIndex
<< " calculated; Total Units = "
<< one_vector_ [2].getTotalUnits ()
<< endl;
}
#endif
}
//========================
return one_vector_ [2];
} // long unsigned int avClassTemplateOneFibonacci::getFibNumber (int n_i)
//#######################################################
//##### PART#6 : The avClassDecUnitFibonacci class ######
//#######################################################
//#############################
//=====================
template <unsigned int EXPO>
class avClassDecUnitFibonacci : public avClassTemplateFibonacci <EXPO, 10>
{
public :
avClassDecUnitFibonacci (int n_i = 0) : avClassTemplateFibonacci<EXPO,
10> (n_i) {}
~avClassDecUnitFibonacci () {}
};
//==========================
typedef avClassDecUnitFibonacci<9> ClassFibonacci;
//==========================
//#######################################################
//##### PART#7 : The avClassDecUnitOneFibonacci class ###
//#######################################################
//############################# //===================== template <unsigned
int EXPO> class avClassDecUnitOneFibonacci : public
avClassTemplateOneFibonacci <EXPO, 10> { public :
avClassDecUnitOneFibonacci (int n_i = 0) : avClassTemplateOneFibonacci<EXPO,
10> (n_i) {} ~avClassDecUnitOneFibonacci () {} };
//==========================
typedef avClassDecUnitOneFibonacci<9> ClassOneFibonacci;
//==========================
//#######################################################
//##### PART#8 : The avClassHexUnitFibonacci class ######
//#######################################################
//#############################
//=====================
template <unsigned int EXPO>
class avClassHexUnitFibonacci : public avClassTemplateFibonacci <EXPO, 16>
{
public :
avClassHexUnitFibonacci (int n_i = 0) : avClassTemplateFibonacci<EXPO,
16> (n_i) {}
~avClassHexUnitFibonacci () {}
};
//#######################################################
//##### PART#9 : The avClassHexUnitOneFibonacci class ###
//#######################################################
//############################# //===================== template <unsigned
int EXPO> class avClassHexUnitOneFibonacci : public
avClassTemplateOneFibonacci <EXPO, 16> { public :
avClassHexUnitOneFibonacci (int n_i = 0) : avClassTemplateOneFibonacci<EXPO,
16> (n_i) {} ~avClassHexUnitOneFibonacci () {} };
//#######################################################
//##### PART#10 : FUNCTIONS #############################
//#######################################################
bool stringIsDigit (const string& string_i);
bool stringIsNonDigit (const string& string_i);
void printAllFib (
long unsigned int n_i,
const string& msg_i = string (),
ios& show_base_i (ios&) = dec
);
void printOneFib (
long unsigned int n_i,
const string& msg_i = string (),
ios& show_base_i (ios&) = dec
);
void printSomeFib (
const vector<long unsigned int>& vect_i,
const string& msg_i = string (),
ios& show_base_i (ios&) = dec
);
int mainFib (int argc, char **argv);
//###===###===###===###===###===###===###===###===###===###
#endif // __fib_class_of_alex_vinokur_H
//###################################################
//############ END OF FILE ##########################
//###################################################
------------------- C++ code : END ----------------------
=== File #1 of 3 : fib_class_of_alex_vinokur.H ==========
#########################################################
=== File #2 of 3 : fib_class_of_alex_vinokur.C ==========
------------------- C++ code : BEGIN --------------------
// ==============================================================
//
// Copyright (c) 1999 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_class_of_alex_vinokur.C
//
// AUTHOR : Alex Vinokur
//
// DESCRIPTION :
// Functions :
// - stringIsDigit
// - stringIsNonDigit
// - printAllFib
// - printOneFib
// - printSomeFib
// - printErrorUsageMessage
// - argv_check
// - mainFib
//
// DATE VERSION
// ---- -------
// Apr-22-1999 AVF 1.0
//
// ##############################################################
#include "fib_class_of_alex_vinokur.H"
//###################################################
//############ FUNCTION #############################
//###################################################
//#####################################################
bool stringIsDigit (const string& string_i)
{
ASSERT (!string_i.empty ());
for (long unsigned int theIndex= 0; theIndex < string_i.size ();
theIndex++)
{
if (!isdigit (string_i [theIndex]))
{
return false;
}
}
return true;
} // bool stringIsDigit (const string& string_i)
//#####################################################
bool stringIsNonDigit (const string& string_i)
{
ASSERT (!string_i.empty ());
for (long unsigned int theIndex= 0; theIndex < string_i.size ();
theIndex++)
{
if (isdigit (string_i [theIndex]))
{
return false;
}
}
return true;
} // bool stringIsNonDigit (const string& string_i)
//#####################################################
void printAllFib (
long unsigned int 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;
}
tmp_strstream << ClassFibonacci (n_i).getAllNumbers (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 (
long unsigned int 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
<< " = "
<< 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<long unsigned int>& 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 (unsigned int theIndex = 0; theIndex < vect_i.size (); theIndex++)
{
tmp_strstream << "Fib#"
<< vect_i [theIndex]
<< " = "
<< f1.getFibNumber (vect_i [theIndex]).getAllInfo
(show_base_i)
<< endl;
} // for (unsigned int theIndex = 0; theIndex < vect_i.size ();
theIndex++)
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 <number>"
<< endl
<< " : "
<< argv[0]
<< " <number> [<number>, <number>, ...]"
<< endl;
}
//#####################################################
bool argv_check (
int argc,
char **argv,
long unsigned int cur_index_i,
long unsigned int& cur_numberValue_o
)
{
//============================
ASSERT (argc >= 2);
ASSERT (cur_index_i >= 1);
//============================
if (!stringIsDigit (string (argv[cur_index_i])))
{
printErrorUsageMessage (argc, argv);
cout << endl
<< "NOT 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 (long unsigned int cur_index_i)
//#####################################################
int mainFib (int argc, char **argv)
{
long unsigned int cur_numberValue;
long unsigned int cur_index;
vector<long unsigned int> vect;
switch (argc)
{
case 0 :
abort ();
break;
case 1 :
printErrorUsageMessage (argc, argv);
exit (1);
break;
case 2 :
cur_index = 1;
if (!argv_check (argc, argv, cur_index,
cur_numberValue))
{
exit (1);
}
printOneFib (cur_numberValue);
break;
case 3 :
if (string ("All") == argv [1])
{
cur_index = 2;
if (!argv_check (argc, argv, cur_index,
cur_numberValue))
{
exit (1);
}
printAllFib (cur_numberValue);
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_class_of_alex_vinokur.C ==========
#########################################################
=== File #3 of 3 : fib_main_of_alex_vinokur.C ===========
------------------- C++ code : BEGIN --------------------
// ==============================================================
//
// Copyright (c) 1999 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_main_of_alex_vinokur.C
//
// AUTHOR : Alex Vinokur
//
// DESCRIPTION : Main program
//
// DATE VERSION
// ---- -------
// Apr-22-1999 AVF 1.0
//
// ##############################################################
#include "fib_class_of_alex_vinokur.H"
//###################################################
//###################################################
//###################################################
//==============================
int main (int argc, char **argv)
{
return mainFib (argc, argv);
}
//###################################################
//############ END OF FILE ##########################
//###################################################
------------------- C++ code : END ----------------------
=== File #3 of 3 : fib_main_of_alex_vinokur.C ===========
#########################################################
------------------- Compilation : BEGIN -----------------
Compilation Command Line :
g++ -O3 fib_main_of_alex_vinokur.C fib_class_of_alex_vinokur.C
------------------- Compilation : END -==----------------
#########################################################
------------------- Running : BEGIN ---------------------
=========
Running#1
=========
Command Line :
--------------
a.out 12
Output :
-------
Fib#12 = 144; Size = 3 (dec digits)
=========
Running#2
=========
Command Line :
--------------
a.out 5 9 10 12
Output :
-------
Fib#5 = 5; Size = 1 (dec digits)
Fib#9 = 34; Size = 2 (dec digits)
Fib#10 = 55; Size = 2 (dec digits)
Fib#12 = 144; Size = 3 (dec digits)
=========
Running#1
=========
Command Line :
--------------
a.out All 12
Output :
-------
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)
------------------- Running : END -----------------------
#########################################################
------------------- Compiler & System ------------------
g++ -v : gcc version egcs-2.91.57 19980901
(egcs-1.1 release)
uname -a : SunOS <nodename> 5.6 Generic_105181-09
sun4m sparc SUNW,SPARCstation-5
---------------------------------------------------------
//#########################################################