Лучшие способы реализации операции по модулю (вопрос алгоритма)

Я не уверен, что вы там рассчитываете, если честно. Вы говорите об операции по модулю, но обычно операция по модулю выполняется между двумя числами a и b, и ее результатом является остаток от деления a на b. Где a и b в вашем псевдокоде...?

В любом случае, может это поможет: a mod b = a - floor(a / b) * b.

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

Еще один способ ускорить вычитание — использовать бинарный поиск. Если вы хотите a mod b, вам нужно вычесть b из a до тех пор, пока a не станет меньше b. Итак, в основном вам нужно найти k такое, что:

a - k*b < b, k is min

Один из способов найти это k — линейный поиск:

k = 0;
while ( a - k*b >= b )
    ++k;

return a - k*b;

Но вы также можете выполнить бинарный поиск (только несколько тестов, но он работал на всех из них):

k = 0;
left = 0, right = a
while ( left < right )
{
    m = (left + right) / 2;
    if ( a - m*b >= b )
       left = m + 1;
    else
       right = m;
}

return a - left*b;

Я предполагаю, что решение для бинарного поиска будет самым быстрым при работе с большими числами.

Если вы хотите вычислить a mod b и только a является большим числом (вы можете хранить b в примитивном типе данных), вы можете сделать это еще быстрее:

for each digit p of a do
    mod = (mod * 10 + p) % b
return mod

Это работает, потому что мы можем записать a как a_n*10^n + a_(n-1)*10^(n-1) + ... + a_1*10^0 = (((a_n * 10 + a_(n-1)) * 10 + a_(n-2)) * 10 + ....

Я думаю, что бинарный поиск - это то, что вы ищете.

Есть много способов сделать это за время O(log n) для n бит; вы можете сделать это с умножением, и вам не нужно повторять 1 бит за раз. Например,

a mod b = a - floor((a * r)/2^n) * b

где

r = 2^n / b

предварительно вычисляется, потому что обычно вы используете один и тот же b много раз. Если нет, используйте стандартный метод суперсходящейся полиномиальной итерации для обратного (итерация 2x - bx^2 в фиксированной точке).

Выберите n в соответствии с диапазоном, в котором вам нужен результат (для многих алгоритмов, таких как возведение в степень по модулю, это не обязательно должно быть 0..b).

(Много десятилетий назад мне казалось, что я нашел способ избежать двух умножений подряд... Обновление: я думаю, что это Умножение Монтгомери (см. Алгоритм REDC). Я беру свои слова назад, REDC выполняет ту же работу, что и более простой алгоритм, описанный выше. Не знаю, зачем вообще был изобретен REDC... Возможно, задержка немного меньше из-за использования младшего порядка результат в цепное умножение вместо результата более высокого порядка?)

Конечно, если у вас много памяти, вы можете предварительно вычислить все частичные суммы 2^n mod b для n = log2(b)..log2(a). Многие программные реализации делают это.

Если вы используете сдвиг и сложение для умножения (что отнюдь не самый быстрый способ), вы можете выполнять операцию по модулю после каждого шага сложения. Если сумма больше модуля, вы вычитаете модуль. Если вы можете предсказать переполнение, вы можете выполнять сложение и вычитание одновременно. Выполнение по модулю на каждом шаге также уменьшит общий размер вашего множителя (такая же длина, как и входная, а не двойная).

Сдвиг модуля, который вы делаете, приближает вас к полному алгоритму деления (модуль просто берет остаток).

EDIT Вот моя реализация на Python:

def mod_mul(a,b,m):
    result = 0
    a = a % m
    b = b % m
    while (b>0):
        if (b&1)!=0:
            result += a
            if result >= m: result -= m
        a = a << 1
        if a>=m: a-= m
        b = b>>1
    return result

Это просто модульное умножение (result = a*b mod m). Операции по модулю в верхней части не нужны, но служат напоминанием о том, что алгоритм предполагает, что a и b меньше m.

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

Для самого модуля я не уверен. Для модуля по модулю как части более крупной модульной экспоненциальной операции, искали ли вы умножение Монтгомери, как указано в страницу википедии по модульному возведению в степень? Прошло некоторое время с тех пор, как я изучал этот тип алгоритма, но, насколько я помню, он обычно используется в быстром модульном возведении в степень.

изменить: как бы там ни было, ваш алгоритм по модулю на первый взгляд кажется нормальным. Вы в основном выполняете деление, которое представляет собой повторяющийся алгоритм вычитания.

Этот тест (modulus(n-1) != 1) // битовый тест?

- кажется излишним в сочетании с (modulus<result).

При проектировании аппаратной реализации я должен осознавать, что тесты меньше/больше, чем тесты, подразумевают больше логики (вычитания), чем побитовые операции и ветвления на нуле.

Если бы мы могли легко выполнять побитовые тесты, это могло бы быть быстро:

m=msb_of(modulus)

while( result>0 ) 
{
  r=msb_of(result) //countdown from prev msb onto result
  shift=r-m        //countdown from r onto modulus or 
                   //unroll the small subtraction 

  takeoff=(modulus<<(shift))  //or integrate this into count of shift

  result=result-takeoff;  //necessary subtraction

  if(shift!=0 && result<0)
  { result=result+(takeoff>>1); }

  } //endwhile

if(result==0) { return result }
else          { return result+takeoff }

(непроверенный код может содержать ошибки)

result многократно уменьшается на modulus, сдвигается для соответствия старшим значащим битам.

После каждого вычитания: result имеет шанс ~50/50 потерять более 1 старшего разряда. Он также имеет ~ 50/50 шанс стать отрицательным, добавление половины того, что было вычтено, всегда снова сделает его положительным. > его следует вернуть в плюс, если сдвиг не был = 0

Рабочий цикл завершается, когда result недоработано, а 'shift' равен 0.