Pace Raul, I'll post this here as it compares a J verb's speed with
yet another Haskell fib function, and is arguably relevant to thoughts
about efficient implementations of exact integer calculations in
our language of choice. I don't really want to learn Haskell....
Google easily leads to a Haskell wiki page on Fib functions,
https://wiki.haskell.org/The_Fibonacci_sequence#A_version_using_some_identities
In particular it shows the "Fastest fib in the West". I've downloaded
Haskell (a mere 1.6 GB!!!) and got it to run that function for
fib(475000).
On my machine it reports a time of 0.58 sec and space of 87 MB.
This compares with the Jwiki f7 verb running in 19 sec and 5 MB.
I suppose f7 is doing about 30 matrix multiplications with ever
larger arguments.
I'm surprised at the 87MB compared with J's 5MB, always
assuming these are commensurate.
Thanks for your patience,
Mike
On 02/09/2015 21:51, Joe Bogner wrote:
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
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
