I spoke about this at the Dyalog 2008 conference. The technique suffices to handle tall as well as wide matrices, and works for any associative and commutative function (not just +). The analysis for higher-ranked arrays is similar.
The key idea is this. Suppose you have a matrix b of bits. ] b=: 17 6 $ i. 6 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 The columns are labelled by the column indices. To compute +/b, you need to add up all the bits having the same column indices. 6 *. 8 24 ] b1=: 5 24 ($,) b,3 6$0 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 If you conceptually reshape the matrix into one having 6*.8 columns, the column indices are still lined up, but the conceptual matrix now has a nice multiple of 8 columns, whence you don't have do finicky bit picking except on a final small number of subtotals. The sum then is (24$i.6) +//. +/b1 ----- Original Message ----- From: Raul Miller <[email protected]> Date: Tuesday, September 7, 2010 11:26 Subject: Re: [Jprogramming] Splitting an integer into its digits To: Programming forum <[email protected]> > On Tue, Sep 7, 2010 at 11:41 AM, Roger Hui <[email protected]> wrote: > > The same arguments but +/b instead of +/"1 b is even more amusing. > > Bit booleans are great for arrays with fat rows. You can > handle the > "end pieces" the simple and not so efficient way and still get enough > of a speedup from the rest of the row that they are fast. > > But I shudder when I think about skinny arrays. > > -- > Raul ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
