Если x = (xn–1 … x0)b,
то вычисление x2 с помощью умножения в столбик потребует n2 операций
(умножений цифр – каждой на каждую). Если учесть повторения цифр в сомножителях, то количество операций можно сократить.
Рассмотрим эту идею на примере двузначного числа.
Пусть x = ( x1x0 ) b = x1b + x0.
Тогда x2 = x12b2 + 2 b x1x0 + x02,
что вычисляется за три умножения: умножение на b (b2) – это сдвиг числа на одну
(две) цифру влево, умножение на 2 при b = 2k – сдвиг на один бит влево, приb ≠2k – одна операция сложения.
Алгоритм быстрого возведения числа в квадрат.
Вход: x = (xn–1 … x0)b.
Выход: y = (y2n–1 … y0)b = x2.
Обозначения: u, v – цифры в системе счисления с основаниемb, c ∈ {0, 1} – бит переноса, (de)b – двузначные числа, (cde)b – трехзначные.
Для i от 0 до 2n – 1 положить yi = 0.
Для i от 0 до n – 1
2.1. Вычислить (uv)b = y2i + xi · xi; положить y2i = v, c = 0.
2.2. Для j от i + 1 до n – 1
вычислить (cuv)b = yi+j+ 2 xi · x j + (cu)b; положить yi+j = v.
2.3. Число (yi+n+1yi+n) увеличить на оставшийся перенос (cu)b.