Mathematica 9 is now available
Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2004
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

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: [mg49627] Re: Fibonacci [5,000,000] contains 1044938 decimal digits
  • From: alexvn at bigfoot.com (Alex Vinokur)
  • Date: Sun, 25 Jul 2004 02:55:29 -0400 (EDT)
  • References: <7f4ffu$6dj$1@nnrp1.dejanews.com>, <Mo2OZGACWlF3Ewez@raos.demon.co.uk>, <7g0qsd$dr9@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

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: RE: In Plot, horizontal range is reduced depending on PlotRange
  • Next by Date: Long function defintions
  • Previous by thread: Re: Nullspace
  • Next by thread: Re: Fibonacci [5,000,000] contains 1044938 decimal digits