MathGroup Archive 2004

[Date Index] [Thread Index] [Author Index]

Search the Archive

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
>  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: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);
> 
>       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


  • 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