J does seem very awfully slow in executing, e.g., fib3 475000. On my iMac, that
gives a timing of over 38 seconds.
By contrast -- and to the extent that the timers involved can reasonably be
compared -- on the same system, running the Wolfram Language looping definition
fib[n_] := Module[{fi = 1, fi1 = 0}, Do[{fi, fi1} = {fi + fi1, fi}, {n -
1}]; fi]
in Mathematica 10.2 gives execution speed of just over 1.08 seconds for
fib[475000].
(And the built-in function Fibonacci executes for argument 475000 at the
astonishing speed of 0.0021 seconds!)
Although the internals of Mathematica are proprietary, the docs say that
high-precision arithmetic is implemented by means of GMP.
> On 2 Sep 2015 14:03:24 -040, Jose Mario Quintana
> <jose.mario.quint...@gmail.com> wrote:
>
>
> 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?
> ????????????????????????????????????????????
....
——
Murray Eisenberg mur...@math.umass.edu
Mathematics & Statistics Dept.
Lederle Graduate Research Tower phone 240 246-7240 (H)
University of Massachusetts
710 North Pleasant Street
Amherst, MA 01003-9305
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
