1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
|
%==========================================================================
% Solutions to above sample exercises
%==========================================================================
%\advance\vsize by 3truecm
\choosett{apl}
\noindent
\header%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vskip 1cm
\noindent
As the index of the neutral element we use the index origin \BX@IO@ which
usually has the value @0@. Then $S(N)=
\{0,\dots,N-1\}$, given by the vector \IO@N@.
An example on groups are the cyclic groups $({\bf Z}_n,+)$
the group tables of which are generated by the \APL\ function @ZNPLUS@:
\hskip\parskip\vbox{\hsize=15truecm
\begintt
@DL Z_ZNPLUS N;@BXIO
[1] @BXIO_0
[2] Z_N@AB(@ION)@SO.+@ION
@DL
\endtt
}\smallskip
\item{1.} The matrices represent binary operations of $S(N)$,
since they are $N\times N$-matrices with elements from
$S(N)$. They are all associative and also commutative except for
the case (b). This can be seen by the function @TEST@:
\hskip\parskip\vbox{\hsize=15truecm
\begintt
@DL Z_TEST B
[1] " B IS A BINARY OPERATION. THE FUNCTION RETURNS A BOOLEAN 2-VECTOR
[2] " (B ASSOCIATIVE, B COMMUTATIVE)
[3] Z_(&/&/&/B[B;]=B[;B]),&/&/B=@TRB
@DL
\endtt
}\smallskip
\item{2.}
\hskip\parskip\vbox{\hsize=15truecm
\begintt
@DL P_X GPOWER N;I
[1] " G GLOBAL
[2] P_@BXIO @DM I_0
[3] TEST:@GO(N<I_I+1)/0
[4] P_G[P;X]
[5] @GOTEST
@DL
\endtt
}\smallskip
\item{3.}
\hskip\parskip\vbox{\hsize=15truecm
\begintt
@DL P_X BGPOWER N;IJ
[1] " G GLOBAL
[2] P_@BXIO
[3] NEXTJ:@GO(0=N,IJ_2@ABN)/0,SQX
[4] P_G[P;X]
[5] SQX:X_G[X;X]
[6] N_(N-IJ)%2
[7] @GONEXTJ
@DL
\endtt
}
\item{} A comment: if $i_j=0$, then the power is not increased,
but the square $x^{2^{j+1}}=(x^{2^j})^2$ is computed.
The number of iterations is $k$; $n = i_0+i_12+\cdots+i_k2^k \ge 2^k$,
when $i_k \not= 0$, and hence $k \le \log_2(n)$.
Thus, the complexity is $O(\log_2(n))$.
\smallskip
\vfill\eject
\item{4.}
\hskip\parskip\vbox{\hsize=15truecm
\begintt
@DL Z_A GTSGP G
[1] " RETURNS THE SUBGROUP OF G GENERATED BY A
[2] Z_,A
[3] TEST:@GO(&/&/G[Z;Z]@EPZ)/FOUND
[4] Z_Z UNION G[Z;Z]
[5] @GOTEST
[6] FOUND:Z_Z[@GUZ]
@DL
\endtt
}
\hskip\parskip\vbox{\hsize=15truecm
\begintt
@DL Z_A UNION B;V;@BXIO
[1] V_(,A),,B
[2] @BXIO_1
[3] Z_,CLEAN((@ROV),1)@ROV
@DL
\endtt
}
The auxiliary function @CLEAN@ was given earlier.
\bigskip
\item{5.}
\hskip\parskip\vbox{\hsize=15truecm
\begintt
@DL Z_INV G
[1] " RETURNS THE VECTOR OF INVERSE ELEMENTS OF G
[2] (@BXIO=,G)/,(@ROG)@ROG[@BXIO;]
@DL
\endtt
}\smallskip
\item{6.}
\hskip\parskip\vbox{\hsize=15truecm
\begintt
@DL H_A BGTSGP G;Y
[1] " RETURNS THE SUBGROUP OF G GENERATED BY A
[2] H_Y_@BXIO
[3] B:@GO(0=@ROY_(,G[Y;A])MINUS H)/0
[4] H_H UNION Y
[5] @GOB
@DL
\endtt
}
\hskip\parskip\vbox{\hsize=15truecm
\begintt
@DL Z_A MINUS B
[1] Z_(@NTA@EPB)/A
@DL
\endtt
}\smallskip
\item{7.} If the elements of $G_i$ have been indexed by the interval
$[0,n_i-1]$, the elements of $G_1\times G_2$ become indexed
in a natural way by the elements of the Cartesian product
$[0,n_1-1]\times[0,n_2-1]$. With the bijection
$(i,j) \mapsto in_2+j:[0,n_1-1]\times[0,n_2-1]
\longrightarrow[0,n_1n_2-1]$
(the inverse $k\mapsto((k-(k \bmod n_2))/n_2,k \bmod n_2)$
selects the quotient and remainder in the division by $n_2$)
we get $[0,n_1n_2-1]$ as the index set.
\vfill\eject
\hskip\parskip\vbox{\hsize=15truecm
\begintt
@DL G_G1 PROD G2;@BXIO;I;J;IREM;JREM;N1;N2;N
[1] N_(N1_(@ROG1)[1])#N2_(@ROG2)[1] @DM I_@BXIO_0
[2] G_(N,N)@RO0
[3] JLOOP:J_0
[4] CORE:G[I;J]_(G1[(I-IREM)%N2;(J-JREM)%N2]#N2)+G2[IREM_N2@ABI;JREM_N2@ABJ]
[5] @GO(N>J_J+1)/CORE
[6] @GO(N>I_I+1)/JLOOP
@DL
\endtt
}
Example:
\hskip\parskip\vbox{\hsize=15truecm
\begintt
(ZNPLUS 2) PROD ZNPLUS 10
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
1 2 3 4 5 6 7 8 9 0 11 12 13 14 15 16 17 18 19 10
2 3 4 5 6 7 8 9 0 1 12 13 14 15 16 17 18 19 10 11
3 4 5 6 7 8 9 0 1 2 13 14 15 16 17 18 19 10 11 12
4 5 6 7 8 9 0 1 2 3 14 15 16 17 18 19 10 11 12 13
5 6 7 8 9 0 1 2 3 4 15 16 17 18 19 10 11 12 13 14
6 7 8 9 0 1 2 3 4 5 16 17 18 19 10 11 12 13 14 15
7 8 9 0 1 2 3 4 5 6 17 18 19 10 11 12 13 14 15 16
8 9 0 1 2 3 4 5 6 7 18 19 10 11 12 13 14 15 16 17
9 0 1 2 3 4 5 6 7 8 19 10 11 12 13 14 15 16 17 18
10 11 12 13 14 15 16 17 18 19 0 1 2 3 4 5 6 7 8 9
11 12 13 14 15 16 17 18 19 10 1 2 3 4 5 6 7 8 9 0
12 13 14 15 16 17 18 19 10 11 2 3 4 5 6 7 8 9 0 1
13 14 15 16 17 18 19 10 11 12 3 4 5 6 7 8 9 0 1 2
14 15 16 17 18 19 10 11 12 13 4 5 6 7 8 9 0 1 2 3
15 16 17 18 19 10 11 12 13 14 5 6 7 8 9 0 1 2 3 4
16 17 18 19 10 11 12 13 14 15 6 7 8 9 0 1 2 3 4 5
17 18 19 10 11 12 13 14 15 16 7 8 9 0 1 2 3 4 5 6
18 19 10 11 12 13 14 15 16 17 8 9 0 1 2 3 4 5 6 7
19 10 11 12 13 14 15 16 17 18 9 0 1 2 3 4 5 6 7 8
\endtt
}
\end
|
