# 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.

## JOMA

Journal of Online Mathematics and its Applications