# Re: [Jprogramming] Generating Lookup Tables (LUTs)

```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.dobrog...@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 <rauldmil...@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
>>
>> 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:
>>
>> :
>>    (m {. x) inds m {. y
>> )
>>
>> Or, more concisely:
>>
>>    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.dobrog...@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
>
>
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm```