Jakiś czas temu wykonałem projekt na szukaniu ścieżki z drzewami czwórkowymi i chciałbym poprawić jego wydajność. Wygląda na to, że użycie arytmetyki tesseralnej do określenia sąsiedztwa węzłów (zgodnie z ta strona, dzięki uprzejmości wydziału geografii Uniwersytetu Kolumbii Brytyjskiej) byłaby znacznie szybsza niż metoda brute force, której obecnie używam (sprawdzam współdzielone krawędzie, co działa dobrze dla statycznego drzewa czwórkowego, ale byłoby zbyt duże, gdyby mapa się zmieniała).

Mniej więcej rozumiem, co zostało powiedziane w sekcji Algorytm sąsiedztwa, ale nie jestem pewien, jak zacząć. Interesuje mnie przede wszystkim C#, ale byłoby świetnie, gdyby pojawiło się już jakieś źródło do pracy z arytmetykami tesserowymi, na które mógłbym spojrzeć, niezależnie od języka. W przeciwnym razie, czy ktoś mógłby mi dać kilka wskazówek na temat radzenia sobie z dodawaniem/odejmowaniem niesie?

2
bendicott 18 luty 2012, 11:12

2 odpowiedzi

Najlepsza odpowiedź

Myślę, że najłatwiejszym sposobem radzenia sobie z tesseralną arytmetyką jest "rozpakowanie bitów" liczb, wykonanie dowolnej liczby operacji arytmetycznych w normalny sposób i "zipowanie bitów" z powrotem, gdy potrzebna jest forma tesseralna:

z = bit_zip(bit_unzip(x) + bit_unzip(y));

(Ten przykład działa tylko dla unsigned. W przypadku liczb całkowitych ze znakiem, rozpakuj każdą liczbę do dwóch zmiennych i wykonaj normalną arytmetykę na obu częściach osobno).

Szybkie implementacje „bit-unzip” i „bit-zip” można znaleźć w „Matters Computational ”, rozdział 1.15 „Bit-wise zip”.

2
Evgeny Kluev 21 luty 2012, 21:31

Cóż, nie znam żadnego sposobu, aby to zrobić wydajnie, ale zwykły algorytm „dodaj za pomocą operacji bitowych” sugeruje następujący algorytm (nie testowany):

static int tesseral_add(int x, int y)
{
    int a, b;
    do
    {
        a = x & y;
        b = x ^ y;
        x = a << 2; // move carry up 2 places instead of the usual 1
        y = b;
    } while (b != 0);
    return b;
}

Który prawdopodobnie zapętla się dość dużo, jeśli są łańcuchy nośne.


Właściwie jest na to o wiele lepszy sposób.

Zauważ, że dla z = interleave(a, -1); w = interleave(b, 0); dodanie z i w bezpośrednio daje częściowo poprawny wynik, ponieważ wszelkie przeniesienia są przenoszone ponownie (wszystkie bity "pomiędzy" to 1). Jedynym „problemem” jest to, że niszczy współrzędne y.

Tak więc, aby dodać dwie liczby tesseralne z = interleave(a, b); w = interleave(c, d);, jest na to fajny, krótki sposób:

int xsum = (z | 0xAAAAAAAA) + (w & 0x55555555);
int ysum = (z | 0x55555555) + (w & 0xAAAAAAAA);
int result = (xsum & 0x55555555) | (ysum & 0xAAAAAAAA);
4
harold 10 sierpień 2012, 23:56