You are here

Evolution of a Computer Application - Search

Author(s): 
John J. Wavrik

Groups32 has a mechanism to search the groups of orders 1-32 to find those with given generators satisfying given relations, or to find groups that contain subgroups with the given finite presentation.  The algorithm used is quite literal:  All group elements are substituted for the generators, and then the orders and relations are checked.  A "shortcut" evaluation is used:  Once a condition is found to be FALSE, no subsequent conditions are checked.

This is the slowest procedure in Groups32. Direct assembly language coding of G* (and 8 other words) does result in a dramatic speedup of SEARCH.

Here is how SEARCH can be used to identify the dihedral groups, which are groups with two generators, x and y, with x of order 2, but the order of y is not specified.  The defining relation is  xy = y'x, where ' indicates inverse.  The prompted input in the following example is from the command completion user interface that I describe in the next section.

Enter distinct generators as a string
e.g.  RS means two generators R and S
       Generators:  xyDo you want these to generate the entire group? (y or n) Y
Enter the exact order for each generator.
Press Enter for no order specified
     X is of order    2 Y is of order
A relation is of the form  LHS = RHS
Put in LHS RHS  or  LHS  ( if RHS is e )
       
LHS RHS >>  xy  y'xGenerators:
     XY
Orders:
     X= 2
RELATIONS:
     XY    = Y'X
-- Pressing ESC will abort the search --
2  group order =  2  X = B   Y = B
5 group order = 4 X = C Y = B
8 group order = 6 X = D Y = B
13 group order = 8 X = E Y = B
18 group order = 10 X = F Y = B
22 group order = 12 X = G Y = B
27 group order = 14 X = H Y = B
40 group order = 16 X = I Y = B
47 group order = 18 X = J Y = B
52 group order = 20 X = K Y = B
58 group order = 22 X = L Y = B
69 group order = 24 X = M Y = B
78 group order = 26 X = N Y = B
86 group order = 28 X = O Y = B
92 group order = 30 X = P Y = B
111 group order = 32 X = B Y = D

The group of quaternionic units (order 8) can be presented as a group with three generators, a, b, c, and relations ab = c, bc = a, ca = b.  The following chart shows the timing for the SEARCH command using different Forth implementations and computers.

Timing for Search

Groups32 ver 7.0 // Win32Forth high level

1308270 ms

Groups32 ver 7.0 // Win32Forth assembly language

    51300 ms

Groups32 ver 7.0 // SwiftForth

  307656 ms

Groups32 ver 6.4g // Gforth LINUX

1794000 ms

Groups32 ver 6.4g // Gforth on Internet

2700000 ms

The entry marked Win32Forth assembly language replaces just nine words by assembly language equivalents -- the increase in speed is remarkable. 

The entries for Gforth compare a LINUX version of Forth on a personal computer with the timing for the same version (running on a SUN server) accessed via Telnet on the Internet.

Notice that the fastest timing (about 1 min) is for a personal computer using assembly language coding of a few time-critical commands, and the slowest, using the Internet, is about 45 min. With the exception of the entry marked "Internet", the computer used has a Pentium III processor running at 450 Mhz.

The process of searching through a collection of groups to find those with a given set of generators and relations is inherently time-consuming. This does not preclude the possibility that a better algorithm will make a major improvement.

John J. Wavrik, "Evolution of a Computer Application - Search," Convergence (December 2004)