[Jprogramming] Generating Lookup Tables (LUTs)

Thu Oct 13 06:34:42 UTC 2016

I've tried to clean up the code to be more explanatory. All we really care
about is generating L2 given an arbitrary Y. Rewriting this has also helped
me catch a subtle bug with arrays going left-to-right but #. and #:
interpreting numbers right-to-left.

   NB. X and Y are completely arbitary and are chosen to be
   NB. easy to trace.
   ] X =. 0 1 1 0 1
0 1 1 0 1
   ] Y =. |.=/~i.5
0 0 0 0 1
0 0 0 1 0
0 0 1 0 0
0 1 0 0 0
1 0 0 0 0

   NB. This is the final result but we are actually trying to
   NB. generate lookup tables for highly optimized C++ code.
   X (+./@:*.) Y
1 0 1 1 0

   NB. Break up x into 2-bit chunks.
   NB. Note: reversed with |. because #. below interprets right-most
   NB.       digit as most significant but J's array has first
   NB.       item as left-most.
   X
0 1 1 0 1
   _2<@|.\X
┌───┬───┬─┐
│1 0│0 1│1│
└───┴───┴─┘

   NB. We convert 2-bit chunks of x into indices.
   _2#.@|.\X
2 1 1

   ]L2=. _2((|."1@:#:@:i.@:(2^#)) (+./"2 @: (*."0 1"1 _)) ])\Y
0 0 0 0 0 NB. zero
0 0 0 0 1 NB. 0 { y
0 0 0 1 0 NB. 1 { y
0 0 0 1 1 NB. +./ 0 1 { y

0 0 0 0 0 NB. zero
0 0 1 0 0 NB. 2 { y
0 1 0 0 0 NB. 3 { y
0 1 1 0 0 NB. +./ 2 3 { y

0 0 0 0 0 NB. zero
1 0 0 0 0 NB. 4 { y
0 0 0 0 0
0 0 0 0 0

   NB. Compute by 2-bit lookups (same result as +./@:*. above).
   NB. We don't really care, this just demonstrates that the LUT works.
   +./ (_2#.@|.\x) {"0 2 L2
1 0 1 1 0

Cheers,

Mike

On Wed, Oct 12, 2016 at 7:00 PM, Michal Dobrogost <
michal.dobrogost at gmail.com> wrote:

> Hi Raul,
>
> What is the definition of *inds*?
>
> I would describe the higher level operation as: select the rows of Y where
> X is 1. Then take the column-wise OR of them.
>
> However the real thing I'm interested in is generating the lookup tables
> which serve as an intermediate step in the higher level operation.
>
> On Wed, Oct 12, 2016 at 9:35 AM, Raul Miller <rauldmiller at gmail.com>
> wrote:
>
>> I'm not quite sure I understand what you are doing here.
>>
>> Here's what I understand from your description:
>>
>> You're looking for rows where a bit set in X has a bit set in Y, and
>> you want to split up X and Y into smaller pieces for your intermediate
>> result, and you want to use indices rather than bit operations for
>> your final operation.
>>
>> That gives me something like this.
>>
>>    X =: ? 5 $ 2
>>    Y =: 30 > ? 5 6 $ 100
>>    X
>> 0 1 1 1 1
>>    Y
>> 0 0 0 0 0 0
>> 1 0 0 0 0 0
>> 1 1 1 0 0 1
>> 1 0 0 1 0 0
>> 0 0 0 0 0 1
>>    (_2 {. X) inds _2 {. Y
>> 0 3 5
>>    (3 {. X) inds 3 {. Y
>> 0 1 2 5
>>    0 3 5 ([ -. -.) 0 1 2 5
>> 0 5
>>
>> So maybe you would be looking at making an adverb along the lines of:
>>
>> L=: adverb define
>> :
>>    (m {. x) inds m {. y
>> )
>>
>> Or, more concisely:
>>
>> L=: adverb define
>>    inds&(m&{.)
>> )
>>
>> But when I look at your calculations, I don't see anything like this.
>>
>> If I am off base here, could you describe how what you are looking for
>> differs from what I am understanding?
>>
>> Thanks,
>>
>> --
>> Raul
>>
>>
>> On Wed, Oct 12, 2016 at 12:14 PM, Michal Dobrogost
>> <michal.dobrogost at gmail.com> wrote:
>> > Hi All,
>> >
>> > I've been mucking around generating look up tables in C++. Getting
>> > frustrated, I wrote up this J single liner. Can you think of ways to
>> > simplify the LUT computation (the expression we assign to L2 and L3
>> below)?
>> >
>> > *Original Operator (no LUT)*
>> >
>> >    ] x =. ? 5 $ 2
>> > 1 0 1 1 0
>> >    ] y =. 30 > ? 5 6 $ 100
>> > 1 0 0 0 0 0
>> > 0 1 0 1 1 0
>> > 0 1 0 0 0 1
>> > 0 0 0 0 1 1
>> > 0 1 1 1 0 1
>> >    x (+./@:*.) y
>> > 1 1 0 0 1 1
>> >
>> > *LUT Explanation*
>> >
>> > The idea is to break up x into smaller chunks (2-bits, 3-bits, etc) and
>> > precompute the operation for the corresponding chunks of y. Then we just
>> > convert the chunks into indices and look them up in the LUT.
>> >
>> >    _2<\x
>> > ┌───┬───┬─┐
>> > │1 0│1 1│0│
>> > └───┴───┴─┘
>> >    _2#.\x
>> > 2 3 0
>> >
>> > *2-bit LUT*
>> >
>> >    ]L2=. _2((#:@:i.@:(2&^)@:#) (+./"2 @: (*."0 1"1 _)) ])\y
>> > 0 0 0 0 0 0
>> > 0 1 0 1 1 0
>> > 1 0 0 0 0 0
>> > 1 1 0 1 1 0
>> >
>> > 0 0 0 0 0 0
>> > 0 0 0 0 1 1
>> > 0 1 0 0 0 1
>> > 0 1 0 0 1 1
>> >
>> > 0 0 0 0 0 0
>> > 0 1 1 1 0 1
>> > 0 0 0 0 0 0
>> > 0 0 0 0 0 0
>> >
>> >    +./ (_2#.\x) {"0 2 L2    NB. Compute by 2-bit lookups
>> > 1 1 0 0 1 1
>> >
>> > *3-Bit LUT*
>> >
>> >    ]L3=. _3((#:@:i.@:(2&^)@:#) (+./"2 @: (*."0 1"1 _)) ])\y
>> > 0 0 0 0 0 0
>> > 0 1 0 0 0 1
>> > 0 1 0 1 1 0
>> > 0 1 0 1 1 1
>> > 1 0 0 0 0 0
>> > 1 1 0 0 0 1
>> > 1 1 0 1 1 0
>> > 1 1 0 1 1 1
>> >
>> > 0 0 0 0 0 0
>> > 0 1 1 1 0 1
>> > 0 0 0 0 1 1
>> > 0 1 1 1 1 1
>> > 0 0 0 0 0 0
>> > 0 0 0 0 0 0
>> > 0 0 0 0 0 0
>> > 0 0 0 0 0 0
>> >
>> >    +./ (_3#.\x) {"0 2 L3    NB. Compute by 3-bit lookups
>> > 1 1 0 0 1 1
>> > ----------------------------------------------------------------------
>> > For information about J forums see http://www.jsoftware.com/forums.htm
>> ----------------------------------------------------------------------
>> For information about J forums see http://www.jsoftware.com/forums.htm
>
>
>