Более эффективные способы реализации модульной операции (вопрос алгоритма)

Ответ 1

Я не уверен, что вы рассчитываете там, чтобы быть честным. Вы говорите об операции по модулю, но обычно операция по модулю находится между двумя номерами 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 + ...

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

Ответ 2

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

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

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 &lt&lt 1
        if a>=m: a-= m
        b = b>>1
    return result

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

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

Ответ 3

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

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

Ответ 4

Этот тест (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 }

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

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

После каждого вычитания: result имеет вероятность 50/50 потерять более 1 мсб. У этого также есть вероятность 50/50 идти отрицательно, добавление половины того, что было вычтено, всегда положит его в положительное снова. > он должен быть возвращен в положительный, если сдвиг не был = 0

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

Ответ 5

Есть много способов сделать это за 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). Многие программные реализации делают это.