Fibonacci [5,000,000] contains 1044938 decimal digits
- To: mathgroup at smc.vnet.net
- Subject: [mg17117] Fibonacci [5,000,000] contains 1044938 decimal digits
- From: Alex Vinokur <alexander.vinokur at telrad.co.il>
- Date: Sat, 17 Apr 1999 03:35:11 -0400
- Organization: Deja News - The Leader in Internet Discussion
- Sender: owner-wri-mathgroup at wolfram.com
Hi,
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.
//============================================================
In order to compute above-mentioned Fibonacci numbers
the special class titled DesirableLongInt was defined.
The are two versions of this class :
- first one based on the STL vector class
(vector<unsigned long int>);
- second one based on the STL basic_string class
(basic_string<unsigned long int>).
DesirableLongInt number contains as many digits as it requires
(at least 1,000,000 decimal digits). There is no need to think
of the calculation precision beforehand.
The bc utility (arbitrary precision arithmetic language) was also
used to calculate the Fibonacci numbers.
//============================================================
Here are the experiment results
Comparative table.
================================================================
| | About Fib [n] |
| |----------------------------------------------------|
| Index n | Decimal | Calculation time (hh:mm:ss) |
| | Digits |-----------------------------------------|
| | | DesirableLongInt | bc utility |
| | |----------------------------| |
| | | vector | basic_string | |
|--------------------------------------------------------------|
| 100000 | 20899 | 1:08.30 | 1:33.94 | 1:39.40 |
| 500000 | 104494 | 26:38.46 | 38:41.73 | 40:21.01 |
| 1000000 | 208988 | 1:42:43.78 | 2:35:08.71 | 2:39:51.56 |
| 5000000 | 1044938 | 43:00:17.66 | 63:34:31.07 | None |
================================================================
Conclusion. Although Fib[5,000,000] was calculated,
these methods are unacceptable to calculate Fib [1,000,000+]
because it takes too long time.
The question is, if is there any EXPLICIT method
that calculates ALL digits Fib [5,000,000+] and
takes acceptable time?
//============================================================
What was Fib [5,000,000] calculated for?
Here are some reasons.
A) It is always helpful to know what are the limits of
*our+computer* possibilities.
B) About Fib [5,000,000] itself. What to do with it?
The things needless today become necessary earlier
than we suppose.
C) About the methods of the large Fibonacci numbers calculation.
The (successful or unsuccessful) approach intended
to solve one problem are quite often adopted & adapted
to solve another ones.
D) So-called (n+1)-th reason, i.e., incomprehensible today.
Sometimes such reason is made known in the course of time.
Sometimes it isn't.
//============================================================
//#########################################################
//------------------- Compiler & System ------------------
g++ -v : gcc version egcs-2.91.57 19980901
(egcs-1.1 release)
uname -a : SunOS <nodename> 5.6 Generic_105181-11
sun4u sparc SUNW,Ultra-60-09
psrinfo -v : -> The sparc processor operates at 360 MHz
//---------------------------------------------------------
Thanks,
Alex
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own