Быстрое евклидово деление на С

Question

Я заинтересован в получении остатка от евклидова деления , то есть для пары целых чисел (i, n) найдите r, например:

i = k * n + r, 0 <= r < |k|

простое решение:

int euc(int i, int n)
{
    int r;

    r = i % n;
    if ( r < 0) {
        r += n;
    }
    return r;
}

Но так как мне нужно выполнить это десятки миллионов раз (это используется внутри итератора для многомерных массивов), я бы хотел избежать ветвления, если это возможно. Требования:

• Разветвление, но также желательно быстрее.
• Приемлемо решение, которое работает только для положительного n (но оно должно работать для отрицательного i).
• n заранее неизвестен и может принимать любое значение> 0 и

Редактировать

На самом деле довольно легко ошибиться в результате, поэтому вот пример ожидаемых результатов:

• euc (0, 3) = 0
• euc (1, 3) = 1
• euc (2, 3) = 2
• euc (3, 3) = 0
• euc (-1, 3) = 2
• euc (-2, 3) = 1
• euc (-3,3) = 0

Некоторые люди также беспокоятся, что не имеет смысла оптимизировать это. Мне это нужно для многомерного итератора, в котором элементы за пределами границ заменяются элементами в «виртуальном массиве», который повторяет исходный массив. Поэтому, если мой массив x равен [1, 2, 3, 4], виртуальный массив равен [...., 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4] и, например, x [-2] равен x 1 и т. Д. *

Для второго массива измерения d мне нужно евклидово деление d для каждой точки. Если мне нужно сделать корреляцию между массивом n ^ d и ядром m ^ d, мне нужно евклидово деление n ^ d * m ^ d * d. Для трехмерного изображения 100x100x100 точек и ядра 5 * 5 * 5 точек это уже ~ 400 миллионов евклидовых делений.

Answer 1

В своем ответе Эрику Бейнвиллу вы говорите, что большую часть времени 0 <= i < n и что у вас есть

if (i>=0 && i<n) return i;

как первая строка вашего euc() в любом случае.

Поскольку вы все равно проводите сравнения, вы можете также использовать их:

int euc(int i, int n)
{
    if (n <= i)            return i % n;
    else if (i < 0)        return ((i + 1) % n) + n - 1;
    else /* 0 <= i < n */  return i;  // fastest possible response for common case
}

Answer 2

Если вы также можете гарантировать, что я никогда не меньше -n, ​​вы можете просто поставить опциональное дополнение перед модулем. Таким образом, вам не нужна ветвь, и по модулю вырезается то, что вы добавили, если вам это не нужно.

int euc(int i, int n)
{
    return (i + n) % n;
}

Если я меньше -n, ​​вы все равно можете использовать этот метод. В таком случае вы, вероятно, точно знаете, в каком диапазоне будут находиться ваши значения. Поэтому вместо добавления n к i вы можете добавить x * n к i, где x - любое целое число, которое дает вам достаточный диапазон. Для дополнительной скорости (на процессорах, у которых нет однократного умножения), вы можете сдвигать влево вместо умножения.