That is a big factor but perhaps it is not quite a surprise to some members
of this forum. Yes, I would like to see the Haskell version please; thanks
in advance.
It seems that if one wants to play with "arbitrary precision arithmetic,
operating on signed integers, rational numbers, and floating-point
numbers" efficiently,
one would have to use Haskell, Mathematica or a another language that
implements GMP (hopefully J will not be left behind for too long in this
area).
On Wed, Sep 2, 2015 at 2:48 PM, aai <agroeneveld...@gmail.com> wrote:
> 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
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
