Przypomnijmy konstrukcję typowego programu. Jądrem programu jest cykl, w którym sie po kolei wykonują operacje t(r) dla generatorów 1,2,4,8,16,… . Na przykład, w programie dla sumy wszystkich liczb „a” umieszczonych w punktach przestrzeni (C2 )3 mamy najpierw ekspansję do całej przestrzeni (C2 )3 a następnie
for (g= 1; g < 8; g= g << 1)
{
A= a;
t(r);
a = a + A;
}
Operacje transferu t(r) się tu stosują do wszystkich antionów naraz. Na przykład t(2) przemieszcza antiony (antionowe dane) z punktów 0,1,4,5 do punktów 2,3,6,7, i odwrotnie. Wygląda to jak refleksja, zwierciadlane odbicie w 3-wymiarowej sztywnej bryle, w poprzek odpowiedniej płaszczyzny. *)
- Operację transferu mozna przyrównać do refleksji tylko wtedy, kiedy wszystkie antiony w (C2 )n równoczesnie wykonują t(r) wzdłuz tego samego generatora r. Ogólnie równoczesne t() w interpretacyjnym kroku obliczenia Sτ to jakaś permutacja antionów.
Wracajac do omawianego przypadku, połowa antionów zajmujących punkty …xxx0x przechodzi do przeciwległych punktów …xxx1x i na odwrót (symbol x zastępuje wszystkie mozliwe 0 i 1). Tak jest okreslona operacja t(2), mianowicie transfer wzdłuż generatora 2, czyli z „currentpoint” do „currentpoint ^ 2”. Różnice pomiędzy algorytmami są zawarte tylko w operacjach na danych. Jesli w powyzszym programie zamienimy instrukcję „a= a+A” na cos innego, otrzymamy inny algorytm. W programie sortowania według algorytmu Batchera (omówimy w jednym z nastepnych rozdziałów) bedziemy mieli bardziej skomplikowaną konstrukcję z dwoma włozonymi cyklami i w rezultacie sekwencję generatorów 1 / 2,1 / 4,2,1 / 8,4,2,1 / 16,8,4,2,1 / ….
Bazy i podbazy
Przygotujemy teraz teren dla rozważania ogólniejszych ruchów, kiedy transfer poszczególnych antionów będzie zależał od wartosci danych w punktach, czyli w zasadzie od „currentpoint”. Wejdziemy na teren trochę ogólniejszych permutacji antionów, a co za tym idzie, ogólniejszych transformacji danych w przestrzeni.
Wprowadzimy kilka terminów i zapisów. Zbiór wszystkich generatorów przestrzeni (C2 )n nazwiemy bazą. Umówmy się, że wszystkie generatory bazy razem wzięte zapiszemy 111111…1 . Na przykład 111111 będzie oznaczać bazę zawierajacą generatory 100000, 010000, 001000, 000100, 000010, 000001. Taka baza zapisana dziesiętnie (po arabsku) wyglada 63. Jesli w binarnym zapisie bazy niektóre jedynki zastąpimy zerami, otrzymamy podbazę. Podbaza to po prostu podzbiór generatorów. Przykładowo 14 = 1110, 51 = 110011, … itp. są podbazy dla odpowiednich baz 15 i 63. Szczególnym przypadkiem jest jednoelementowa podbaza, jest to to samo co jeden generator.
Kod Graya
Kod Graya jest specjalny binarny kod dla kodowania liczb. Wyjasnimy na przykładzie. W schemacie poniżej mamy w pierwszej kolumnie liczby 0,1,… 7, w drugiej kolumnie te same liczby są zapisane dwójkowo standardowym sposobem. W trzeciej kolumnie kody z drugiej kolumny zostały przesunięte o jedną pozycję wprawo. Najbardziej prawy bit przesuwanego kodu wychodzi z naszego pola widzenia (odrzucamy go, nie interesuje nas) a do bitu najbardziej wlewo wkładamy zero.
0 000 000 000
1 001 000 001
2 010 001 011
3 011 001 010
4 100 010 110
5 101 010 111
6 110 011 101
7 111 011 100
Czwarta kolumna to juz jest kod Graya. Zliczamy przy pomocy „^” drugą i trzecią kolumnę, co mozna zapisać w postaci funkcji:
int _cdecl gray(int v)
{
return (v ^ (v >> 1));
}
Operację „^” znamy z jezyka programowania „C”. Polega na dodawaniu (odejmowaniu) modulo 2 przeciwległych bitów w dwójce argumentów wyrażonych binarnie. Parametr „v” w powyzszej funkcji „gray(v)” jest wartosc kodu z drugiej kolumny. ” v >> 1″ oznacza przesunięcie kodu w prawo.
Geneza kodu Graya i inne ciekawe informacje mozna przeczytac w dodatku. W tym miejscu nas interesuje właściwość kodu Graya polegajaca na tym, że idąc w czwartej kolumnie od góry w dół (a nastepnie z powrotem do góry), sąsiednie kody róznią sie w jednym bicie.
I o to nam chodzi, zeby antion przesuwał sie w (C2 )n tak jak na rysunku. Sasiednie punkty w wyznaczonej trajektorii róznia sie w jednym bicie. Dobrze jest zapamiętać tę trajektorię jako ciag liczb 0,1,3,2,6,7,5,4, i znowu „zero”. Taka trajektoria (droga) jest też znana jako cykl Hamiltona w grafie (C2 )n . Ogólnie jest więcej cykli Hamiltona dla danego grafu (jesli istnieją), my zafiksujemy sobie właśnie tę, okresloną programowo.
Gray transfer
Zdefiniujemy teraz funkcję gtrans(s), która obliczy wartość generatora jako przesuniecia z „currentpoint” do nastepnego punktu wzdłuż trajektorii Graya. Parametrem „s” funkcji jest podbaza, w ramach której się to przesunięcie dzieje. Najpierw przykład. Skorzystamy z powyższego rysunku, gdzie podbaza s= 7, i wezmiemy do pomocy tabelkę. W pierwszej i drugiej kolumnie mamy „currentpoint”, w trzeciej kolumnie jest następny punkt w drodze wzdłuż trajektorii Graya, a w czwartej kolumnie mamy generator, który takie przesuniecie załatwi. Wynikowy generator gtrans(s) jest więc różnicą (sumą modulo 2) kodów z drugiej i trzeciej i drugiej kolumny.
0 000 001 001
1 001 011 010
3 011 010 001
2 010 110 100
6 110 111 001
7 111 101 010
5 101 100 001
4 100 000 100
W komputerze nie mamy bezpośredniej operacji, która nam obliczy nastepna wartość wzdłuz trajektorii Graya i dlatego w programie mamy troche skomplikowane działania: funkcję antigray(), zwykłe dodawanie +1 i z powrotem funkcję gray(). Poniżej przedstawiona funkcja gtrans(s) działa poprawnie dla specjalnych podbaz (2n )-1 , czyli dla baz …000111 itp. Pełna wersja gtrans(s) dla dowolnej podbazy (z dziurami w ciagu 11111…11) jest w prob-bope.cpp.
Na marginesie zauważmy, że funkcja gray(v) przypomina rózniczkowanie a antigray(v) całkowanie. Parametr „v” wyrażony binarnie traktujemy jako funkcję, bo funkcja to jest własciwie ciąg warosci. W przypadku rózniczkowania przesuwamy o 1 i odliczamy, w przypadku całkowania zliczamy róznice.
Program na współczynniki dwumianowe
Funkcję gtrans() wykorzystamy w programie, który liczy współczynniki (nk) we wzorze (1 + x)n = 1 + x + n.x + … . Tez nazywane współczynnikami Pascala, bo pojawiaja sie w znanym trójkącie Pascala. Poruszamy się wzdłuz trajektorii Graya w przestrzeni (C2 )4 .
Wynik jest nastepujący:
currentpoint 6 binom 1
currentpoint 2 binom 4
currentpoint 14 binom 0
currentpoint 10 binom 0
currentpoint 4 binom 0
currentpoint 0 binom 1
currentpoint 12 binom 0
currentpoint 8 binom 0
currentpoint 7 binom 0
currentpoint 3 binom 6
currentpoint 15 binom 0
currentpoint 11 binom 0
currentpoint 5 binom 0
currentpoint 1 binom 4
currentpoint 13 binom 0
currentpoint 9 binom 0
Czyli dla punktów 0,1,3,2,6,7,5,4 (kolejność Graya) mamy wartosci zmiennej binom 1,4,6,4,1,0,0,0 jak ma być.