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

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

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

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

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

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

А = bn/2U1+U0.

Тогда: А2 = (bn/2U1+U0)2 = bnU12+2bn/2U1U0+U02,

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

2U1U0 = U12 + U02 – (U1-U0)2

получаем А2 = (bn+bn/2)U12- bn/2(U1-U0)2 + (bn/2+1)U0|2.

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

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

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

n-1

X=∑Xibi,

i=0

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

n-1

X2 = ∑ X2i b2i +2∑XiXjbi+j,

i=0 i<j

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

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

1.       С:=0;

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

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

4.       Т := Т + 2*Ai*Ai +Ci+j;

5.       С := LODIGIT (Т);

6.       T :=Т/b;

7.       Т := Т +Ai2 + С2i+1;

8.       С2i := LODIGIT (T);

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

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

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

12.     конец.