Some additional timings on my machine and comparison to MIcroJ
In J:
fib3=. ({: @:(({: , +/)@:]^:(2-~[))&1 1x) NB. For y >: 3!
6!:2 'fib3 475000'
60.7922
NB. fib test
fibtest =: 3 : 0
x1 =. 1x
x2 =. 1x
c =. 0
while. c < (y-2) do.
tmp =. x1
x1 =. x2
x2 =. tmp + x1
c=.c+1
end.
x2
)
6!:2 'fibtest 475000'
61.5696
NB. test does it speed things up if the c and while check are eliminated:
NB. fib test
fibtest2 =: 3 : 0
x1 =. 1x
x2 =. 1x
for_c. i. (y-2) do.
tmp =. x1
x1 =. x2
x2 =. tmp + x1
end.
x2
)
6!:2 'fibtest2 475000'
55.7621
In MicroJ:
I added basic BigInteger support[1].
NB. fib test
fibtest =: 3 : 0
x1 =. (3!:101) 1 NB. convert to bignum
x2 =. (3!:101) 1
c =. 0
while. c < (y-2) do.
tmp =. x1
x1 =. x2
x2 =. tmp + x1
c=.c+1
end.
x2
)
6!:2 'fibtest 475000'
46.2624291
NB. fib with for.
fibtestx =: 3 : 0
x1 =. (3!:101) 1 NB. convert to bignum
x2 =. (3!:101) 1
for_c. i. (y-2) do.
tmp =. x1
x1 =. x2
x2 =. tmp + x1
end.
x2
6!:2 'fibtestx 475000'
26.0208426
So in my implementation of MicroJ, it is nearly a factor 2 to use a for
instead of a while since the check and increment can be eliminated[2]
That got me thinking, a for loop would be a perfect candidate for a hotspot
JIT. As a proof of concept, I replaced my c# code with this:
names["tmp"] = names["x1"];
names["x1"] = names["x2"];
names["x2"] = math((A<BigInteger>)names["tmp"], (A<BigInteger>)names["x1"],
(a, b) => a + b);
6!:2 'fibtestx 475000'
8.2506247
So the best I can do with C# at present looks to be about 8.25 seconds
Ideally that code would be generated automatically by the interpreter and
just in time compiled. Here's a crude implementation[3], [4] and resulting
performance:
6!:2 'fibtestx 475000'
8.4406424
It's effectively the same speed as f7a on my machine in jconsole (untested
on MicroJ as those primitives are not yet implemented)
6!:2 'f7a 475000'
8.69614
1 -
https://msdn.microsoft.com/en-us/library/system.numerics.biginteger(v=vs.110).aspx
2 - https://github.com/joebo/microj/blob/master/primitives.cs#L1307
3 - https://github.com/joebo/microj/blob/master/primitives.cs#L1299
4 - https://github.com/joebo/microj/blob/master/primitives.cs#L1209
On Wed, Sep 2, 2015 at 3:11 PM, Murray Eisenberg <mur...@math.umass.edu>
wrote:
> 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
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
