Возведение в квадрат длинного числа

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

• умножать операнд на себя самого, используя при этом один из приведенных выше алгоритмов умножения,
• использовать модификацию метода Карацубы,
• воспользоваться методом «треугольника».

Возведение в квадрат умножением

Первый метод прост, действуем по определению: С=A² - АЧА. При этом требуется выполнения n элементарных операций умножения и некоторого количества операций сложения

Метод Карацубы

Как и в алгоритме Карацубы представим основание в виде

А = b^n/2U₁+U₀.

Тогда: А² = (b^n/2U₁+U₀)² = bⁿU₁²+2b^n/2U₁U₀+U₀²,

т.е. требуется выполнение 2 операций возведения в квадрат и одной опера­ции умножения -значных чисел. Однако, воспользовавшись тождеством

2U₁U₀ = U₁² + U₀² – (U₁-U₀)²

получаем А² = (bⁿ+b^n/2)U₁²- b^n/2(U₁-U₀)² + (b^n/2+1)U_0|².

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

Метод «треугольника» возведения в квадрат

Однако из метода Карацубы все же можно выжать некоторое ускорение даже при малой разрядности операндов. Для этого представим основание степени в b-ичной системе счисления

_n-1

X=∑X_ibⁱ,

ⁱ⁼⁰

Очевидно, что

_n-1

X² = ∑ X²_i b²ⁱ +2∑X_iX_jb^i+j,

^{i=0 i<j}

Вычисления по этой формуле выполняет следующий алгоритм.

Алгоритм 1.7. Вычисление квадрата длинного числа А длины n цифр: С=А²

1.       С:=0;

2.       для i = 0…n-1 выполнить 3-11;

3.       для j = 0…i-1 выполнить 4-6;

4.       Т := Т + 2*A_i*A_i +C_i+j;

5.       С := LODIGIT (Т);‘

6.       T :=Т/b;

7.       Т := Т +A_i² + С_2i+1;

8.       С_2i := LODIGIT (T);

9.       T :=Т/b + C_i+j;

10.     С_2i+1 := LODIGIT (T);

11.     С_2i+2 := HIDIGIT (Т)

12.     конец.