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
