Actually, thinking about this, the performance for finding the 475000th fibonacci number is going to be dominated by the performance of extended precision addition (it's much larger than the largest representable floating point number). And J's current implementation while rather portable is not optimized for speed.
Unless you build your own implementation, or find some nice analytic shortcuts... -- Raul On Tue, Sep 1, 2015 at 8:32 PM, Jon Hough <jgho...@outlook.com> wrote: > 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
