Even without the rep. squaring in J of f7a the Haskell version is ~ 33x
faster in the GHCi interpreter. If you want to check it yourself I'll
e-mail you the Haskell code (to avoid remarks of Raul).
Op 2-9-2015 om 20:03 schreef Jose Mario Quintana:
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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
