summaryrefslogtreecommitdiff
path: root/fonts/apl/solutions.tex
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /fonts/apl/solutions.tex
Initial commit
Diffstat (limited to 'fonts/apl/solutions.tex')
-rw-r--r--fonts/apl/solutions.tex198
1 files changed, 198 insertions, 0 deletions
diff --git a/fonts/apl/solutions.tex b/fonts/apl/solutions.tex
new file mode 100644
index 0000000000..85e3730545
--- /dev/null
+++ b/fonts/apl/solutions.tex
@@ -0,0 +1,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
+
+