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

Fibonacci [5,000,000] contains 1044938 decimal digits

11 views
Skip to first unread message

Alex Vinokur

unread,
Apr 26, 1999, 3:00:00 AM4/26/99
to
In article <Mo2OZGAC...@raos.demon.co.uk>,
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.
> >
> >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?
[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

---------------------------------------------------------

//#########################################################


-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own


Alex Vinokur

unread,
Jul 25, 2004, 3:03:42 AM7/25/04
to
On 26 Apr 1999 00:42:53 -0400, Alex Vinokur wrote:
>In article <Mo2OZGAC...@raos.demon.co.uk>,
> 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.
>> >
>> >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?
>[snip]
>
>Hi,
>
>Yes, I can.
>Here is one.
>
> Alex
[snip]


Here is an improved version of the program.

// ############################################
// [C++] Computing very large Fibonacci numbers
// Version 2.6.1 (with performance test)
// --------------------------------------------
// Copyright (C) 1999-2004 Alex Vinokur
// mailto:ale...@connect.to
// http://mathforum.org/library/view/10978.html
// --------------------------------------------
// Copyright (C) 2004 John Harrison, vector.reserve()-related
improvement
// ############################################

#include <cstdlib>
#include <cassert>
#include <string>
#include <sstream>
#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;


#define MAX_VALUE(x,y) ((x) > (y) ? (x) : (y))
#define ASSERT(x)

// #define ASSERT(x) assert(x)


#define MAX_UNIT_VALUE (ULONG_MAX >> 2)
#define BASE1 10
#define BASE2 1000000000 // BASE1 ** (BASE1 - 1)


#if (BASE2 >= MAX_UNIT_VALUE)
#error Compilation Error-1 : (BASE2 >= MAX_UNIT_VALUE)
#endif

#if (!(BASE1 * (BASE2/BASE1 + 1) < MAX_UNIT_VALUE))
#error Compilation Error-2 : (!(BASE1 * (BASE2/BASE1 + 1) <
MAX_UNIT_VALUE))
#endif


typedef unsigned int uint;
typedef unsigned long ulong;

// =========
class BigInt
// =========
{
friend ostream& operator<< (ostream& os, const BigInt& ins_i);

private :
static ulong head_s;
vector<ulong> units_;

public :
BigInt (ulong unit_i)
{
ASSERT (unit_i < BASE2);
// ---------------------
// The reserve() has been added under the influence of the John
Harrison's improvement
// See method get_number (uint n_i)
units_.reserve(units_.size() + 1);
// ---------------------
units_.push_back (unit_i);
}

BigInt (BigInt big1_i, BigInt big2_i)
{
const ulong max_size = MAX_VALUE (big1_i.units_.size (),
big2_i.units_.size ());

// ---------------------
// The reserve()'s have been added under the influence of the
John Harrison's improvement
// See method get_number (uint n_i)
units_.reserve(units_.size() + 1);
big1_i.units_.reserve(max_size);
big2_i.units_.reserve(max_size);
units_.reserve(max_size);
// ---------------------

big1_i.units_.resize(max_size);
big2_i.units_.resize(max_size);
units_.resize(max_size);

head_s = 0;
transform (big1_i.units_.begin(), big1_i.units_.end(),
big2_i.units_.begin(), units_.begin(), *this);

if (head_s) units_.push_back (head_s);

}

ulong operator() (const ulong n1, const ulong n2)
{
const ulong value = n1 + n2 + head_s;
head_s = value/BASE2;
return (value%BASE2);
}

};


// --------------
inline ostream& operator<< (ostream& os, const BigInt& ins_i)
{
ASSERT (!ins_i.units_.empty ());
for (ulong i = (ins_i.units_.size () - 1); i; --i)
{
os << ins_i.units_ [i] << setw (BASE1 - 1) << setfill ('0');
}
return os << ins_i.units_ [0];
}


// ============
class Fibonacci
// ============
{
private :
vector<BigInt> fibs_;
BigInt get_number (uint n_i = 0);

public :
void show_all_numbers () const;
void show_last_number () const;
void show_number (ulong n_i);

Fibonacci (uint n_i = 0) { get_number (n_i); }
~Fibonacci () {}

};


// -----------------------
BigInt Fibonacci::get_number (uint n_i)
{
// ---------------------
// The improvement below has been proposed by John Harrison
// in
http://groups.google.com/groups?selm=c58obb%242qat6b%241%40ID-196037.news.uni-berlin.de
fibs_.reserve(n_i + 1);
// ---------------------
const uint cur_size = fibs_.size ();

for (uint i = cur_size; i <= n_i; ++i)
{
switch (i)
{
case 0 :
fibs_.push_back (BigInt(0));
break;

case 1 :
if (fibs_.empty ()) fibs_.push_back (BigInt (0));
fibs_.push_back(BigInt (1));
break;

default :
// fibs_.push_back (BigInt (get_number (i - 2), get_number (i
- 1)));
fibs_.push_back (BigInt (fibs_ [i - 2], fibs_ [i - 1]));
break;
}
}

ASSERT (n_i < fibs_.size());
return fibs_ [n_i];

}


// -----------------------
void Fibonacci::show_all_numbers () const
{
ostringstream oss;

for (uint i = 0; i < fibs_.size (); ++i)
{
oss << "Fib [" << i << "] = " << fibs_ [i] << "\n";
}
cout << oss.str();
}


// -----------------------
void Fibonacci::show_last_number () const
{
ostringstream oss;

oss << "Fib [" << (fibs_.size() - 1) << "] = " << fibs_.back() <<
"\n";

cout << oss.str();
}

// -----------------------
void Fibonacci::show_number (ulong n_i)
{
ostringstream oss;

if (!(n_i < fibs_.size())) get_number (n_i);

oss << "Fib [" << n_i << "] = " << fibs_[n_i] << "\n";

cout << oss.str();
}

// -------------------
ulong BigInt::head_s (0);


// ==============================
#define ALL_FIBS "all"
#define TH_FIB "th"
#define SOME_FIBS "some"
#define RAND_FIBS "rand"

#define MAX_RAND_FIB 25000

#define SETW1 4

// ---------------------
void usage (char **argv)
{
cerr << "USAGE : "
<< endl

<< " "
<< argv[0]
<< " "
<< setw (SETW1)
<< std::left
<< ALL_FIBS
<< " <N> ---> Fibonacci [0 - N]"
<< endl

<< " "
<< argv[0]
<< " "
<< std::left
<< setw (SETW1)
<< TH_FIB
<< " <N> ---> Fibonacci [N]"
<< endl

<< " "
<< argv[0]
<< " "
<< std::left
<< setw (SETW1)
<< SOME_FIBS
<< " <N1> [<N2> ...] ---> Fibonacci [N1], Fibonacci [N2], ..."

<< endl

<< " "
<< argv[0]
<< " "
<< std::left
<< setw (SETW1)
<< RAND_FIBS
<< " <K> [<M>] ---> K random Fibonacci numbers ( < M;
Default = "
<< MAX_RAND_FIB
<< " )"
<< endl;
}


// ---------------------
string check (int argc, char **argv)
{
if (argc < 3) return string();

const string str (argv[1]);
if (
(str == ALL_FIBS)
||
(str == TH_FIB)
||
(str == SOME_FIBS)
||
(str == RAND_FIBS)
)
{
return str;
}
return string();

}


// ---------------------
#include <ctime>


int main (int argc, char **argv)
{

const string option (check (argc, argv));
if (option.empty())
{
usage (argv);
return 1;
}

const uint N = atoi (argv[2]);

const clock_t clock_start = clock();
assert (clock_start != clock_t (-1));

if (option == ALL_FIBS)
{
Fibonacci fib(N);
fib.show_all_numbers();
}

if (option == TH_FIB)
{
Fibonacci fib(N);
fib.show_last_number();
}

if (option == SOME_FIBS)
{
Fibonacci fib;
for (int i = 2; i < argc; i++) fib.show_number (atoi(argv[i]));
}

if (option == RAND_FIBS)
{
const int max_rand_fib = (argc == 3) ? MAX_RAND_FIB : atoi
(argv[3]);
Fibonacci fib;
for (uint i = 0; i < N; i++) fib.show_number
(rand()%max_rand_fib);
}

const clock_t clock_end = clock();
assert (clock_end != clock_t (-1));

cerr << (double (clock_end - clock_start)/CLOCKS_PER_SEC) << endl;

return 0;
}


Alex Vinokur
http://mathforum.org/library/view/10978.html
http://sourceforge.net/users/alexvn

Michael Taktikos

unread,
Jul 26, 2004, 4:38:05 AM7/26/04
to
Alex Vinokur <ale...@bigfoot.com> wrote:

> >> >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.

[...]


> >> >But to get ALL digits of the large Fibonacci number is very
> advisable one.

> [C++ code, snip]

Thanks for your code.
Until now, the fastest way to get with "Mathematica-alone" all digits of
large Fibonacci numbers seems to be that of Roman Maeder:

********************************************************
fibmaeder[n_] :=
Module[{r11 = 1, r12 = 0, r22 = 1, digits = IntegerDigits[n-1, 2], i, t},
Do[ If[ digits[[i]] == 1,
{r11, r22} = {r11(r11 + 2r12), r12(r11 + r22)};
r12 = r11 - r22
, t = r12(r11 + r22);
{r11, r12} = {r11(r11 + 2r12) - t, t};
r22 = r11 - r12
],
{i, Length[digits]-1}
];
If[ digits[[-1]] == 1,
r11(r11 + 2r12),
r11(r11 + r22) - (-1)^((n-1)/2)
]
]

********************************************************

If you don't need all the digits, but only the number of the contained
decimal digits,
you can use the function of Binet with an appropriate precision:

In[1]:=fiboBinet[n_]:=Module[{gr=GoldenRatio^n}, N[(gr+1/gr)/Sqrt[5],1000]]
In[2]:=Timing[fiboBinet[10^9]]
(gives with my old AMD 700 MHz the answer {0.6 Second,
7.9...*10^208987639} )

Now I detected an other function, which seems to be faster than Binet's one:
fiboNew(n) = g^n/(2g-1) with g = GoldenRatio.

Let's try it:
In[3]:=fiboNew[n_]:=N[(GoldenRatio^n)/(2*GoldenRatio-1),1000];
In[4]:=Timing[fiboNew[10^9]]

It gives the answer {0.1 Second, 7.9...*10^208987639}

By searching with Google and looking in your "Bronstein" you will not find
it published,
therefore I ask the group: is this the first publication or did I only
discovered the wheel again?
I believe to have a proof that this function gives allways the same answer
as Binet's one,
now I'm looking if it contains bugs.

Greetings from Hamburg,

Michael Taktikos


Bobby R. Treat

unread,
Jul 26, 2004, 4:45:09 AM7/26/04
to
I'm not sure I'd bother with C code for this. After a fresh start, I get:

Timing@N@Fibonacci[5000000]

{0.25*Second, 7.108285972058527236971171956172`15.954589770191005*^1044937}

Fibonacci[5000000] gives all the digits, too.

Bobby

ale...@bigfoot.com (Alex Vinokur) wrote in message news:<cdvm0e$7hv$1...@smc.vnet.net>...

Alex Vinokur

unread,
Jul 27, 2004, 7:13:23 AM7/27/04
to

"Michael Taktikos" <michael....@hanse.net> wrote in message news:ce2ftd$8rh$1...@smc.vnet.net...

> Alex Vinokur <ale...@bigfoot.com> wrote:
>
> > >> >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.
> [...]
> > >> >But to get ALL digits of the large Fibonacci number is very
> > advisable one.
> > [C++ code, snip]
>
> Thanks for your code.

Impoved version of that algorithm can be seen at
http://groups.google.com/groups?selm=2mk62rFo1mv0U1%40uni-berlin.de

> Until now, the fastest way to get with "Mathematica-alone" all digits of
> large Fibonacci numbers seems to be that of Roman Maeder:
>
> ********************************************************
> fibmaeder[n_] :=
> Module[{r11 = 1, r12 = 0, r22 = 1, digits = IntegerDigits[n-1, 2], i, t},
> Do[ If[ digits[[i]] == 1,
> {r11, r22} = {r11(r11 + 2r12), r12(r11 + r22)};
> r12 = r11 - r22
> , t = r12(r11 + r22);
> {r11, r12} = {r11(r11 + 2r12) - t, t};
> r22 = r11 - r12
> ],
> {i, Length[digits]-1}
> ];
> If[ digits[[-1]] == 1,
> r11(r11 + 2r12),
> r11(r11 + r22) - (-1)^((n-1)/2)
> ]
> ]
>

[snip]

I would like to measure the comparative performance of my C++ algorithm and "Mathematica-alone" code above.
However I have never worked with "Mathematica-alone".
How can I compare those algorithms?


--

Daniel Lichtblau

unread,
Jul 29, 2004, 8:05:31 AM7/29/04
to
Alex Vinokur wrote:
> "Michael Taktikos" <michael....@hanse.net> wrote in message news:ce2ftd$8rh$1...@smc.vnet.net...
>
>>Alex Vinokur <ale...@bigfoot.com> wrote:
>>
>>
>>>>>>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.
>>>>>
>>[...]
>>
>>>>>>But to get ALL digits of the large Fibonacci number is very
>>>>>
>>>advisable one.
>>>[C++ code, snip]
>>
>>Thanks for your code.
>
>
> Impoved version of that algorithm can be seen at
> http://groups.google.com/groups?selm=2mk62rFo1mv0U1%40uni-berlin.de
>
>
>>Until now, the fastest way to get with "Mathematica-alone" all digits of
>>large Fibonacci numbers seems to be that of Roman Maeder:
>>
>>********************************************************
>>fibmaeder[n_] :=
>> Module[{r11 = 1, r12 = 0, r22 = 1, digits = IntegerDigits[n-1, 2], i, t},
>> Do[ If[ digits[[i]] == 1,
>> {r11, r22} = {r11(r11 + 2r12), r12(r11 + r22)};
>> r12 = r11 - r22
>> , t = r12(r11 + r22);
>> {r11, r12} = {r11(r11 + 2r12) - t, t};
>> r22 = r11 - r12
>> ],
>> {i, Length[digits]-1}
>> ];
>> If[ digits[[-1]] == 1,
>> r11(r11 + 2r12),
>> r11(r11 + r22) - (-1)^((n-1)/2)
>> ]
>> ]
>>
>
> [snip]
>
> I would like to measure the comparative performance of my C++ algorithm and "Mathematica-alone" code above.
> However I have never worked with "Mathematica-alone".
> How can I compare those algorithms?

You could run them both on identical machines/inputs and check the
timings. You might also want to read what Mark Sofroniou said about this
five years ago (in response to your similar post back then).

http://forums.wolfram.com/mathgroup/archive/1999/Apr/msg00349.html

His point remains unchanged. Not knowing then about Mark's posts, I also
wrote a bit about this in 2001:

http://forums.wolfram.com/mathgroup/archive/2001/Jan/msg00234.html

But what Mark said is most relevant here. In essence, the method in
Maeder's code is a good divide-and-conquer, based on doubling
recurrences in Fibonacci numbers. This is much faster than anything
based on the linear recurrences, as it takes advantage of asymptotically
fast multiplication.


Daniel Lichtblau
Wolfram Research

Alex Vinokur

unread,
Jul 31, 2004, 3:21:41 AM7/31/04
to

"Daniel Lichtblau" <da...@wolfram.com> wrote in message news:ceap6b$aej$1...@smc.vnet.net...

> Alex Vinokur wrote:
[snip]
> > I would like to measure the comparative performance of my C++ algorithm and "Mathematica-alone" code above.
(I mean codes for computing Fibonaccii).

> > However I have never worked with "Mathematica-alone".
> > How can I compare those algorithms?
>
> You could run them both on identical machines/inputs and check the
> timings. You might also want to read what Mark Sofroniou said about this
> five years ago (in response to your similar post back then).
>
> http://forums.wolfram.com/mathgroup/archive/1999/Apr/msg00349.html

<QUOTE from that message>
Generally it is not efficient to compute Fibonacci numbers using the exact
formula involving Sqrt[5] because at high precision better methods exist.

</QUOTE>

Of course.
But I would like to know what is time complexity of computing Fibonacci numbers using the _exact_
formula.

>
> His point remains unchanged. Not knowing then about Mark's posts, I also
> wrote a bit about this in 2001:
>
> http://forums.wolfram.com/mathgroup/archive/2001/Jan/msg00234.html
>
> But what Mark said is most relevant here. In essence, the method in
> Maeder's code is a good divide-and-conquer, based on doubling
> recurrences in Fibonacci numbers. This is much faster than anything
> based on the linear recurrences, as it takes advantage of asymptotically
> fast multiplication.
>
>
> Daniel Lichtblau
> Wolfram Research
>

There are very fast algorithms for computing Fibonacci numbers not using the exact
formula.
For instance, GMP (GNU Multiple Precision Arithmetic Library) http://www.swox.com/gmp/.

http://swox.com/cgi-bin/gmp_calc.pl?expr=fib+%285000000%29
---------------------------------------------
The result of executing fib (5000000) is:
computation took 466 ms
result is about 1044938 digits, not printing it
---------------------------------------------


--

Daniel Lichtblau

unread,
Aug 1, 2004, 4:18:09 AM8/1/04
to
Alex Vinokur wrote:
> "Daniel Lichtblau" <da...@wolfram.com> wrote in message news:ceap6b$aej$1...@smc.vnet.net...
>
>>Alex Vinokur wrote:
>
> [snip]
>
>>>I would like to measure the comparative performance of my C++ algorithm and "Mathematica-alone" code above.
>>
> (I mean codes for computing Fibonaccii).
>
>>>However I have never worked with "Mathematica-alone".
>>>How can I compare those algorithms?
>>
>>You could run them both on identical machines/inputs and check the
>>timings. You might also want to read what Mark Sofroniou said about this
>>five years ago (in response to your similar post back then).
>>
>>http://forums.wolfram.com/mathgroup/archive/1999/Apr/msg00349.html
>
>
> <QUOTE from that message>
> Generally it is not efficient to compute Fibonacci numbers using the exact
> formula involving Sqrt[5] because at high precision better methods exist.
>
> </QUOTE>
>
> Of course.
> But I would like to know what is time complexity of computing Fibonacci numbers using the _exact_
> formula.
>
>
>>His point remains unchanged. Not knowing then about Mark's posts, I also
>>wrote a bit about this in 2001:
>>
>>http://forums.wolfram.com/mathgroup/archive/2001/Jan/msg00234.html
>>
>>But what Mark said is most relevant here. In essence, the method in
>>Maeder's code is a good divide-and-conquer, based on doubling
>>recurrences in Fibonacci numbers. This is much faster than anything
>>based on the linear recurrences, as it takes advantage of asymptotically
>>fast multiplication.
>>
>>
>>Daniel Lichtblau
>>Wolfram Research
>>
>
>
> There are very fast algorithms for computing Fibonacci numbers not using the exact
> formula.
> For instance, GMP (GNU Multiple Precision Arithmetic Library) http://www.swox.com/gmp/.
>
> http://swox.com/cgi-bin/gmp_calc.pl?expr=fib+%285000000%29
> ---------------------------------------------
> The result of executing fib (5000000) is:
> computation took 466 ms
> result is about 1044938 digits, not printing it
> ---------------------------------------------

I'm not sure what you want to do. There are many exact formulas. The one
in question (Mathematica code from Roman Maeder) uses a doubling
recurrence, that is, f[2*n] in terms of f[n] and f[n+1] (or something
like that. It is exact. But I do not know if you are interested in the
complexity of the best exact formulas, or the complexity of a particular
exact formula e.g. the closed form involving Sqrt[5].

Below is computed exactly, then numericized. It is not done using any
formula involving Sqrt[5].

In[2]:= Timing[ff = Fibonacci[5000000];]
Out[2]= {0.59 Second, Null}

In[3]:= InputForm[N[ff]]
Out[3]//InputForm=
7.108285972058527236971171956172`15.954589770191005*^1044937

Likewise the GMP result you site is computed using an exact method
(probably about the same as what we do).


Daniel Lichtblau
Wolfram Research

Alex Vinokur

unread,
Aug 1, 2004, 6:49:16 PM8/1/04
to

"Daniel Lichtblau" <da...@wolfram.com> wrote in message news:cei901$2jt$1...@smc.vnet.net...
> Alex Vinokur wrote:
[snip]

> > But I would like to know what is time complexity of computing Fibonacci numbers using the _exact_
> > formula.

I want to refine myself.
I would like to compare efficiency of algorithms which compute Fibonacci numbers using the _primary_ formula.

[snip]


>
> I'm not sure what you want to do. There are many exact formulas. The one
> in question (Mathematica code from Roman Maeder) uses a doubling
> recurrence, that is, f[2*n] in terms of f[n] and f[n+1] (or something
> like that. It is exact. But I do not know if you are interested in the
> complexity of the best exact formulas, or the complexity of a particular
> exact formula e.g. the closed form involving Sqrt[5].
>
> Below is computed exactly, then numericized. It is not done using any
> formula involving Sqrt[5].
>
> In[2]:= Timing[ff = Fibonacci[5000000];]
> Out[2]= {0.59 Second, Null}
>
> In[3]:= InputForm[N[ff]]
> Out[3]//InputForm=
> 7.108285972058527236971171956172`15.954589770191005*^1044937
>
> Likewise the GMP result you site is computed using an exact method
> (probably about the same as what we do).
>
>
> Daniel Lichtblau
> Wolfram Research
>


--

Michael Taktikos

unread,
Aug 1, 2004, 6:50:18 PM8/1/04
to

"Daniel Lichtblau" <da...@wolfram.com> wrote:

> > There are very fast algorithms for computing Fibonacci numbers not using
the exact
> > formula.
> > For instance, GMP (GNU Multiple Precision Arithmetic Library)

[snip]


> > ---------------------------------------------
> > The result of executing fib (5000000) is:
> > computation took 466 ms
> > result is about 1044938 digits, not printing it
> > ---------------------------------------------

In the most cases, when we look at so large Fibonacci numbers, we are only
intereted in the first
and the last digits (in Mathematica by using the function Short).
Remembering that the last d digits of Fibonacci numbers are repeating for
d=1, 2, 3, ...
with the periods 60, 300, 1500, ..., 15*10^(d-1),

we can use the following superfast computation which gives the first f and
the last l digits and the number of unshown digits:

fiboNewShort[k_, f_, l_]:=Module[{erg,m,fibmaeder,lastDigits},
fibmaeder[n_]:=
Module[{r11=1,r12=0,r22=1,digits=IntegerDigits[n-1,2],i,t},


Do[If[digits[[i]]==1,{r11,r22}={r11(r11+2r12),r12(r11+r22)};
r12=r11-r22,t=r12(r11+r22);
{r11,r12}={r11(r11+2r12)-t,t};

r22=r11-r12],{i,Length[digits]-1}];
If[digits[[-1]]==1,r11(r11+2r12),r11(r11+r22)-(-1)^((n-1)/2)]];
lastDigits[n_, d_]:=Module[{pis,zyk},
Which[d==1,zyk=60,d==2,zyk=300, d>2, zyk=15*10^(d-1)];
Mod[fibmaeder[Mod[n,zyk]],10^d]];
m=MantissaExponent[ N[GoldenRatio^k/(2*GoldenRatio-1),35]];
erg=SequenceForm[Floor[m[[1]]*10^f],"<<",m[[2]]-f-l,
">>",lastDigits[k,l]];
erg]

Now we test the build-in function with Fibonacci[1000000], and apply the
command Short: Then we see the 38 first and the 39 last digits.

Timing[Short[Fibonacci[1000000]]]

{0.10 Second,
19532821287077577316320149475962563324<<208911>>
684684301719893411568996526838242546875}

Our function can simulate this:

Timing[fiboNewShort[1000000,38,39]]

{0 Second,
19532821287077577316320149475962563324<<208911>>
684684301719893411568996526838242546875}

Since the last digits are more time expansive than the first, when we apply
large values we should try not so many last as first digits - example: 20
first and only 6 last digits:

Timing[fiboNewShort[10^9,20, 6]]

{0.16 Second,
79523178745546834678<<208987614>>546875}

As you surely have seen, for the last digits I used the algorithm of Maeder
and for the first digits
my own formula. However, I think this is not unbeatable, and would be
thankful for suggestionsto make it faster...

Ed Pegg Jr

unread,
Aug 7, 2004, 4:16:03 AM8/7/04
to
For finding the number of digits in any sufficently large Fibonacci
number in base 10, let k = (ArcCsch[2])/Log[10]. The number of
digits in Fibonacci[n] is Round[n k].

k ~ 0.20898764024997873376927208923755541682245923991821

Fibonacci[10^9] has 10^9 k ~ 208987640 digits.

--Ed Pegg Jr
www.wolfram.com
www.mathpuzzle.com
www.maa.org columnist

0 new messages