Знайомство з простими арифметичними алгоритмами і методами оцінки їх складності (Практичне заняття № 1)

Практичне заняття №1 (ТСО).

Ціль заняття: Ознайомитися з простими арифметичними алгоритмами і методами оцінки їх складності.

 Прості алгоритми і їх складність.

 Складання і віднімання.

 Помітимо, що стандартні шкільні алгоритми складання і віднімання чисел стовпчиком, мають оцінку складності O(log N), де N- більше з двох чисел. Це мінімально можлива оцінка складності. Ми розглядаємо оцінку складності з точністю до константного множника.

 Множення і ділення.

 Для множення і ділення двох чисел N і M алгоритми множення стовпчиком і ділення кутом дають оцінку O(log N log M) . Тому для функцій оцінки складності множення і ділення двох n- розрядних чисел виконується нерівність

 n£F(n)£O(n²)

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

 Позначимо M(n) - складність операції множення двох n-розрядних чисел, D(n) - складність операції ділення із залишком 2n- розрядного числа на n- розрядне число, S(n)- складність операції зведення в квадрат n -розрядного числа і R(n)- складність операції обернення n- розрядного числа.

 Алгоритм Евкліда.

 Позначатимемо НСД чисел А і В через (А, В). Нагадаємо, що алгоритм Евкліда полягає в послідовному виконанні операції ділення із залишком до отримання нульового залишку. Хай А > В > 0 . Позначимо A = r_-1 , B = r₀  і за і . Тоді  і до отримання залишку  необхідно виконати  ділення.

Оцінка складності алгоритма Евкліда

Розширений алглритм Евкліда.

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

 Наприклад

5x +7y НСД (5,7 )

1.  r_{- 1} = 5; r₀ = 7

x _{- 1} = 1; y _{- 1} = 0; x ₀ = 0; y ₀ = 1

d ₁ = ë r _{-  1} / r ₀  û =  ë 5 / 7 û = 0

r ₁ = r _{- 1} - d ₁ r ₀ = 5 - 0´ 7 = 5

x ₁ = x _{- 1}  - d₁ x ₀ = 1 - 0´ 0 = 1

y ₁ = y _{- 1} - d ₁  y ₀ = 0 - 0´ 1= 0

2.   d ₂ = ë r ₀  / r ₁  û =  ë 7 / 5 û = 1

r ₂ = r ₀  - d ₂  r ₁ = 7 - 1´ 5 = 2

x ₂ = x ₀   - d₂ x ₁ = 0 - 1´ 1 = - 1

y ₂ = y ₀  - d ₂  x ₁ = 1 - 1´ 0= 1

3. d ₃ = ë r  ₁ / r ₂  û =  ë 5 / 2 û = 2

r ₃ = r  ₁ - d ₃ r ₂ = 5 - 2´ 2 = 1

x ₃ = x  ₁  - d₃ x ₂ = 1 - 2´ ( - 1) = 3

y ₃ = y  ₁ - d₃  y ₂ = 0 - 2´ 1= - 2

4.  d₄ = ër₂ / r₃ û =  ë 2 / 1 û = 2

r₄ = r₂ - d ₄ r₃= 2 - 2´ 1 = 0

Справді знайдені числа і  , що задовольняють рівності

Д(5,7)

5 ´ 3 +7´ ( - 2 ) = НОД (5,7 )

Сам алгоритм можна представити таким чином:

r_{- 1} = А; r₀ = B

x _{- 1} = 1; y _{- 1} = 0; x ₀ = 0; y ₀ = 1

for i = 1 until r _i  > 0 do

        begin

                d _i = ë r _{i - 2}  / r _{i - 1}  û ;

                r _i = r _{i - 2} - d _i  r _{i - 1} ;

                x _i = x _{i - 2}  - d _i  x  _{i - 1} ;

                y  _i = y  _{i - 2} - d  _i   y  _{i - 1} ;

                i = i + 1;

end

Значення  і  при яких   будуть шуканими.

 Складність цього алгоритму відрізняється від складності звичайного алгоритму Евкліда не більше, ніж на константний співмножник, і складає

 , де  довжина запису чисел  і 

 Складання, віднімання.

 При складанні чисел в інтервалі . Сума   може вийти за межі інтервалу, тому може знадобитися ще одне віднімання .          ( 13 (mod 17) + 8 (mod 17) = 13 + 8 -17 = 4 (mod 17 )) Аналогічно, при відніманні може потрібно ще одне складання .  (7 (mod 13) - 12 (mod 13) = 7 - 12 + 13 = 8 (mod 13 )) Тому, складність цих операцій рівна .

 Множення.

 Для знаходження лишку, відповідного добутку двох лишків, треба виконати одне множення  -розрядних чисел і одне ділення  -розрядного числа на  -розрядне. Тому, складність даної операції рівна .

 У багатьох випадках, особливо при апаратній реалізації алгоритмів, зручно відмовитися від операцій множення і ділення і замінити їх операціями складання. Один з таких алгоритмів, що був запропонований                      П.Л. Монтгомері в 1985 році., полягає в наступному. Хай   -непарне число, потрібно помножити лишки  і . Розглянемо алгоритм:

R = 0;

for i = 0 until i < n do

          begin

if a_i = 1 then R = R + B;

if R - непарне then R = R + N;

R = R / 2;

end

if R ³ N then R = R - N.

Сутність даного алгоритма в тому, що в силу рівності

A =

множення числа В на число А зводиться до обчислення виразу

AB =