~~~ From:

~~~ Subject:

On Sun, 2 Jun 1996 hoey@aic.nrl.navy.mil wrote:

Jerry writes of the standard S24 x S24 model, which uses 48 bytes per

position without packing. He also has a "supplement" representation

that uses one facelet from each edge and corner, for 20 bytes. He

packs them into 13 bytes on tape.The way I did it the last time I worked on brute force was to

pack eight twelve-bit fields:

The way I count it, Dan's result is twelve bytes of eight bit bytes. So

Dan has bested me by one byte (but see below).

The orientations in two twelve-bit fields (2^11 and 3^7),

It looks like you are only storing the orientation of eleven of the

twelve edge cubies. The orientation of the twelfth can be inferred from

the orientation of the first eleven. On the other hand, you could store

all twelve and still fit in twelve bits. It also looks like you are only

storing the orientation of seven of the eight corner cubies. Again, the

orientation of the eighth can be inferred from the orientation of the

first seven. This time it matters. That is, 3^7 will fit in twelve

bits, but 3^8 will not, if I am counting it right.

Also, postmultiplying by a fixed permutation can be done with table

lookup without unpacking. I used this feature for twelve permutations

of particular interest.I am somewhat rusty on the implications of using this representation

in conjunction with Shamir's algorithm. I think it provides an

ordering of the permutations that enables at least an approximation to

the random access you need, then you unpack it and do a better job.

I think that unpacking would be required to build and traverse the "Shamir

tree", but the unpacking that would be required should be relatively easy.

I have always been reluctant to form compositions of packed formats

because it seemed both messy and slow to have to unpack both permutations

which are being composed and then to repack the result. In principle,

what you have to do is about the same as what you have to do in building

and traversing the "Shamir tree" with packed formats. But in practice it

seems a lot messier to unpack two permutations and to repack their

composition than to simply unpack one permutation as you traverse a tree.

Dan seems to have solved the problem for certain specific cases (and for

post-multiplying only) via table lookup. It is not clear to me that

table lookup could be used for the more general case of multiplying any

permutation by any other permutation.

I have always known that the supplements of the corners and edges could be

reduced by one byte each unpacked, down to seven bytes for the corners and

down to eleven bytes for the edges. The missing bytes could always be

reconstructed, but I didn't want to bother. Now, it occurs to me that

working with the supplements alone and never expanding them back to S24 x

S24, there is really no reason ever to reconstruct the missing bytes.

Hence, we can have an eighteen byte representation unpacked. The eighteen

byte representation easily packs down to twelve bytes (same as Dan's).

We could surely do better if we tried. Log2(|G|) is about 65.22, so we

should be able to represent each position in 66 bits, or in 9 bytes. But

I don't think the packing required would be worth the trouble.

66 bits is the theoretical minimum to represent |G| positions if the

positions are independent. But the positions are not really independent

(e.g., M-conjugacy). I'm not sure exactly what the best we can do

actually is.

My Shamir program is going to represent each position as a pair of indices

(i1,i2). i2 will be a single byte containing 1..48 and indexing M. i1

will be two or three bytes indexing a table of representatives of

M-conjugacy classes. The table in turn will consist of eighteen byte

supplements of permutations less the last edge and the last corner cubie.

A two-byte index will cover quarter turns through level 6 of the tree

(there are 18,395 representatives at level 6). A three-byte index will

cover quarter turns through level 9 of the tree (there are 14,956,266

representatives at level 9). I am dubious that I will even get into the

three byte index business. It will simply take too long. That is, a two

byte index through level 6 will allow level's 7 through 12 to be

calculated. It may well take too long to go any further than that.

Anyway, (i1,i2) means m'[i2]X[i1]m[i2]. The indices (i1,i2) will be

sorted according to the lexicographic order of m'[i2]X[i1]m[i2]. The

"Shamir tree" will be built with the indices as the leaf nodes. The

effective storage required for each position will be maybe five bytes or

so because you have to count the table of representatives in any honest

accounting of memory requirements. Thus, the tree structure itself will

be the biggest consumer of memory.

This approach will not require any packing or unpacking, but it will

require lots of extra multiplying of permutations. However, at most

points in the processing, it will not be necessary to multiply the entire

permutation. Multiplying a single cell of the vector will usually suffice

for comparing vectors, traversing the tree, etc.

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us Pellissippi State (423) 539-7127 10915 Hardin Valley Road (423) 694-6435 (fax) P.O. Box 22990 Knoxville, TN 37933-0990