You are here

Evolution of a Computer Application - Groups16 to Groups32 Transition

Author(s): 
John J. Wavrik
From this point on, the numbering of groups corresponds to the intermediate revisions of Groups16 and to Groups32. The duplicate groups have been eliminated, and the numbering for groups of orders 1-16 is changed. Eventually groups of orders 17-32 will be added.

In the transition to Groups32, I made a number of changes.  ID appears so often in the code above because we stored group elements as A, B, C, … , and we often need to use the corresponding numbers 0, 1, 2, … to access tables or arrays. We have already pointed out that the group multiplication word G* would be faster if this conversion from the letters to indices were eliminated.  I changed the group tables to store 0, 1, 2, ... for the elements, which required revising many of the existing words that use tables and arrays.  GLIMITS (which put loop limits on the stack) was renamed to For-All-Elements, and the limits are now indices rather than ASCII codes.  The words /A, /B, /C, … that put ASCII codes on the stack were changed to put 0, 1, 2, … on the stack. I changed the display word .ELE from

: .ELE  ( ele -- )  EMIT SPACE ;

to

: .ELE  ( ele -- )  ID + EMIT SPACE ;
Reminder: Code in red was in the early 1990 version, Groups16; Code in green is in the current Groups32; Blue represents code that was not in the 1990 version and did not survive to Groups32.

These changes were not as disruptive as it might seem at first.  Many of the words in the system are not aware of how the data are represented and so required no change.

A consideration in implementing a system is precisely this:  Can the programming be done in such a way that details of data representation are hidden in lower level words?  Do most of the words in the system need to know whether group elements are represented by indices or by ASCII codes?  Do most of the words in the system need to know where or how the data are stored? 

These questions have repercussions when changes are made in the system.  They also have psychological repercussions: How much is the mathematician allowed to think in terms of mathematical objects (groups, elements, etc.), and how much must he or she think in terms of computer representation. The purpose of some of the changes in this transition is to make the language and concepts more in terms of mathematical objects and procedures applied to them.  Even the small change in name from GLIMITS to For-All-Elements is significant.

I had an important change in attitude in the transition: Several procedures were originally written to produce output on the screen -- they were regarded as top-level. I found while extending the system that it would be useful to separate the generation of information from printing it. An example of this is a factoring of the Orders command (discussed previously) into a procedure to calculate the orders of elements and a procedure to print them:

: Orders  ( grp# --  )   CR >Group
       ." Group number " Gnum .
       ." of Order "     Gord .  CR
       Calc-Orders  Prt-Orders  ;

This allows other commands to use information about orders of elements. This, in turn, required the development of data structures that could be used to transmit information from one procedure to another. In the case of subgroups and sets, it involved representing data in a form that could be transmitted on the stack. In the case of element orders, it meant providing other procedures access to the locations in memory where data were stored.

The transition also was marked by the addition of other features -- most notably, a way to deal with subgroups and a permutation group package -- plus refinement of existing features.

a. First Subgroups Package

My subgroups code represents a first effort to introduce some of the further structure of group theory into the system. It is transitional code and does not represent the way that subgroups are handled in Groups32. It was, however, very useful, providing a way to test later code as it was being developed. It displays the subgroup generated by a collection of elements. In the transition period, I had not yet introduced the idea of treating a set as an object that could be put on the stack. 

In this package, a particular subgroup (the current subgroup) is treated as a counted table or array. This approach was eventually replaced by a more sophisticated one. While the code in this section does not appear in Groups32, it does mark an important stage in the transition.

  1. Overview
  2. Top Level words and Examples
  3. Details

a.i. Overview

The main purpose of this code is to find a way to exhibit the subgroup generated by a collection of elements.  The subgroup being generated is represented by a counted array or table of bytes.  This is a list of the elements found (so far) to be in the subgroup.  The first byte is the count, and the remaining bytes are subgroup elements.

The most important top level words in the package are SGfirst ( ele -- ) and SGnext ( ele -- ), which are used to enter the first and subsequent elements.  The main words used in implementation are  >SGtable ( ele -- ) and SGsweep.  >SGtable adds a new element to the table (subgroup) if it is not already there. SGWEEP repeatedly computes products of pairs of elements currently in the subgroup, and uses >SGtable to add the products to the subgroup.  This continues until no new elements are added.

a.ii. Top Level Words and Examples

 

Top Level Words

: SGfirst ( ele -- ) 
     SG-init >SGtable 
     SGsweep SG. ;

Use this for first element to initialize the table

: SGnext ( ele -- )
     >SGtable SGsweep SG.  ;

Use this for remaining elements

When I first introduced these words, I was using the conventions of the 1990 version. In the 1990 system, they had a slightly different form, using GETE to get the input element from the input stream -- so one would use "SGfirst B" to start a subgroup with element B. The examples below were produced using the current version of Groups32. It is necessary to add the constants.

0 CONSTANT /A     1 CONSTANT /B
  2 CONSTANT /C     3 CONSTANT /D
  4 CONSTANT /E     5 CONSTANT /F
  6 CONSTANT /G     7 CONSTANT /H
  8 CONSTANT /I     9 CONSTANT /J
 10 CONSTANT /K    11 CONSTANT /L
 12 CONSTANT /M    13 CONSTANT /N
 14 CONSTANT /O    15 CONSTANT /P
 16 CONSTANT /Q    17 CONSTANT /R
 18 CONSTANT /S    19 CONSTANT /T

The input is in the form  "/B SGfirst".  This output also assumes the new numbering of groups.

32 >GROUP
/B SGfirst B C D A
/E SGnext B C D A E F G H
/I SGnext B C D A E F G H I J K L M N O P

The subgroup generated by B, E, and I is the whole group.  

a.iii. Details

We are storing the elements of a subgroup in SGtable.  The first byte of SGtable is the number of elements already in the table. The others are the stored subgroup elements (the data) in whatever order they have been generated. Let us say we have already found that elements B, F, and E are in the subgroup and have been found in that order. The SGtable will look like this:

The word SGtable puts the address of the table on the stack (marked addr).  The standard Forth word COUNT takes the address of a counted structure and returns the pair address_of_data and count.  Thus COUNT would return the pair addr1 3  in this case. The sequence COUNT + will take addr and return addr_end (the next available position at the end of the table).

We would like to add a new element to the table if it is not already there. We use a clever (but well known) trick to do this.  The strategy is to put the new element in the position at the end of the table and then scan to see if it is found.  It will be found, of course.

I am torn, in this section, between clarity and authenticity.  I have decided to present code in the form in which it appears in some of the transitional versions of the system. I have, however, presented the code with component sections separated by blank lines. For clarity, >SGtable should have been factored.  The structure is

: >SGtable ( ele -- )
  \ add ele to table if new
     DUP 
     Put_at_end
     Find_position ( pos )
     Found_at_end? ( t/f ) 
     IF Update-count THEN ;

There are obvious inefficiencies in the code:  SGsweep, for example, recomputes products that have already been computed.  It really should take only products with any newly added elements.  Remember, however, this code is intended to display a subgroup as elements are added from the keyboard -- so its speed is really limited by the input and output.

Auxiliary Words

CREATE SGtable 40 ALLOT
 
: SG.  SGtable COUNT 0 
 ?DO DUP C@ .ELE 1+ LOOP
 DROP CR ;

Print the subgroup

: SG@  ( k - ele[k] )
 SGtable 1+ + C@  ;

Return the k-th element, k = 0, 1, 2, ... .

:  SG-init  SGtable 40 ERASE  ;
 
:  >SGtable  ( ele -- )
 DUP  SGtable COUNT +   C!
             
 SGtable COUNT + 1+  
 SGtable 1+ 
 DO ( ele )
 I C@ OVER =  
 IF  DROP I LEAVE THEN  
 LOOP
             
 SGtable COUNT + =
 IF  SGtable C@ 1+ 
 SGtable C!  THEN  ;


Put the element at the end of the table.



Loop over data addresses.
Check if stored element is ele.
If so, put address where found on stack.

Check if found at end of table (where we stored it) -- if so, increment count of table.

: SGord ( -- sgord)
 SGtable C@  ;
 
: SG*  ( k1 k2 - prod )
 SG@ SWAP SG@ SWAP G* ;
 
: SGsweep  
 SGord 0= 
 ABORT"  Table is Empty "
 BEGIN  SGord
 SGord 0  DO  SGord 0 DO
 J I SG*  >SGtable
 LOOP LOOP
 SGord =  UNTIL  ;

Take products of existing elements in SGtable and add to table. Repeat this until no new elements are added.

Top Level Words

: SGfirst ( ele -- ) 
 SG-init >SGtable 
 SGsweep SG. ;

Use this for first element to initialize the table.

: SGnext ( ele -- )
 >SGtable SGsweep SG.  ;

Use this for remaining elements.

b. Sets

In previous sections the top level words have printed information to the screen. The information they produced was not intended to be used by further words.  In this section we introduce a representation for sets (subsets of group elements) as objects that can be transmitted to other words on the stack.

  1. Overview
  2. Top Level Words and Examples
  3. Details

b.i. Overview

In October, 1991 I wrote a new version of Groups16, using a newer and more extensive 16-bit version of Forth (FPC). This rewrite included some of the changes above.  The most notable new idea, however, was to introduce tools for representing and manipulating sets. Some of the commands could be written to produce a set as a result, rather than print a list of elements. Sets could be transmitted on the stack from one procedure to another.

Sets are represented by "bit maps": stack elements (the same as integers) in which a bit is set when an element is in the subset. For example, the set {B, D} contains elements 1 and 3 (A is element 0) and so is represented by 10, which is 1010 in binary.  This allows the representation of subsets of {A, B, …. ,P}. Procedures are provided for input and output, as well as standard set manipulations, test of set membership, etc.

b.ii. Top Level Words and Examples

 

#Set
(  set -- #ele) Returns number of elements in set.
2^n
(  n -- 2^n ) Raise 2 to the input power. (See Singleton.)
Contains
(  set1 set2 -- f ) Returns true if set1 contains set2.
Empty-Set
( -- 0 ) Returns the empty set.
Member!
(  ele set -- set' ) Make ele a member of set.
Member?
(  ele set -- f ) Returns true if ele is a member of set.
Set-
(  sub1 sub2 -- sub1-sub2 ) Returns difference of sets.
Set&
(  sub1 sub2 -- intersection ) Returns intersection of sets.
Set*
(  set1 set2 -- product ) Returns the set of products of elements in set1 set2 in given group.
Set.
( set -- ) Prints set (given as integer bitmap) using letters for elements.
Set+
(  sub1 sub2 -- union ) Returns union of sets.
Set-G
( -- gset ) Returns underlying set of current group.
Singleton
( n -- {n} ) Returns set with ele as only member.
SubGrp.
(  subg -- ;;;  print subg ) Prints subgroup (bitmap as set) using letters. This is the same as Set.

Examples 

{ ABC} { BC} Contains . -1 (true)
{ ABC} { BD} Contains . 0  (false)
/B { ABC} Member? . -1
/D { ABC} Member? . 0
/D { ABC} Member! 
Set. { A B C D }
/B Singleton Set. { B }
{ ABC} { BCD} Set- Set. { A }
{ ABC} { BCD} Set+ Set. { A B C D }
{ ABC} { BCD} Set& Set. { B C }
{ ABCD} #Set . 4
8 TABLE

 
 _A_B_C_D_E_F_
A |A B C D E F
B |B C A F D E
C |C A B E F D
D |D E F A B C
E |E F D C A B
F |F D E B C A
Group number 8 of Order 6
    1 elements of order  1:   A
    3 elements of order  2:   D E F
    2 elements of order  3:   B C
    0 elements of order  6:
{ B} Generates Set. { A B C }
{ BD} Generates Set. { A B C D E F }
Center Set. { A }
/B Centralizer Set. { A B C }
{ B} Generates Normalizer Set. { A B C D E F }
{ D} Generates Normalizer Set. { A D }  
  

b.iii. Details

	
: 2^N ( n - 2^n )   \ integer with bit n set
       1 SWAP 0 ?DO 2* LOOP ;
: Singleton ( n - set )  2^N  ;
: Contains  ( set1 set2 - t/f ) \ TRUE if set1 contains set2 
          SWAP OVER AND = ;
: Member?  ( ele subg - t/f )  
          SWAP Singleton Contains ;
: Member!  ( ele subg -- subg' )  
          SWAP Singleton OR ;

Notice the use of "bitwise" operations AND and OR. 5 2 OR gives 7 while 5 2 AND gives 0.

5  ( 1 0 1 )

2  ( 0 1 0 )

Here is a word for printing a set:

	
: SubGrp.  ( subg -- ) \  print subg   
     ." { "  1  ( bit mask )
     16 0  DO  2DUP AND   \ check if bit is set
               IF  I .ELE  THEN
               2*         \ left shift mask
           LOOP   2DROP ." } " ;

Notice that the idea of representing sets (and subgroups) as arrays has been abandoned in favor of using a representation as integers. The word SubGrp. here is defined to print a subgroup represented as an integer -- it supercedes the early version of SG. in which a set is represented as an array -- but it has the same function.

	
: Set.  SubGrp. ;

Here is a word for inputting a set. The definition uses some features of Forth compilation to make it "state smart" (i.e., it acts differently if the system is compiling). Notice that, when interpreting, this word produces an integer, which is put on the stack. When the system is compiling, it stores the integer in the definition. This definition is not included in Groups32, since the command completion interface used there prompts for input of sets. The details of this definition are beyond the scope of this article.

: {   ( -- set ;;; interpret string up to } as a set      )
      0                              \ start with empty set
      ASCII }  WORD                  \ get string up to }
      COUNT 2DUP UPPER               \ convert to upper case
      0 DO  DUP C@ ID -   DUP 0 15 BETWEEN  \ check if valid
          IF    ROT Member! SWAP     \ set addr
          ELSE  DROP        THEN  1+ \ next address
        LOOP  DROP
      STATE @  IF  [COMPILE] LITERAL  THEN  ; IMMEDIATE

Some basic set operations:

: Set-  ( set1 set2 -- set1-set2 ) 
    \ set difference
        OVER AND XOR  ;
: Set+  ( set1 set2 -- union )  
     \ set union
        OR  ;
: Set&  ( set1 set2 -- intersection ) 
     \ set intersection
        AND  ;
: #Set  ( set -- #ele )  
           0 SWAP 
      BEGIN  ( cnt n ) DUP  
      WHILE  0 2    ( cnt lsb msb 2 )
             UM/MOD ( cnt r n/2 )
             >R + R>  \ update cnt
      REPEAT DROP ;

In #Set we shift bits to the right by dividing by 2. The Forth word

       UM/MOD ( ud un - ur uq )

takes a double precision unsigned integer and divides by a single precision integer. It produces an unsigned remainder and unsigned quotient. In each step in the loop we are dividing by 2, the remainder (0 or 1) is added to the count, and the quotient is used in the next step.

A double precision integer is represented by two stack elements; the top of the stack is the most significant part.

An important operation on subsets of a group is to form Here is the high-level Forth version:

VARIABLE Stemp
: Stemp!  ( ele -- )  Stemp @  Member!  Stemp ! ;
:  Set*  ( set1 set2 --  set1*set2 )   0 Stemp !
      For-All-Elements DO   OVER I SWAP Member?
           IF  ( first ele is member of set1 )
                For-All-Elements DO  I OVER Member?
                IF ( second ele is member of set2 )
                    J I G*  Stemp!
                THEN    LOOP
            THEN  LOOP  2DROP Stemp @  ;

 

c. Sets and Subgroups

We are now in a position to write a word “Generates” that finds the subgroup generated by a given set. Notice that the idea here is the same as used previously in SGsweep: We repeatedly take all products of elements in a subgroup under construction until we get something closed under products. In this case we take only products using new elements. The subgroup is represented as a set, so adding new elements uses the set operations we have just defined. We use the following notation in the comments for Generates:

S is the originally given set of generators.
X is the total set of products formed so far.
Y is the set of products yet to be multiplied by S.

: Generates  ( set -- subg )  >R
     1 1                        (  X = Y = {id} )
     BEGIN    R@ Set*           (  X Y*S )
              OVER Set-         (  X Y'      Y'=Y*S-X new prods )   
              SWAP OVER Set+    (  Y' X'     X'=X+new           )
              SWAP ?DUP         (  leave if no new products     )
  0= UNTIL
     R>  DROP ;

Since Set-G, the underlying set of G, occurs in subgroup operations, we have >Group calculate and save it when a new group is installed.

: LCoset  ( ele subg -- lcos )  SWAP Singleton SWAP Set* ;
: RCoset  ( ele subg -- rcos )  SWAP Singleton Set*  ;
: Centralizer  ( ele -- centrz )  1  
     For-All-Elements
       DO  OVER  I OVER G*   SWAP I G* =
           IF  I SWAP Member!  THEN
       LOOP  SWAP DROP  ;
: Center  ( -- center )   1  
    For-All-Elements
     DO  I Centralizer  Set-G =
         IF  I SWAP Member!  THEN  LOOP ;
: Normalizer ( subg -- normal )  1  
    For-All-Elements
    DO  OVER I OVER LCoset  I ROT RCoset =
        IF I SWAP Member!  THEN  LOOP  SWAP DROP ;
: Normal?  ( subg - t/f )
        Normalizer Set-G = ;

 

d. Listing Subgroups

We wish to make a list of all distinct subgroups and also maintain a list of the corresponding generators. Thus the ordered list will be indices into a table of subgroups and generators. SUBGTABLE is a record structure that holds subgroups and generators for them.  The comparison function SGCOMP was chosen so that subgroups get listed in increasing size. After generating all subgroups, one can access them as an array SUBGROUP with indices 0..#SUBGROUPS-1.

Ordered Lists Package

We make use of a package for handing ordered lists that was written in 1989. Rather than exhibit the code for this package, we describe the words used here.

Note:  The implementation of ORDLIST used here uses single bytes for indices and therefore can contain at most 256 indices.

 

ORDLIST
ORDLIST This is a defining word. is the maximum number of elements in the list. is the name of a comparison function with the stack diagram
( i j -- -1 | 0 | 1 )
>LST
( list -- ) Install list as the current list
ISIN?
( n list - i  t/f ) Check if the element of index n is in the list. If it is, i is the position, and the flag is TRUE. If it is not on the list, then i is the place where it should be inserted.
(INS)
( n i --) Insert n at position i
LST@
( i - n ) n is the entry at position i in the current list.
OL-EMPTY
( list -- ) Empty the given list.

An ORDLIST is paired with an array-like structure that holds the actual data. The ordered list is a list of indices of data. When we create an ordered list, we supply a comparison function.

Suppose i and j are two indices and L[i], L[j] the corresponding data. The comparison function has stack diagram

( i j --  -1 | 0 | 1 ).

-1 if L[i] < L[j],  0 if L[i] = L[j], and 1 if L[i] > L[j].

One of the uses of ordered lists in this system is to keep a list without duplicates.

In the following code, we establish an array SUBGTABLE that holds subgroups and generators. The comparison function SGCOMP compares subgroups.  S1 < S2 if S1 has fewer elements than S2 or, if they have the same number of elements, S1 comes before S2 as unsigned integers.  SUBGLIST is the name for the ordered list. When this name is used, an address is put on the stack. >LST uses this address to make SUBGLIST the current ordered list and all the ordered list words refer to it.

CREATE  SUBTABLE  100 2* CELLS  ALLOT (Note 9)
: 'SUBG  ( index -- addr_of_subg )  
       2 CELLS * SUBTABLE + ;
: 'GEN ( index -- addr_of_gen )  'SUBG CELL + ;
: SGCOMP  ( idx1 idx2 --  -1|0|1 )  
      'SUBG @ SWAP 'SUBG @ SWAP
      OVER #SET  OVER #SET -  ?DUP 0=
      IF     2DUP U<  IF 2DROP 1   ELSE U> THEN
      ELSE   >R 2DROP R>  0> IF -1 ELSE 1  THEN
      THEN ;
100 ORDLIST SUBGLIST SGCOMP
VARIABLE SGPTR
: >SGTABLE  ( genset --  )  \ put at end
       DUP 1 SGPTR +! SGPTR @ 'GEN !
       GENERATES  SGPTR @ 'SUBG ! ;
: NEWSUB ( ele subgidx  --  )
NEWSUB takes an element and the index of a subgroup in SUBTABLE.  It will produce a new subgroup if the element is not in the existing one.
2DUP 'SUBG @ MEMBER?
 
IF 2DROP
if ele is in the subgroup, then drop both
ELSE 'GEN @  MEMBER!
Else add the element to generating set. This returns a new generating set with the element added.
>SGTABLE
>SGTABLE takes a generating set and puts it and the subgroup it generates at the end of SUBTABLE.
SGPTR @ SUBGLIST ISIN?           
We now check the ordered list SUBGLIST to see if this subgroup has previously appeared.
IF  DROP  -1 SGPTR +!
If it is already there, we DROP the position (produced by ISIN?) and decrease the SGPTR - in effect, removing the subgroup from the end of the table.
ELSE  SGPTR @ SWAP

              (INS)    THEN
If it is new, we insert the index in the proper place in the ordered list SUBGLIST.
THEN  ;
 

GENERATE-SUBGROUPS repeatedly tries to add generators to existing subgroups. Notice that the inner loop is over all elements, while the outer loop is over only the indices of SUBTABLE corresponding to subgroups added in the previous pass. (Any subgroups prior to that already have been processed.) 

: GENERATE-SUBGROUPS   ( grp# -- ) 
      >GROUP  SUBGLIST OL-EMPTY
      SUBGLIST >LST  0 SGPTR !
      1 0 'SUBG !   0 0 'GEN !   0 0 (INS)
     -1                    
     BEGIN  ( old_top )      \ previous top of SUBTABLE
          1+ SGPTR @ DUP >R  \ save current SGPTR value
          1+ SWAP            \ use only recently added subgroups
          DO   \ loop over subgroups 
               FOR-ALL-ELEMENTS
               DO  \ loop over elements
                  I J LST@ NEWSUB  LOOP
          LOOP  
          R> SGPTR @ OVER =   \ compare old SGPTR with current
     UNTIL   ( exit when no more subgroups have been added )
     DROP  ;

Once the subgroups have been generated, we display them in increasing order, first ordered by size then by lexicographic order of elements.

: SHOW-SUBGROUPS  
    SUBGLIST >LST  
    CR ."    * = Normal subgroup"
    CR ."    Generators"  25 TAB  ." Subgroup"
    SGPTR @ 1+ 0
    DO CR  I 3 .R  2 SPACES  I LST@ DUP
      'GEN @ SET.  25 TAB  'SUBG @
      DUP NORMAL? IF 42 ELSE BL THEN EMIT  SG.
    LOOP  CR ;

After GENERATE-SUBGROUPS, the subgroups are in an array. 'SUBG  gives the address of the subgroup in position k, 0 < k < N (where N is the number of subgroups). The index of the k-th subgroup in the ordered list is LST@ .

: #SUBGROUPS  SGPTR @  1+  ;
: SUBGROUP  ( indx -- subg or empty )
        SUBGLIST >LST  DUP 0 #SUBGROUPS WITHIN
        IF   LST@  'SUBG  @
        ELSE  DROP 0 THEN  ;
: SUBGROUPS ( grp# -- )  GENERATE-SUBGROUPS
                 SHOW-SUBGROUPS  ;

Example:

8  SUBGROUPS

* = Normal subgroup
Generators Subgroup
0 { } *{ A }
1 { D } { A D }
2 { E } { A E }
3 { F } { A F }
4 { B } *{ A B C }
5 { B D } *{ A B C D E F }

e. Some Simple Programs

Notice that we are developing a group theory language that can be used when we do further programming. Here are some examples of new words created using this language:

: Abelian?  ( -- t/f )  
    \ is current group abelian?
           CENTER SET-G =  ;
: IsAnOrder? ( n - t/f ) 
     \ is n the order of some element?
     \ Assume CALC-ORDERS has been run
     FALSE   ( n flag )
     MaxOrd 0 DO  OVER I 'ORD @ =
                  IF DROP TRUE THEN
              LOOP  SWAP DROP ;
: Cyclic?  ( grp# -- t/f )
       >GROUP CALC-ORDERS
       GORD IsAnOrder?  ;

When put in a loop over all groups, Cyclic? allows us to identify the cyclic groups. Here are some variants on the IsAnOrder? command:

: OfOrder ( n - ele t | f ) 
    \ find element of order n
     FALSE   ( n flag )
     For-All-Elements
     DO  OVER I EleOrder =
         IF 2DROP I TRUE LEAVE THEN
     LOOP
     DUP 0= IF SWAP DROP THEN ;
0 CONSTANT Empty-Set
: OrderN  ( n -- set )
    \ set of all elements of order n
       Empty-Set  ( n set )
       For-All-Elements  DO
           OVER I EleOrder =
           IF  I SWAP Member! THEN
       LOOP  SWAP DROP ;

The following is an incorrect attempt to identify the dihedral groups. It looks for groups of order n that contain an element of order 2 and an element of order n/2 and that are non-abelian:

: Oops-Dihedral?  ( grp# -- t/f )
   >GROUP  CALC-ORDERS
   Abelian?  NOT
   2 IsAnOrder? AND
   GORD 2 / IsAnOrder?  AND  ;

A dihedral group certainly satisfies these conditions, but some groups satisfy these conditions without being dihedral.
Here, for example, are the two non-abelian groups of order 8. One of them actually is the dihedral group, and the other is the group of quaternionic units. It should be easy to spot group 13 as the dihedral group - it has lots of reflections (elements of order 2) and only two rotations (elements of order 4). However both groups are non-abelian and have elements of order 2 and n/2.

Group number 13 of Order 8
    1 elements of order  1:   A
    5 elements of order  2:   C E F G H
    2 elements of order  4:   B D
    0 elements of order  8:
Group number 14 of Order 8
    1 elements of order  1:   A
    1 elements of order  2:   C
    6 elements of order  4:   B D E F G H
    0 elements of order  8:

An easy way to locate the dihedral groups in the current Groups32 system is to use the SEARCH command -- a dihedral group has two generators x and y, x is of order 2, the order of y can be left unspecified, and the relation is xy = y'x where ' denotes inverse. It is an interesting exercise at this point to try to write a word DIHEDRAL? with the stack diagram ( grp# -- t/f ) that determines if the given group is dihedral. Here is a solution:

: Dihedral?  ( grp# -- t/f )
   >GROUP  FALSE
   For-All-Elements DO 
     For-All-Elements DO
        I EleOrder 2 =
        J EleOrder Gord 2/ =  AND
        J I G* J G*   I =     AND
        IF DROP TRUE THEN
     LOOP LOOP ;

I will use this as an example to explore some issues in the performance of code. It is obvious that this code is not efficient in several ways:

  1. It runs through all pairs of elements of the group -- it should exit the double loop if it finds a pair that satisfies the conditions. 
  2. If the first element, I, is not of order 2, it nevertheless chooses all possible second elements, J. 
  3. There are three conditions to be tested, and they are tested in sequence -- but all three are evaluated (and combined using AND), even if the first is false.

The code, however, is direct, simple, and easily written. It has actually been optimized for clarity rather than for execution speed.
Be aware of the modern perversion that everything must run as fast as possible. Your time is valuable! This is a word that will identify, interactively, only one group for each even order -- and it will do so in less than one second. It is simply not worth the programming time required to make this particular word run faster. It may, nevertheless, be instructive to use this as an example for examining ways to increase speed.
We introduce a way to test the conjunction of conditions that stops testing when one is found to be false. Here is a way to synthesize this behavior from existing control structures.
We want to create words ?IF and ?THEN so that ?IF cccc ?THEN behaves as follows. We assume a flag on the stack. If this flag is TRUE, it is removed from the stack and cccc is executed (leaving behind a new flag). If this flag is FALSE, then cccc is not executed, and the FALSE flag is left on the stack. This is logically equivalent to the sequence IF cccc ELSE FALSE THEN.

: ?IF    POSTPONE IF  ;  IMMEDIATE  (Note 10)
: ?THEN  POSTPONE ELSE 
         POSTPONE FALSE
         POSTPONE THEN ; IMMEDIATE
: Dihedral?  ( grp# -- t/f )
      >GROUP  FALSE
   For-All-Elements DO 
     For-All-Elements DO
       I EleOrder 2 =
       ?IF  J EleOrder Gord 2/ =  ?THEN
       ?IF  J I G* J G*   I =     ?THEN
       IF DROP TRUE THEN
     LOOP LOOP ;

This version of Dihedral? will now execute a condition only if the previous conditions have evaluated to TRUE. With this change it takes only 234 milliseconds to find the dihedral groups of order up to 32 rather than 411 milliseconds.
We have previously used the word LEAVE to exit prematurely from a DO .. LOOP construct. LEAVE, however, exits only from the current loop. Forth provides a word EXIT that exits from the current procedure and a word UNLOOP that discards the current loop parameters. Thus

: Dihedral?  ( grp# -- t/f )
      >GROUP  FALSE
    For-All-Elements DO 
      For-All-Elements DO
          I EleOrder 2 =
        ?IF  J EleOrder Gord 2/ =  ?THEN
        ?IF  J I G* J G*   I =     ?THEN
        IF DROP TRUE
           UNLOOP UNLOOP EXIT (Note 11)
        THEN
     LOOP LOOP ;

Since we have gone this far, here is a version of Dihedral? that takes care of all three of the objections:

: Dihedral?  ( grp# -- t/f )
      >GROUP  FALSE
      For-All-Elements DO
          I EleOrder 2 =
          IF  For-All-Elements DO
              I EleOrder Gord 2/ =
              ?IF  I J G* I G*
                   J = ?THEN
              IF DROP TRUE
                 UNLOOP UNLOOP EXIT
              THEN
              LOOP
          THEN
       LOOP  ;

I suspect that this can be written and understood only by someone who first writes one of the simpler versions. It finds all the dihedral groups up to order 32 in 213 milliseconds.
Now, if one frequently needs to determine whether a group is dihedral, there is a rather interesting further possibility: Generate results by a method that might be slow -- and then use the stored results rather than re-calculating.

CREATE DIHEDS  MaxTables ALLOT 
      \ number of groups
: 'DIHED  ( grp# -- addr )
        DIHEDS + ;
: Old-Dihedral?  Dihedral? ;
: Dihedral?  ( grp# -- t/f )
        'DIHED C@ ;
: Calc-Dihedral
         DIHEDS MaxTables ERASE
         For-All-Groups DO
             I Old-Dihedral? I 'DIHED C!
         Loop ;
Calc-Dihedral

Now the time for executing Dihedral? is reduced to .03 milliseconds, not counting the time it takes to create the table. The moral of the story is that one should first optimize for clarity and go further only if it is necessary. The Forth language does support a variety of ways to make things faster and also perhaps clearer, ranging from the ability to introduce new control constructs to the ability to store previously computed information.

f. Groups32

At this point, if you are using Windows, you should run the Groups32 program in a separate window. This will make it possible to see how the program works and to try examples.  Examples can be copied and pasted from the article or a text editor to Groups32. If you want to do more extended programming, Win32Forth uses plain text files that can be created by an external editor and loaded into Groups32 by using INCLUDE .  When Groups32 starts, it is in the commands completion interface (to be described later). To do programming, one must QUIT this interface.

A useful Forth word is "see".  SEE , where is a word in the dictionary, will decompile the dictionary entry for the word, allowing you to see the definition of the word.

 

JOMA

Journal of Online Mathematics and its Applications

Dummy View - NOT TO BE DELETED