The savings, including the reported space usage, are indeed impressive!
t0=: 0:`1:`(($:&<:+(-+:) $: ])`(+/@:($:
i.@>:)@<.@-:@[)@.(0=])`0:@.(2|-))@.(1+*@-)
"0
f0=: <@({: t0 ])\@i.
t1=: 0:`1:`(($:&<:+(-+:) $: ])`(+/@:($:
i.@>:)@<.@-:@[)@.(0=])`0:@.(2|-))@.(1+*@-)
M."0
f1=: <@({: t1 ])\@i. M.
( f2=. f1 f. ) NB. Using the scope for recursion (103!:0) extension:
http://www.jsoftware.com/pipermail/programming/2013-March/031835.html
<@({: 0:`1:`(($:&<: + (- +:) $: ])`(+/@:($: i.@>:)@<.@-:@[)@.(0 = ])`0:@.(2
| -))@.(1 + *@-)M."0 (103!:0) ])\@i.M.
st
7!:2@:] ; 6!:2
st'f0 50'
┌─────┬──────────┐
│46784│6.19811211│
└─────┴──────────┘
st'f1 50'
┌───┬────────────┐
│832│0.0100949664│
└───┴────────────┘
st'f2 50'
┌───┬─────────────┐
│832│0.00793115699│
└───┴─────────────┘
,. o f2 9
┌─────────────────┐
│1 │
├─────────────────┤
│0 1 │
├─────────────────┤
│1 0 1 │
├─────────────────┤
│0 2 0 1 │
├─────────────────┤
│2 0 2 0 1 │
├─────────────────┤
│0 4 0 2 0 1 │
├─────────────────┤
│3 0 5 0 2 0 1 │
├─────────────────┤
│0 7 0 5 0 2 0 1 │
├─────────────────┤
│5 0 9 0 5 0 2 0 1│
└─────────────────┘
On Wed, May 1, 2013 at 5:11 AM, Aai <[email protected]> wrote:
> From the seqfan forum I picked up the computing of the following triangle:
>
> ({.~1+1 i:~ '1'=])"1 ": > F 10
> 1
> 0 1
> 1 0 1
> 0 2 0 1
> 2 0 2 0 1
> 0 4 0 2 0 1
> 3 0 5 0 2 0 1
> 0 7 0 5 0 2 0 1
> 5 0 9 0 5 0 2 0 1
> 0 12 0 10 0 5 0 2 0 1
>
> The terms on a row are computed recursively (see verb xT and T).
>
> The triangle can be computed with J as follows:
>
> 1. explicit
>
> xT=: 4 :0 "0
> select. * x-y
> case. _1 do. 0
> case. 0 do. 1
> case. do.
> if. 1=2| x-y do. 0 return. end.
> if. 0=y do. +/ (xT i.@>:)<.-: x else. (x xT&<: y) + (x-+:y) xT y end.
> end.
> )
>
> xF=: <@({: xT ])\@i.
>
> or
>
> 2. tacit:
>
> T=: 0:`1:`(($:&<:+(-+:) $: ])`(+/@:($:
> i.@>:)@<.@-:@[)@.(0=])`0:@.(2|**-))@.(1+*@-)
> "0
> F=: <@({: T ])\@i.
>
>
> example:
>
> ,. F 9
> ┌─────────────────┐
> │1 │
> ├─────────────────┤
> │0 1 │
> ├─────────────────┤
> │1 0 1 │
> ├─────────────────┤
> │0 2 0 1 │
> ├─────────────────┤
> │2 0 2 0 1 │
> ├─────────────────┤
> │0 4 0 2 0 1 │
> ├─────────────────┤
> │3 0 5 0 2 0 1 │
> ├─────────────────┤
> │0 7 0 5 0 2 0 1 │
> ├─────────────────┤
> │5 0 9 0 5 0 2 0 1│
> └─────────────────┘
>
>
> The interesting thing here is the major speed up by applying double
> memoization:
> ( I use the tacit verbs)
>
> T=: 0:`1:`(($:&<:+(-+:) $: ])`(+/@:($:
> i.@>:)@<.@-:@[)@.(0=])`0:@.(2|**-))@.(1+*@-)
> M."0
> F=: <@({: T ])\@i. M.
>
> You can follow the stepwise speed up by first adding M. to T and after
> that also to F and comparing the timings. The speed up is huge.
>
>
> FYI.
>
>
> BTW the triangle is of some interest: try summing the rows
>
>
>
>
> --
> Met vriendelijke groet,
> @@i = Arie Groeneveld
>
> ------------------------------**------------------------------**----------
> For information about J forums see
> http://www.jsoftware.com/**forums.htm<http://www.jsoftware.com/forums.htm>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
