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