From:

Subject:

On 12/17/94 at 12:55:35 dlitwin@geoworks.com said:

"Jerry Bryan" writes:

> I claim that you could store each position in a byte with clever

> indexing. Actually, you could store each position in 5 bits, or 5/8 of a

> byte...Could you explain what you mean by this? You can't mean each

possible cube position because you only get 256 from a byte. Are you

talking about each type of operation you can perform on a cube? I'd buy

that, but I'd think you could store that in 4 bits (12 possible moves).

I'm clearly missing something here.

I have talked about this before, but let's have a go at it again.

Previously, I have talked about it in terms of corners only or

edges only. This time, let's talk about it in terms of whole cubes.

In terminology we have used recently, we will talk about

representing G[C,E]=<Q[C,E]>. That is, we will only represent

corners and edges. There is no need for the purposes of

this paper to include Face centers because |G[C,E]| = |G[C,E,F]|.

For each cube position, we only need to store the depth, assuming

we have some way to index to the proper cell in a data structure

containing the depth for each cube position. As long as the depth

does not exceed 31, then 5 bits will suffice for each cell.

Start with G[C] and G[E] separately (corners only, and edges only).

Partition G[C] into equivalence classes of the form {m'(Xc)m}

for each m in M (the set of 48 rotations and reflections), for each

c in C (the set of 24 rotations), and for each X in G[C].

Partition G[E] into equivalence classes of the form {m'(Yc)m}

for each m in M, for each c in C, and for each Y in G[E]. These

tasks have already been accomplished via computer search.

For each {m'(Xc)m} choose a representative element V, and for each

{m'(Yc)m} choose a representative element W. It is not strictly

necessary, but it will prove convenient if each representative

element is even, and such a choice is always possible. Denote the

sets of representative elements as G*[C] and G*[E]. These sets

have already been created via computer search. We have

|G*[C]|=77802 and |G*[E]|=851625008. The sets G*[Cl and G*[E]

will be used as indices, and will have to be stored. But storing

them is between 10^12 and 10^13 bytes, which is a drop in the

bucket compared to storing 10^18 depths.

We can think of a cube in G[C,E] as XY with X in G[C] and Y in G[E].

That is, X is the corners and Y is the edges. Both X and Y are even,

or both X and Y are odd, and the choice of odd or even can be thought

of as an index which doesn't have to be stored. V=Repr{m'(Xc)m} can

be thought of as an index for XY. V has to be stored, but it only

has to be stored once for the whole data structure, not once very

every position XY for which V=Repr{m'(Xc)m}. Similarly,

W=Repr{m'(Yc)m} can be thought of as an index for XY, and W only

has to be stored once for the entire data structure.

Given V, we can write X=n'(Vd)n for some fixed n in M and for

some fixed d in C. Notice that since V is even, the parity of

d is the same as the parity of X, and hence there are 12 rather than

24 choices for d. Notice also that while both n and d will always exist,

neither is necessarily unique, depending on how "symmetrical" is V.

Hence, a selection procedure is necessary to assure that both n and

d are unique. d can be thought of as an index for XY, and d does

not need to be stored. As for n being an index, see two paragraphs

below.

Given W, we can write Y=o'(We)o for some fixed o in M and for some

fixed e in C. Notice that since W is even, the parity of

e is the same as the parity of Y, and hence there are 12 rather than

24 choices for e. Notice also that while both o and e will always exist,

neither is necessarily unique, depending on how "symmetrical" is W.

Hence, a selection procedure is necessary to assure that both o and

e are unique. e can be thought of as an index for XY, and e does not

need to be stored. As for o being an index, see the next paragraph.

We could think of n and o as both being indices for XY, with both

of them having 48 different values. The indices would not have to be

stored. However, we can write XY as (n'(Vd)n)(o'(We)o). Any

M-conjugate of XY has the same length as XY. If we conjugate by nn'

we have

n(n'(Vd)n)(o'(We)o)n'=n(n'(Vd)n)n')(n(o'(We)o)n')=(Vd)(p'(We)p),

where p=on', p'=no', and p is in M. Hence, there is only one index

into M with 48 different values, not two.

Putting this all together, we need a table with

2*77802*851625008*12*12*48 cells, and each cell could be 5 bits.

The total number of cells is about .916*10^18. The actual number

of M-conjugate classes is about .901*10^18. (I am using a slightly

unusual decimal point placement in deference to the total size of

the table being "about 10^18".) The reason that the table size

is a bit larger than the number of M-conjugate classes is that the

table will contain some empty cells due to the non-uniqueness of

some of the indexing by C and M. The number of cells that will be

non-empty *will* in fact be exactly the same as the number of

M-conjugate classes.

I have talked about indices that would have to be stored, and indices

that would not have to be stored. As an example of indices that

would have to be stored, consider a table of names and ages. E.g.,

Name Age Doe, John 25 Evans, Bill 42 Jones, Jane 33 Smith, Sarah 21

You can think of the names as indices into the ages, and the names do

have to be stored.

On the other hand, think of storing N floating point numbers in an

array X, with I as an index for I in 1..N. You would write this

in a program as something like X[I]. The index I would have to be

stored once, I suppose, but it would not have to be stored with each

X.

Similarly, in the proposed structure for storing all of God's

Algorithm, the indices V and W would have to be stored, but the

parity index 1..2 would not have to be stored, the rotation index

1..12 for V would not have to be stored, the rotation index 1..12

for W would not have to be stored, and the M conjugation

index 1..48 for V or W (but not both) would not have to be stored.

But even though the indices V and W would have to be stored, they

would only have to be stored once for the whole program, not for

each cube position.

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU