In Julia (from my console): julia> fib(n) = ([big(1) 1; 1 0]^n)[1,2] fib (generic function with 1 method)
julia> @time x=fib(475000); elapsed time: 1.389054075 seconds (120836244 bytes allocated, 2.44% gc time) julia> Julia implements BigInt using GMP so it is really fast. It trades space for speed! I agree about using GMP/MPFR in J for extended integers. I have little experience to help out with such an effort but not enough to undertake to implement much of it. On Wed, Sep 2, 2015 at 10:56 AM, Mike Day <mike_liz....@tiscali.co.uk> wrote: > 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
