I guess the point of this contest is to test (the speed of) recursion?
If that's so, you probably don't care about the closed-form (non-recursive)
version of the Fibonacci
function found in ~system/examples/graphics/plot/plexam.ijs:
fib=: 3 : ';/|:+.(%:5)%~(p^y)-(-.p)^y[p=.-:>:%:5'
Besides being faster than the recursive versions by orders of magnitude,
this one
is not restricted to positive integer arguments. The demo that contains it
- text in "DLINE2" -
gives a nice illustration of the plot of this continuous version.
(I like to remove the "+." part of this and directly get the complex results
for negative
arguments.)
Playing around with recursive versions myself, I came up with explicit and
tacit
versions like this:
NB.* fibre: Fibonacci recursive explicit
fibre=: 3 : 0
if. y e. 0 1 2 do. y{0 1 1
else. +/(fibre"0) y-2 1 end.
)
NB.* fibrt: Fibonacci recursive tacit
fibrt=: (0 1 1{~])`([:+/([:(fibrt"0)2 1-~])) @. (2<])
These have the following timings on my 2 GHz laptop:
6!:2 'fibre 30'
14.434402
6!:2 'fibrt 30'
10.348812
(Closed-form timing is neglible: about 8.4e_5 seconds)
As you can see, I special-case the first three integer arguments. Looking
at Terrence's
version, I realized he only special-cases the "base_case" of 1. Since the
members of
the Fibonacci series are fixed for all time and the special-casing greatly
affects the depth
of the recursion, it occurred to me to examine how much this affects the
timing.
I found that these versions
NB.* fibrt10: Fibonacci recursive tacit: special-case 1st 10 > 0
fibrt10=: (0 1 1 2 3 5 8 13 21 34 55{~])`([:+/([:(fibrt10"0)2 1-~])) @.
(10<])
NB.* fibre10: Fibonacci recursive explicit: special-case 1st 10 > 0
fibre10=: 3 : 0
if. y<11 do. y{0 1 1 2 3 5 8 13 21 34 55
else. +/(fibre10"0) y-2 1 end.
)
were considerably faster:
6!:2 'fibre10 30'
0.36031507
6!:2 'fibrt10 30'
0.2905657
Of course, this is because they reduce recursion. Which, to my mind, brings
into
question the whole project: why compare recursive versions for speed when
the
greatest speed-up comes from doing away with recursion?
Also, I find the closed-form version much more interesting - it's really
better in numerous
ways than the recursive version.
Anyway, my two cents....
Devon
On 5/19/07, Terrence Brannon <[EMAIL PROTECTED]> wrote:
It would help if I were thinking of fibonacci and not factorial... i
was expecting
fib 5 to be 120... lol.
this program works:
t =: 3 : 'y > 1'
fib =: base_case ` rec_case @. t
rec_case =: 3 : '( fib (y-1) ) + ( fib (y-2) )'
base_case =: 1:
fib 3
3
fib 4
5
fib 5
8
fib 6
13
On 5/19/07, Raul Miller <[EMAIL PROTECTED]> wrote:
> On 5/19/07, Raul Miller <[EMAIL PROTECTED]> wrote:
> > t should be either
> > t=:>&1
> >
> > or, if you prefer
> > t=:1 < ]
>
> Other valid definitions include
> t=: ] > 1:
> and
> t=: > 1:
>
> and, of course
> t=:1: < ]
>
> --
> 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
--
Devon McCormick, CFA
^me^ at acm.
org is my
preferred e-mail
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
