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