Тессеральная арифметика / квадродерево

Question

Некоторое время назад я занимался проектами по поиску пути с помощью квадродерев, и я хотел бы улучшить его производительность. Кажется, что использование тессеральной арифметики для определения смежности узлов (согласно этой странице , любезно предоставленной отделом географии Университета Британской Колумбии) будет намного быстрее, чем метод грубой силы, который я использую в данный момент. (Я проверяю общие ребра, что прекрасно работает для статического дерева квадрантов, но было бы слишком много накладных расходов, если бы карта менялась).

Я более или менее понимаю, что сказано в разделе «Алгоритм смежности», но я не совсем уверен, с чего начать. Меня в первую очередь интересует C #, но было бы здорово, если бы уже был какой-то источник информации о работе с тессеральной арифметикой, на который я мог бы смотреть независимо от языка. В противном случае, кто-нибудь мог бы дать мне несколько советов по работе с переносами сложения / вычитания?

Answer 1

Ну, я не знаю ни одного способа сделать это эффективно, но обычный алгоритм «добавления с побитовыми операциями» предлагает следующий алгоритм (не тестировался):

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;
}

, который возможно зацикливаетсямного, если есть цепочки для переноса.

---

На самом деле, есть гораздо лучший способ сделать это.

Обратите внимание, что для z = interleave(a, -1); w = interleave(b, 0); добавление z и w напрямую дает частично правильный результат, потому что любые переносы переносятся повторно (все биты "между ними" равны 1).Единственная «проблема» заключается в том, что она уничтожает координаты y.

Таким образом, чтобы добавить два тессеральных числа z = interleave(a, b); w = interleave(c, d);, есть хороший короткий способ сделать это:

int xsum = (z | 0xAAAAAAAA) + (w & 0x55555555);
int ysum = (z | 0x55555555) + (w & 0xAAAAAAAA);
int result = (xsum & 0x55555555) | (ysum & 0xAAAAAAAA);

Answer 2

Я думаю, что самый простой способ иметь дело с тессеральной арифметикой - это «разбить бит» на числа, выполнить любое количество арифметических операций в обычном режиме и «сжать» их обратно, когда нужна форма тессерала:

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

(Этот пример работает только для unsigned. Для целых чисел со знаком распакуйте каждое число в две переменные и выполните обычную арифметику для обеих частей отдельно).

Вы можете найти быстрые реализации для "bit-unzip""и" bit-zip "в" Matters Computational", глава 1.15" Битовый zip ".