Here's another one that mimics the zip/tail from the talk
fib=: [: {. [: _2&{. [: ([: +/"1 [: (}: ,. }.) 1,1,]) / [: i. 1&-
Slow though:
timespacex 'fib 1000'
0.0179245 59648
timespacex 'fib 10000'
0.638343 919808
I killed it after an hour running 475000
You can play with it with this version in MicroJ: {. _2 {. ([: +/"1 [: (}:
,. }.) 1,1,])/(i. 475000)
MicroJ doesn't have bignum support yet so it overflows after 100, but still
you might find it interesting to debug to see how it works
On Wed, Sep 2, 2015 at 11:15 AM, Raul Miller <rauldmil...@gmail.com> wrote:
> On Wed, Sep 2, 2015 at 10:56 AM, Mike Day <mike_liz....@tiscali.co.uk>
> wrote:
> > 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.
>
> Right...
>
> The haskell computational model is that nothing ever changes - it's
> the compiler's job to go through the code and discard values which
> cannot be reached. So, in some sense, everything is memoized.
>
> This works great when it works, and is painful to debug when it
> doesn't work. You just sort of have to learn how to avoid things that
> make you run out of memory. (J can get you into analogous "not enough
> memory" territory, though the things that get you in trouble are
> different, with J.) Then again, maybe that sort of pain makes the
> working examples seem that much sweeter.
>
> The ghci "haskell interpreter" is a wrapper around the compiler (and
> that compiler - somewhat like J - represents decades of work by a
> number of people). Each statement gets sent to the compiler. I think
> previous statements are treated as modules which are dynamically
> linked or something like that - but my experience there is not very
> adequate, and I am mostly guessing.
>
> I guess this part of thread is drifting away from programming forum
> and into territory which probably belongs in either the chat or source
> forums...
>
> Thanks,
>
> --
> Raul
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
