From BRYAN@wvnvm.wvnet.edu Sat Dec 17 23:44:44 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA17750; Sat, 17 Dec 94 23:44:44 EST Message-Id: <9412180444.AA17750@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 7248; Sat, 17 Dec 94 23:44:42 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 9464; Sat, 17 Dec 1994 23:44:42 -0500 X-Acknowledge-To: Date: Sat, 17 Dec 1994 23:44:36 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Re: How Big is Big? In-Reply-To: Message of 12/17/94 at 12:55:35 from dlitwin@geoworks.com 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]=. 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