Re: contains 1044938 decimal digits)
- To: mathgroup at smc.vnet.net
- Subject: [mg49803] Re: contains 1044938 decimal digits)
- From: "Michael Taktikos" <michael.taktikos at hanse.net>
- Date: Sun, 1 Aug 2004 18:48:34 -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> <ce2ftd$8rh$1@smc.vnet.net> <200407271100.HAA11140@smc.vnet.net> <ceap6b$aej$1@smc.vnet.net> <200407310714.DAA12036@smc.vnet.net> <cei901$2jt$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
"Daniel Lichtblau" <danl at wolfram.com> wrote:
> > There are very fast algorithms for computing Fibonacci numbers not using
the exact
> > formula.
> > For instance, GMP (GNU Multiple Precision Arithmetic Library)
[snip]
> > ---------------------------------------------
> > The result of executing fib (5000000) is:
> > computation took 466 ms
> > result is about 1044938 digits, not printing it
> > ---------------------------------------------
In the most cases, when we look at so large Fibonacci numbers, we are only
intereted in the first
and the last digits (in Mathematica by using the function Short).
Remembering that the last d digits of Fibonacci numbers are repeating for
d=1, 2, 3, ...
with the periods 60, 300, 1500, ..., 15*10^(d-1),
we can use the following superfast computation which gives the first f and
the last l digits and the number of unshown digits:
fiboNewShort[k_, f_, l_]:=Module[{erg,m,fibmaeder,lastDigits},
fibmaeder[n_]:=
Module[{r11=1,r12=0,r22=1,digits=IntegerDigits[n-1,2],i,t},
Do[If[digits[[i]]==1,{r11,r22}={r11(r11+2r12),r12(r11+r22)};
r12=r11-r22,t=r12(r11+r22);
{r11,r12}={r11(r11+2r12)-t,t};
r22=r11-r12],{i,Length[digits]-1}];
If[digits[[-1]]==1,r11(r11+2r12),r11(r11+r22)-(-1)^((n-1)/2)]];
lastDigits[n_, d_]:=Module[{pis,zyk},
Which[d==1,zyk=60,d==2,zyk=300, d>2, zyk=15*10^(d-1)];
Mod[fibmaeder[Mod[n,zyk]],10^d]];
m=MantissaExponent[ N[GoldenRatio^k/(2*GoldenRatio-1),35]];
erg=SequenceForm[Floor[m[[1]]*10^f],"<<",m[[2]]-f-l,
">>",lastDigits[k,l]];
erg]
Now we test the build-in function with Fibonacci[1000000], and apply the
command Short: Then we see the 38 first and the 39 last digits.
Timing[Short[Fibonacci[1000000]]]
{0.10 Second,
19532821287077577316320149475962563324<<208911>>
684684301719893411568996526838242546875}
Our function can simulate this:
Timing[fiboNewShort[1000000,38,39]]
{0 Second,
19532821287077577316320149475962563324<<208911>>
684684301719893411568996526838242546875}
Since the last digits are more time expansive than the first, when we apply
large values we should try not so many last as first digits - example: 20
first and only 6 last digits:
Timing[fiboNewShort[10^9,20, 6]]
{0.16 Second,
79523178745546834678<<208987614>>546875}
As you surely have seen, for the last digits I used the algorithm of Maeder
and for the first digits
my own formula. However, I think this is not unbeatable, and would be
thankful for suggestionsto make it faster...
Greetings from Hamburg,
Michael Taktikos