Oh I missed f7. I think I gave up after f4, assuming the ones after that were mathematical curiosities and notsuitable for big numbers. f7 is pretty fast. I got 8.3 seconds on my Ubuntu (32-bit) PC.
> Date: Wed, 2 Sep 2015 15:56:33 +0100 > From: mike_liz....@tiscali.co.uk > To: programm...@jsoftware.com > Subject: Re: [Jprogramming] Comparing J speed > > Yes, the Jwiki verb f7 using a binary power method is fast > and quite compact. (My own version, twice as slow as f7 for > some reason, has two current 2x2 matrices, so presumably > needs to store 8 extended integers at a time; the final > number is about 2^330000 (!), so even 8 such integers will > use a fair amount of space. Space for my version for 475000 > is about 5MB, while it's about 5.6MB for f7 .) > > The Haskell implementation must be really tight, though. > Rademacher talks about lazy evaluation, but his function > _appears_ to employ a list of all prior Fibonacci numbers > to produce the required element. I suppose the zip and > tail functions somehow know to discard the prior elements. > He showed how an interpreted (I think) Haskell fib function > was memoized in a certain case, which I forget; even then > it was impressively fast and not excessive in memory > consumption. > > Now/how to program the binary power method in Haskell?! > > I keep having problems with space and time using extended > integers, so implementing the GMP method/s would be > interesting, but I don't have the skills for doing it! > > Thanks, > > Mike > > On 02/09/2015 14:03, David Lambert wrote: > > Essays > > http://www.jsoftware.com/jwiki/Essays/Fibonacci%20Sequence > > > > Fibonacci numbers by matrix product: > > > > A=:2 2$1 1 1 2 > > mp=:+/ .* > > mp~A > > 2 3 > > 3 5 > > mp~^:4 x:A > > 1346269 2178309 > > 2178309 3524578 > > > > Then multiply specific matrices to find a particular Fibonacci number. > > From Wolfram Alpha the entry for 1346269 says > > > > 1346269 is the 31st Fibonacci number (F_31). > > > > 1346269 is the hypotenuse of 2 primitive Pythagorean triples: > > 1346269^2 = 184981^2+1333500^2 = 602069^2+1204140^2 > > > > > >> Date: Wed, 2 Sep 2015 01:32:45 +0100 > >> From: Jon Hough<jgho...@outlook.com> > >> To:"programm...@jsoftware.com" <programm...@jsoftware.com> > >> Subject: [Jprogramming] Comparing J speed > >> Message-ID:<dub125-w26a3268198fcd76285843ac...@phx.gbl> > >> Content-Type: text/plain; charset="iso-8859-1" > >> > >> In this talkhttps://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. > > > > ---------------------------------------------------------------------- > > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
