Modulo Алгоритм создания

Question

Хорошо это домашнее задание вопрос, который я нарушающие покой мой мозг о

Показать алгоритм, который на входе целых чисел а, Ь где а п разрядное и б < а, вычисляет мод б в O (N^2)

Я придумал следующий алгоритм, и я подумал, что я нахожусь в правильном направлении:

modulus(a,b) 
c = a-b; 
modulus (c,b) 
result c; 

будет ли это правильно? Или я делаю это слишком интуитивно? Какие-нибудь советы?

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

Answer 1

Чтобы вычислить mod b, вы должны вычитать кратность b от a до тех пор, пока результат не станет меньше b. Для простоты предположим, что a> = 0, b> 0, но вы можете использовать отношения mod (-a, b) = mod (a, -b) = -mod (a, b) для восстановления отрицательно- подписанных случаев.

Самый наивный (но неэффективный) способ реализации mod заключается в следующем:

def mod(a, b): 
    while a >= b: 
     a -= b 
    return a 

Это ужасно, когда гораздо больше, чем Ь. Сложность - O (a/b), которая является O (2^n) в худших случаях, где n - количество бит. Вместо этого мы можем попытаться вычесть большие кратные b, и мы можем сделать это с битовым сдвигом.

def mod(a, b): 
    bs = b 
    while bs <= a: 
     bs <<= 1 
    while bs > b: 
     bs >>= 1 
     if a >= bs: a -= bs 
    return a 

В этом коде мы сохраняем смещение b (в переменной bs) до тех пор, пока оно больше, чем a. Затем один шаг за шагом, мы переносим его обратно на b, вычитая значение из a, если мы сможем. Это по существу реализация длинного деления в двоичном формате.

Что касается временной сложности: сдвиг влево - это O (n) (предполагая, что мы имеем дело с произвольными большими числами, где n - количество бит), так как это сравнение и вычитание. Это делает обе петли while в этой реализации O (n^2) по мере необходимости.