From cube-lovers-errors@oolong.camellia.org Wed Jul 16 10:18:34 1997 Return-Path: cube-lovers-errors@oolong.camellia.org Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id KAA12915; Wed, 16 Jul 1997 10:18:33 -0400 Precedence: bulk Errors-To: cube-lovers-errors@oolong.camellia.org Date: Wed, 16 Jul 1997 09:44:21 -0400 (Eastern Daylight Time) From: Jerry Bryan Subject: No Local Maxima 11q from Start To: cube-lovers@ai.mit.edu Message-id: MIME-version: 1.0 Content-type: TEXT/PLAIN; charset=US-ASCII X-X-Sender: jbryan@pstcc6.pstcc.cc.tn.us My new Shamir program has now generated the entire search tree for the standard cube group G up to 11q from Start. This search was accomplished once before using my old tape spinning programs, so there is limited new information. One good result is that all the numbers match between the two programs. The matching results were obtained using different programs, implementing different algorithms, in different programming languages, on different hardware platforms, and under a different operating systems. So I feel pretty good about the numbers. They have been posted before, so I won't post them again. With problems this big, it is always good to have some sort of independent verification because it is impossible to verify anything by hand. Another interesting result is in fact new. The old program was only able to determine local maxima up to 10q from Start while calculating the 11q tree. The new program is able to determine local maxima up to the same distance from Start it is searching. There are no local maxima 11q from Start. I find this result somewhat surprising, since there are four local maxima (unique up to M-conjugacy) 10q from Start. The new program did confirm the previously known 10q local maxima, but failed to find any 11q local maxima. In its search for local maxima, for each position x the program calculates the set E(x) of quarter turns with which a minimal process for the position can end. We call |E(x)| the maximality of x, and a position is a local maximum if its maximality is 12. At a distance of 11q from Start, there exist positions with maximality values for every number in 1..11. This is the first time we have found any positions with a maximality of 9 or 11. (See my note of 16 June 1995, "10q Local Maxima Search Matrix".) There seem to be more positions with even maximality values than odd, and a maximality of 11 is especially interesting because such a position is "almost" a local maximum. I am disappointed in the speed of my program. For this run, it identified about 1100 patterns (representative elements of M-conjugacy classes) per second. This corresponds to about 50,000 positions per second (about 48 times 1100). The program is running on a Pentium P166 with 16MB memory under Windows/95. My concern is that I have worked so hard to make the program run in small amounts of memory that it is running too slow. I am now going to take out a few of the memory saving techniques to see if I can speed it up a bit. The program is actually about 20MB, and runs successfully on a 16MB machine due to the good graces of virtual memory. In fact, I can calculate out to 11q from Start even on an 8MB machine. But trying to calculate out to 12q from Start fails on the 16MB machine (the program is the same size for 11q from Start and for 12q from Start because I am storing all positions up to 6q from Start. The program would only have to be made larger if I were to try calculating 13q from Start or 14q from Start.) When I say the program fails at 12q from Start, I mean that the virtual memory thrashes unmercifully, and therein lies an interesting tale. Why should the program be able to calculate 11q without thrashing, but thrash so badly at 12q? It has to do with the Shamir algorithm itself. Recall that we are producing products of the form ST in lexicographic order. To be specific, we are producing products of the from St in lexicographic order for all t in T and merging the results. S itself is already in lexicographic order. Think of processing a dictionary, and thing of processing S in lexicographic order. We essentially process all the A's, followed by all the B's, then all the C's, etc. There is very good locality of reference as far as the virtual memory goes. Moving up to St, we might first process all the N's, then all the E's, then all the Z's, etc, but there is still very good locality of reference. There is an occasional big jump in where we are referencing memory, but most of the time we reference elements of the set S which are very close together in memory. When we calculate 11q from Start, S is the set Q[6] of positions which are 6q from Start, and T is the set Q[5]. Because Q[5] is only about 1/9 as big as Q[6], the real memory working set to calculate Q[6]Q[5] is only about 10% of the total virtual memory of the program, maybe about 2MB. But when we move up to calculating 12q, we move up to Q[6]Q[6] and the real memory working set becomes the whole 20M program. This simply doesn't work on a 16MB machine. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us Pellissippi State (423) 539-7198 10915 Hardin Valley Road (423) 694-6435 (fax) P.O. Box 22990 Knoxville, TN 37933-0990