Sunday, May 18, 2014

Finite Groups with J

This post is mostly taken from the J Labs, Finite Groups section.

First, label four elements, a, b, c, d as 0, 1, 2, 3.

'a b c d' =: i.4
   a
0
   b
1
   c
2
   d
3
 Now, define a function, f, to be the operator of our group.

 f =: 4&|@+
 i.e. our operator is integer addition modulo 4.

(a,b,c,d) f table (a,b,c,d)
┌─┬───────┐
│f│0 1 2 3│
├─┼───────┤
│0│0 1 2 3│
│1│1 2 3 0│
│2│2 3 0 1│
│3│3 0 1 2│
└─┴───────┘
Here are some example calculations:
   1 f 1
2
   2 f 3
1
   2 f 2
0
 Clearly, we have the group Z_4.


Next, we can try to create Z_2 x Z_2 (direct product of Z_2 and Z_2, also known as V_4).

   'a b' =. i.2
   'c d' =. i.2
  
  
   f =. 2&|@+
 g =. 2&|@+"0

 (c,d)g (a, b)
0 0
   (c,c) g (a, b)
0 1
  lz =. 4 2 $ 0 0 1 0 0 1 1 1
   lz
0 0
1 0
0 1
1 1

 lz g"( 1 1) 0 1
0 1
1 1
0 0
1 0
lz g"( 1 1)/ lz
0 0
1 0
0 1
1 1

1 0
0 0
1 1
0 1

0 1
1 1
0 0
1 0

1 1
0 1
1 0
0 0

Simple Way to Remember Monadic Hooks

A simple to remember the rules of J Hooks is to use the very simple verbs:


v1 =. +!
and
v2 =. +@:!

v1 is a hook while v2 is a simple vrb train that applies ! and then + to the argument(s).

Example

arg =. 1 2 3 4

v1 arg  2 4 9 28
v1 applies ! to each element and then applies + to the result and the original argument.
i.e. 1+1! =2, 2+2!=4 etc.

If you forget how Hooks work, it may be useful to consider this simple case and then you should be able to figure out how to write your verb train correctly.

Wednesday, January 16, 2013

Composing Verbs Part 1: Monads

If we wish to compose two verbs (as shown below) we can use the conjunction @: .

For example, if we have a verb that multiplies all the arguments of a list:

PROD =: */
   PROD 2 3 4 5
120

we can  make a composition verb with the following verb (which decrements the argument):

DEC =: -1:

The composition is written thus:

  COMP =: PROD@:DEC
   COMP 1
0
   COMP 2 3 4
6
   COMP 2 0.5
_0.5
   COMP 3 1.5
1 

Here the composition verb, COMP, multiplies the decremented elements of the list. i.e.  COMP  2 3 4 will multiply 1*2*3 = 6.

Generally if f and g are two monadic verbs and y is the argument then

f@:g y = f(g y)
It should be noted that the composiiton @: is not associative. i.e.

f@:(g@:h) does not equal (f@:g)@:h for verbs f,g,h.
 Obviously g@:f usually doesn't equal f@:g. For example, using our above verbs:

  COMP2 =: DEC@:PROD 

 COMP2 1

0 

 COMP2 2 3 4

23   

COMP2 2 0.5

0   

COMP2 3 1.5

3.5   

Obviously COMP and COMP2 are completely different verbs.

Next we'll look at composition of dyadic verbs.

Monday, August 27, 2012

Rank Part I

For a multidimensional array, we can say the shape of the array is the 1D array made from concatenating the lengths of each axis. For example:


a =: i. 3 3 2
   a
 0  1
 2  3
 4  5
 6  7
 8  9
10 11
12 13
14 15
16 17

Here "a" is a 3 dimensional array with axes of length 3, 3 and 2. We can get the shape of the array by using the "$" monadic verb.
  $a3 3 2


The rank of an array is essentially the dimensionality of the array. For example, still using "a":


#$a
3

Here we used the "#" verb to get the size of the array. Of course, it is 3 dimensional.

The rank is very important as it determines how verbs act on an array.
But not only arrays (nouns) can have ranks. Verbs (operators) also have rank.

In part II we will look at verb ranks.







Sunday, August 19, 2012

Some primitives...

I will briefly go through some of the primitive verbs used in J. These are some of the inbuilt functions (both dyadic and monadic) that seem to be pretty ubiquitous in J code.

Arithmetic Dyadic Verbs
Addition: 2 + 5 6 7  
Subtraction: 4 - 6 
Multiplication: 2 * 4 6 8 
Division: 5 % 6
Exponent: 8 ^ 9
Logarithm: 8 ^. 64 ( = 2)Root: 3 %: 27 ( =3)
Greater: 5 >. 20 ( =20)
Lesser: 9 <. 21 ( =9)GCD:  3 +. 7 ( =1)LCM: 4 *. 10 ( =20)

Arithmetic Monadic Verbs 
Floor: <. 6.1   ( = 6) 
Ceiling: >. 6.1 ( =7) 
Sign: * _4 ( =_1) 
Factorial: ! 5 
Random Integer: ? 7 ( = random int from 0,...,6) 
Random Real: ? 0 ( = random real from 0 to 1)
Comparisons, producing 1 or 0, for true and false, respectively
Equality: 2 = 1 ( = 0) 
Greater than: 1 > 2  
Greater than or equal to: 1 >: 2  Note - don't confuse with dyadic >. 
Less than: 3 < 4 
Less than or equal to: 3 <: 4 Note - don't confuse with dyadic <. 
Inequality: 3 ~: 4
Boolean Operations
OR: +.NOR: +: AND: *.NAND: *:XOR: ~:XNOR: =  
Monadic: 
NOT: -. 


Some boolean examples:

   1 +. 0 (OR)
1
   1 *. 0 (AND)
0
 
   1 0 1 0 0 1 *: 1 (NAND)
0 1 0 1 1 0
Some Binary:

We can also do bit shifting. Here we will shift the number 1 by 3 bits (left rotate):

3 (32 b.)18
 Of course, the output is 8. We can also display the output as a binary value:


#: 4 (32 b.) 31 1 0 0 0 0


Here we used the verb "#:" to change from a decimal number into its binary form.
We can change it back:

#.1 1 0 0 0 0
48


Perhaps in another post I will look into using hexadecimal representations.

Take and Drop List Verbs:

 Take - here the left operand is the index and we take the elements from the list with index less than this.


       1 {. 2 3 5 7  
2    
   5 {. 3 4 6 7 7 8 9 2 1 3 
3 4 6 7 7    
   6 {. i.20 
0 1 2 3 4 5



Drop - same as take but we drop these elements from the original list.


   3 }. i.10
3 4 5 6 7 8 9
 
   6 }. 'A long time ago in a galaxy far, far away...'
 time ago in a galaxy far, far away...
 
   _10 }. 'A long time ago in a galaxy far, far away...'
A long time ago in a galaxy far, f

Well those are some of the basic operations. You can see more here: http://www.jsoftware.com/jwiki/HenryRich?action=AttachFile&do=get&target=J602_RefCard_color_letter_current.pdf







Saturday, August 18, 2012

Boxes

We have seen 1D arrays and multi-dimensional numerical arrays. But what if we want a structure to hold different types of data? For example, we can create a structure, a box, containing both numeric and charcter data.
First we will have a quick introduction to character data.

      charlist =: 'Hello world!'

This creates a D character array. We can use the indexing verbs "{" and "}" to find sublists.

      1{charlist
      e

1} asks for the element of charlist at position 1, similar to C's charlist[1].

      1 2 3{ charlist
      ell

Here we took the 1st, 2nd and 3rd elements of the char array.
We can combine two lists thus.

   charlist =: ' Hello ' , 'world!'

where "," is the verb for concatenating elements.

OK. So what if I try to concat a character list with a numerical list?

    somelist =: 'A phrase', 1 2 3
    | domain error
    |   somelist=:'A phrase'    ,1 2 3

Uh oh. Big problem. The interpreter doesn't want us to do that.
But we can make a "box" to hold both numeric and character data. Here is how:

     char =: 'some important info'
   num =: 1924 1945 1986 1998
   box =: (<char),(<num)
   
   box
┌───────────────────┬───────────────────┐
│some important info│1924 1945 1986 1998│

So the box, which is a scalar object, i.e. it has no size (check $#box), contains one element of char data and one of numerical.

We can search the box to find the data:

         >num
        1924 1945 1986 1998

finds the data corresponding to "num".
We can also go further and make tables of data. For example:


       char1 =: 'important dates'
     char2 =: 'notes'
     num1 =: 15 2
     num2 =: 17 5
     num3 =: 25 12
                        
     note1 =: 'birthday'
     note2 =: 'anniversary'
     note3 =: 'Christmas'


     datebox =: (<char1),<char2
     dates1=: (<num1),<note1
     dates2=: (<num2),<note2
     dates3=: (<num3),<note3

     ((datebox,:dates1),dates2),dates3
┌───────────────┬───────────┐
│important dates│notes      │
├───────────────┼───────────┤
│15 2           │birthday   │
├───────────────┼───────────┤
│17 5           │anniversary│
├───────────────┼───────────┤
│22 11          │Christmas  │
└───────────────┴───────────┘


Here we used the useful dyadic verb ",:", "laminate" which sticks one array on top of another.
An example:

    a1 =: 1 2 3 4
    a2 =: 2 4 6 8
    
    a1,:a2

   1 2 3 4
   2 4 6 8

What about:

    a1 =: 1 2 3 
    a2 =: 2 4 6 8
    
    a1,:a2
    1 2 3 0
    2 4 6 8

The interpreter appends a zero to the top array, as it sees there are too few elements.







Friday, August 17, 2012

Is it prime?

I will write a function (verb) to find if a given integer is prime or not. I'm sure there are much better ways to do this in J than the one I am using, but I wanted to do it for myself. In C style languages it is easy to find if an integer is prime. Just follow the following steps:

  1. Make a loop through all positive integers less than the (floor of) the square root of the given integer. i.e if we want to find if 48 is prime, then we just need to check to see if  2 3 4 5 or 6 divide it.
  2. Loop through the numbers. Use "%" to check the remainder on division. If remainder is zero, break out of the loop and declare our number not prime.
  3. If we reach the end of the loop, we know our number is prime.

In J, there isn't really looping. I had a good think how to do the primality test and the only way I found (without looking at anyone else's code) was to create two functions (verbs). One is a dyadic verb, and the other monadic.

The first verb shall be called ISDIV (meaning "is divisible"):

         ISDIV=:    dyad :'0=x|y'

I think this function is pretty clear. It checks if y divided by x leaves remainder zero. Or checks if y is divisible by x.

          2 ISDIV 4
    1

because 4 is divisible by 2. Here one equates to true, 0 to false.
Now we do the dyadic verb, which is a little more complicated:

       ISPRIME =: monad : '1=#((1+i.>.y^0.5) ISDIV y) #(1+i.(>.y^0.5))'

What's going on here? Well, we check if y ISDIV by all the values up to >.y^0.5, that is, up to the square root of y. This will give us a list of 0's and 1's, corresponding to divisible and not divisible. In teh case of zero 
     
     0 ISDIV y

outputs zero. With our list we now use the dyadic verb "#" (not to be confused with monadic "#", which is tally). This verb copies the 1's form the left operand to the list, which is the right operand. In effect it gives us only those numbers which divide y. More importantly, it gives us the length of the list of those numbers. This is what the monadic "#" at the front means. It gives us the length of the list of divisors of y. We already know that 1 is in the list. So we check to see if the length of this list equals 1, "1=#...". If it does the output is 1 (true), else output is 0 (false).
    
For example:

      ISPRIME 13
      1
      ISPRIME 70
      0
  
Well that was my first attempt at a primality test. I would have liked to have written it with only one function. But my J powers are still weak. I can also already see slight flaws. There is no need to test if 1 is a divisor of a number, so the test of this is wasted. Not a big problem, but...

The verb ISPRIME could easily be modified to not only give us the primality of y, but to output the list of proper divisors.

            DIVLIST =: monad : '((1+i.>.y%2) ISDIV y) #(1+i.>.y%2)'
     DIVLIST 6
     1 2 3 

We could go even further, and calculate sigma(y). That is, the sum of all the proper divisors.

           SIG=: monad : '+/((1+i.>.y%2) ISDIV y) #(1+i.>.y%2)'

All we did was append the +/ on the front. Wait, so now we can test if y is perfect.
           
         ISPERFECT =: monad : 'Y = SIG y'
     ISPERFECT 6
     1

     ISPERFECT 28
     1

     ISPERFECT 18
     0