1. Арифметика многократной точности

1.1. Быстрое возведение в квадрат

Если x = (xn–1 … x0)b, то вычисление x2 с помощью умножения в столбик потребует n2 операций (умножений цифр – каждой на каждую). Если учесть повторения цифр в сомножителях, то количество операций можно сократить. Рассмотрим эту идею на примере двузначного числа. Пусть x = ( x1 x0 ) b = x1  + 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 – трехзначные.

  1. Для i от 0 до 2n – 1 положить y= 0.
  2. Для i от 0 до n – 1
    2.1. Вычислить (uv)b = y2i + xi · xi; положить y2i = v, c = 0.
    2.2. Для j от i + 1 до n – 1
      вычислить (cuv)byi+j + 2 xi · x j + (cu)b; положить yi+j = v.
    2.3. Число (yi+n+1 yi+n) увеличить на оставшийся перенос (cu)b.
  3. Ответ: y.