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.