Actually, the tacit version seems to be faster for relatively small
arguments. First allow me to rewrite fib1
fib2 and your expression as verbs working with extended precision and
producing the yth Fibonacci number:
fib1 =:1x"_`(($:@:<:) + ($:@:-&2))@.(2&<)M.
fib2 =: 3 : 0
x1 =. x:1
x2 =. x:1
c =. 0
while. c < (y-2) do.
tmp =. x1
x1 =. x2
x2 =. tmp + x1
c=.c+1
end.
x2
)
fib3=. ({: @:(({: , +/)@:]^:(2-~[))&1 1x) NB. For y >: 3!
Checking,
(fib1"0 ; fib2"0 ; fib3"0) 3 4 5 6 7
┌──────────┬──────────┬──────────┐
│2 3 5 8 13│2 3 5 8 13│2 3 5 8 13│
└──────────┴──────────┴──────────┘
(fib1 , fib2 , fib3) 111
70492524767089125814114 70492524767089125814114 70492524767089125814114
Comparing their performance,
st=. (, */&.:>@:(1 2&{))@:(] ; 7!:2@:] ; 6!:2)
st&> 'fib1 5555';'fib2 5555';'fib3 5555'
┌─────────┬─────┬────────────┬──────────┐
│fib1 5555│1664 │0.0823093021│136.962679│
├─────────┼─────┼────────────┼──────────┤
│fib2 5555│24704│0.0457517422│1130.25104│
├─────────┼─────┼────────────┼──────────┤
│fib3 5555│23168│0.0209733696│485.911027│
└─────────┴─────┴────────────┴──────────┘
For large arguments, as Groeneveld pointed out, the performance is
dominated by the extended precision
calculations (at least for this method),
st&> 'fib2 475000';'fib3 475000'
┌────────────┬───────┬──────────┬──────────┐
│fib2 475000│1315200│43.1150201│56704874.5│
├────────────┼───────┼──────────┼──────────┤
│fib3 475000│1313664│44.0851651│57913094.4│
└────────────┴───────┴──────────┴──────────┘
The verb f7 (see,
http://www.jsoftware.com/jwiki/Essays/Fibonacci%20Sequence#Sum_of_binomial_coefficients
) and its tacit counterpart (f7a) are indeed much faster (but they use more
space),
f7a=. {.@:{:@:(+/ .*/)@:(+/ .*~@:]^:(I.@:|.@:#:@:[))&(2 2$0 1 1 1x)
(f7 , f7a)111
70492524767089125814114 70492524767089125814114
fib1 =:1x"_`(($:@:<:) + ($:@:-&2))@.(2&<)M. NB. Resetting M.
st&> 'fib1 5555';'fib2 5555';'fib3 5555';'f7 5555';'f7a 5555'
┌─────────┬──────┬────────────┬──────────┐
│fib1 5555│1664 │0.0873909161│145.418484│
├─────────┼──────┼────────────┼──────────┤
│fib2 5555│24704 │0.0456825483│1128.54167│
├─────────┼──────┼────────────┼──────────┤
│fib3 5555│23168 │0.0185578731│429.948804│
├─────────┼──────┼────────────┼──────────┤
│f7 5555 │122368│0.002491974 │304.937875│
├─────────┼──────┼────────────┼──────────┤
│f7a 5555 │88576 │0.0024376783│215.919793│
└─────────┴──────┴────────────┴──────────┘
st&> 'fib3 475000';'f7 475000';'f7a 475000'
┌────────────┬───────┬──────────┬──────────┐
│fib3 475000│1313664│39.7395458│52204410.8│
├────────────┼───────┼──────────┼──────────┤
│f7 475000 │5551232│8.97002017│49794663 │
├────────────┼───────┼──────────┼──────────┤
│f7a 475000 │5415168│7.95243101│43063749.9│
└────────────┴───────┴──────────┴──────────┘
However, we are comparing apples to oranges now. Then again, maybe that
was the case from the start; but, be that as it may, I wonder how the
Haskell version compares to f7/f7a in the same machine... Does anyone know?
On Tue, Sep 1, 2015 at 10:34 PM, 'Pascal Jasmin' via Programming <
programm...@jsoftware.com> wrote:
> equivalent to your explicit function, but slow on my computer
>
> timespacex '({: , +/)^:(474998) 1 1x '
> 63.3016 1.31469e6
>
>
> Your's may be faster due to special code for inplace assignments.
>
> but there may be shortcuts to finding a direct fib number.
>
>
> ----- Original Message -----
> From: Jon Hough <jgho...@outlook.com>
> To: "programm...@jsoftware.com" <programm...@jsoftware.com>
> Cc:
> Sent: Tuesday, September 1, 2015 8:35 PM
> Subject: Re: [Jprogramming] Comparing J speed
>
> Apologies for the messed up fib2, I'm seriously considering dumping
> outlook.com.
>
> > From: jgho...@outlook.com
> > To: programm...@jsoftware.com
> > Date: Wed, 2 Sep 2015 01:32:45 +0100
> > Subject: [Jprogramming] Comparing J speed
> >
> > In this talk https://www.youtube.com/watch?v=apBWkBDVlow
> > the presenter attempts to show Haskell hasn't sacrificed speed for
> expressiveness by comparing a Java Fibonacci calculator to his Haskell
> one.(skip to the 18:00 mark).Essentially, to calculate the 475000th
> Fibonacci number, it took his Java program ~8 seconds, while the very terse
> Haskell program took ~6 seconds.
> > So I tried to do the same in J. My first attempt, used a tacit, memoized
> verb
> > fib1 =:1:`(($:@:<:) + ($:@:-&2))@.(2&<)M.
> >
> >
> > However, this gives a stack error for large numbers (~100000). So I
> decided to make an imperative verb,
> >
> >
> > fib2 =: 3 : 0 x1 =. x:1 x2 =. x:1 c =. 0 while. c < y do. tmp =. x1 x1
> =. x2 x2 =. tmp + x1 c=.c+1 end. x2
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > )
> >
> >
> > This gets there, I can calculate the 475000th Fibonacci number, but
> >
> >
> > timespacex 'fib2 475000'
> >
> >
> >
> >
> > 36.183 1.31558e6
> >
> >
> > It takes 36 seconds (of course, my hardware is different to that in the
> presentation, but still...).
> >
> >
> > Is there a speedier way to do this in J? Preferably a tacit one liner
> would also be good.
> >
> >
> > Thanks,
> > Jon
> >
> >
> > ----------------------------------------------------------------------
> > For information about J forums see http://www.jsoftware.com/forums.htm
>
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
