Инъективная функция сопряжения

Question

Я ищу функцию сопряжения f: ZxZ -> Z со следующими характеристиками:

• Это не должно быть обратимо. Мне нужно только, чтобы он был инъективным (разные пары отображаются на разные целые числа), мне никогда не нужно вычислять пару обратно.
• Определяется над Z (целые числа со знаком)
• Эффективно вычислимо

В данный момент я использую f (x, y) = x + (max (x) -min (x) +1) * y

Это работает, мне просто интересно, может ли быть другая функция, которая более эффективно использует пространство результатов, учитывая, что:

• x, y - целые числа со знаком до 64 бит
• f (x, y) - целое число, максимум 64 бита
• len (f (x, y)) <= 64 бита легко вычисляется </li>

Я знаю, что это означает, что я не могу отобразить все комбинации x, y без результата для переполнения. Я достаточно счастлив, имея возможность установить, будет ли преобразование соответствовать 64 битам или нет. По этой причине идеальная функция отображения будет использовать доступные 64 бита максимально эффективно.

Любой совет?

Answer 1

Полиномы CRC быстро вычисляются с большой диффузией.Я уверен, что вы получите библиотеки для вашего любимого языка.Объедините оба целых числа в 128 бит и вычислите CRC.

Имейте в виду, что вы не можете отобразить 128 бит в 64 битах без коллизий.

Answer 2

Чтобы закодировать два 64-битных целых числа в однозначное уникальное число, возможны 2^64 * (2^64 -1) комбинации входов, поэтому согласно очевидному принципу Pigeonhole нам нужен выход размером не менее 2^64 * (2^64 -1), что равно 2^128 - 2^64, или, другими словами, вам нужна емкость 128 бит для хранения всех возможных выходных данных.

---

Я знаю, что это не может существовать для всех значений. Но это зависит от значений, а не от типов данных. Например. f (4,5) все еще можно выполнить, даже если 4 и 5 хранятся как 64-битные целые числа. В зависимости от используемой функции легко проверить наличие переполнений (в этом случае я бы не использовал отображение).

Вы это знаете. Тем не менее, как вы говорите, вы можете ограничить максимальные значения для ваших 64-битных входов. Выходные данные могут быть 64-разрядными целыми числами со знаком или без знака.

Вывод подписан, реализация на C #:

public static long GetHashCode(long a, long b)
{
    if (a < int.MinValue || a > int.MaxValue || b < int.MinValue || b > int.MaxValue)
        throw new ArgumentOutOfRangeException();

    var A = (ulong)(a >= 0 ? 2 * a : -2 * a - 1);
    var B = (ulong)(b >= 0 ? 2 * b : -2 * b - 1);
    var C = (long)((A >= B ? A * A + A + B : A + B * B) / 2);
    return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}

Вывод без знака, реализация на C #:

public static ulong GetHashCode(long a, long b)
{
    if (a < int.MinValue || a > int.MaxValue || b < int.MinValue || b > int.MaxValue)
        throw new ArgumentOutOfRangeException();

    var A = (ulong)(a >= 0 ? 2 * a : -2 * a - 1);
    var B = (ulong)(b >= 0 ? 2 * b : -2 * b - 1);
    return A >= B ? A * A + A + B : A + B * B;
}

Реализация без знака будет немного быстрее из-за меньшего количества вычислений. Нижняя и верхняя границы для уникальной пары составляют int.MaxValue (-2147483648) и int.MaxValue (2147483647). Исходная функция взята отсюда . Упомянутая в ссылке функция «Элегантное сопряжение» является наиболее эффективной из возможных, поскольку она сопоставляется с каждой отдельной точкой в ​​доступном пространстве. Подробнее об аналогичных методах см. Отображение двух целых чисел в одно уникальным и детерминированным способом