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

• To: mathgroup at smc.vnet.net
• Subject: [mg49656] Re: Fibonacci [5,000,000] contains 1044938 decimal digits
• From: drbob at bigfoot.com (Bobby R. Treat)
• Date: Mon, 26 Jul 2004 04:02:00 -0400 (EDT)
• References: <7f4ffu\$6dj\$1@nnrp1.dejanews.com>, <Mo2OZGACWlF3Ewez@raos.demon.co.uk>, <7g0qsd\$dr9@smc.vnet.net> <cdvm0e\$7hv\$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

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

alexvn at bigfoot.com (Alex Vinokur) wrote in message news:<cdvm0e\$7hv\$1 at smc.vnet.net>...
> On 26 Apr 1999 00:42:53 -0400, Alex Vinokur wrote:
> >In article <Mo2OZGACWlF3Ewez at raos.demon.co.uk>,
> >  Sunil Rao <sunil.rao at ic.ac.uk> wrote:
> >> Alex Vinokur <alexander.vinokur at 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
> >>
> >> 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:alexvn at 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);
>
>
>     }
>
>     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
>   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

```

• Prev by Date: Fibonacci[1,000,000,000] contains 208,987,640 decimal digits (was: Fibonachi[5,000,000] contains 1044938 decimal digits)
• Next by Date: about principal components analysis (PCA)
• Previous by thread: Re: Fibonacci [5,000,000] contains 1044938 decimal digits
• Next by thread: Long function defintions