Home »

Even and odd cube positions

Submitted by tscheunemann on Tue, 07/06/2010 - 12:00.
After calculating 14f* and 15f* being at bit out of range, I started calculations in the quarter turn metric and just for the heck of it I switched to edge cube positions as cosets. I am in the process of verifying 15q*, which will take about 24 hours on a total of 120 cores. In the process I noticed something strange in my output. For coset 0 I get: 
0 11 1 0 0
0 12 1 121477 121477
0 13 1 0 0
0 14 1 2981152 2981152
0 15 1 0 0
so I only have positions for coset 0 at even depths (12 and 14) and none at odd depths (11, 13 and 15). I get the same for coset 1: 
1 11 12 4284 51408
1 12 12 0 0
1 13 12 165274 1983288
1 14 12 0 0
1 15 12 7548786 90585432
but now this coset only contributes to odd depths. The same holds true for all 400000 of 5022205 cosets I have already calculated. This seems hardly to be a coincidence. So it looks like that you can classify cube positions as even or odd in the sense that you need an even or odd number of quarter turns to solve it. And more important you only have to look at the edge cube positions to find out which type it is. For me at least it has the effect that going to 16q* I can completely skip half of the cosets, because I already know that they give no contribution. Has no one ever noticed this? Or, which is more likely, have I just never read about it? Are there other classifications like this?
» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

similar experience

Submitted by brac37 on Sat, 10/16/2010 - 14:01.
I have a similar experience. I implemented the square group corner coordinate, and it appears that all 96 positions satisfy a multiple of four antisymmetries (half of which are symmetries). Hence it is a very crap coordinate for symmetry reduction.
» login or register to post comments

Odd/Even in the Quarter Turn Metric

Submitted by Jerry Bryan on Tue, 07/06/2010 - 14:25.
Yes, this is well known.

Permutations are classified as even or odd depending on whether their decompositions into 2-cycles contain an even or odd number of 2-cycles. Such a decomposition into 2-cycles is not unique. But there is a theorem that states that either all such decompositions contain an even number of 2-cycles or else all such decompositions contain an odd number of 2-cycles.

Quarter turns are odd permutations, so odd permutations must be an odd distance from Start and even permutations must be an even distance from Start in the quarter turn metric. This result obviously doesn't hold in the face turn metric.

The set of even permutations of a group is a subgroup. Typically, for a group G its subgroup of even permutations is called A (i.e., the Alternating group). If G consists entirely of even permutations, then G and A are identical. Otherwise, A is a subgroup of index 2 and there are exactly the same number of even permutations as odd permutations in G. So the number of cube positions that are an even number of moves from Start will be the same as the number of cube positions that are an odd number of moves from Start in the quarter turn metric.

Also, quarter turns are odd in the corners group and also in the edges group. So odd corner positions can only occur with odd edge positions and the same for even positions. Suppose Ge is the edges group and that Ae is the even edges subgroup. Then, the coset associated with a particular corner position xc may be described as xc*Ae if xc is even, and as xc*(yeAe) for some fixed odd ye if xc is odd.
» login or register to post comments

I suspected as much

Submitted by tscheunemann on Wed, 07/07/2010 - 04:16.
So it was just me being surprised. And my "hope" that there may be other such classes, giving more than just the last bit of the number of turns, is probably pointless.

Well, on the other hand my new code is quite a bit faster than expected. I got rid of symmetry analysis all together. I still use symmetry and only calculate 5022205 cosets instead of 479 million, but I skip the symmetry reduction beyond that. On the plus side it makes the code a lot simpler, while only increasing the size of tabulated positions by about 1%. On the "minus" side I only get the totals right. I still get symmetry reduced numbers, but these are only symmetry reduced in whatever cosets I decide to use. It increases the number of positions I have to store for symmetric cosets, but on the other hand it makes cosets more equal and evens out calculation time between cores.

My 15q* calculation took only about 15 hours (with only 20 minutes differences between cores) on 120 1.9GHz Opteron cores. The results are: 

 d   positions
-- ---------------
11     62549615248
12    583570100997
13   5442351625028
14  50729620202582
15 472495678811004
verifying the earlier results (at least the totals) by Tom and others.

Now I have to assess how feasible 16q* is. I use more cosets than Tom so I had no memory problems at all for 15q*. My hope to get a two times speedup because I only have to look at half the cosets is probably wrong. I mean I can skip half the cosets, but since they give no contribution they would have been the fast ones. It still saves a lot of CPU Time but nowhere near 50%. On the other hand it doubles the number of positions I have to store for the remaining cosets.

At depth 14 the smallest coset has 65597 and the largest has 2981152 different positions. At depth 15 the smallest has 839930 and the largest has 13034920 different positions (neglecting of course all the cosets with 0 positions). Even if I expect a ten times increase, the largest coset would have 130 million positions and times 4 Bytes would easily fit in 1GB of memory. The numbers suggest only a five times increase, so 16q* looks easy and even 17q* should not be to difficult.

» login or register to post comments

Opteron cores

Submitted by rokicki on Sun, 07/11/2010 - 16:39.
When you say 120 Opteron cores, are you willing to share
more information on what CPU and motherboard? Is it a
collection of single-socket quads, or is it two-socket
boards with quads, or what CPU? Have you measured the
scalability as the core count increases? Are you
multithreading each coset, or are you just assigning each
core a separate coset?

I'd be interested in seeing the code; I'm sure I can learn
some cool tricks from your code. But of course I understand
if you do not wish to share.
» login or register to post comments

Cray XT6m

Submitted by tscheunemann on Mon, 07/12/2010 - 05:12.
The machine I am currently using is Cray XT6m Supercomputer. It is a kind of its own breed, but at the very heart it is more or less a cluster of PC-type hardware. Each compute node has two twelve core Opteron Processors (which are two six core dies in a CPU case) and a total of 32GB DDR3 SDRAM. Besides the Cray developed Seastar Network these compute nodes lack all other periphery.

For the time being I am just assigning each core a separate coset, which is the easiest and fastest way if each problem can be solved independently on a single core. Since I actually don't multithread, scalability is nearly a non issue. On the other hand I am told that scalability of the machine itself is very good, like Jaguar the No. 1 Top 500 Computer is essentially the same machine just a "few" more racks and a bit older processors.

About sharing the code, I have no problem with that. The code is in C++, the biggest part is a C++ class definition of the cube, which I wrote and spent a little time optimizing for speed. The actual code is surprisingly small. If you don't mind that my comments are mostly in german, I can email it to you right away.
» login or register to post comments

Code

Submitted by rokicki on Mon, 07/12/2010 - 22:40.
I'd be delighted to get it!

I'm currently documenting a lot of my code, and will be releasing it all soon.
» login or register to post comments