Возведение в степень возведением в квадрат

редактировать

Алгоритм быстрого возведения в степень

В математике и компьютерном программировании, возведение в степень возведением в квадрат - это общий метод быстрого вычисления больших положительных целых степеней числа или, в более общем смысле, элемента полугруппа, например полином или квадратная матрица . Некоторые варианты обычно называются алгоритмами возведения в квадрат и умножения или двоичного возведения в степень . Они могут иметь весьма общее применение, например, в модульной арифметике или в питании матриц. Для полугрупп, для которых обычно используется аддитивная нотация, например, эллиптические кривые, используемые в криптографии, этот метод также называется с двойным сложением. .

Содержание

1 Базовый метод
2 Вычислительная сложность
3 Двухуровневый метод
4 Метод скользящего окна
5 Метод лестницы Монтгомери
6 Показатель с фиксированной базой
- 6.1 Метод Яо
- 6.2 Евклидов метод
7 Другие приложения
8 Примеры реализации
- 8.1 Вычисление по степеням 2
  - 8.1.1 Пример выполнения: compute 3
  - 8.1.2 Пример выполнения: compute 3
- 8.2 Вычисление произведений степеней
  - 8.2.1 Пример
  - 8.2.2 Использование преобразования
  - 8.2.3 Примеры
9 Перекодирование знаковых цифр
10 Альтернативы и обобщения
11 См. Также
12 Примечания
13 Ссылки

Базовый метод

Метод основан на наблюдении, что для положительного целого числа n мы имеем

xn = {x ( x 2) n - 1 2, если n нечетное (x 2) n 2, если n четное. {\ displaystyle x ^ {n} = {\ begin {case} x \, (x ^ {2}) ^ {\ frac {n-1} {2}}, {\ t_dv {if}} n {\ t_dv {нечетно}} \\ (x ^ {2}) ^ {\ frac {n} {2}}, {\ t_dv {if}} n {\ t_dv {четно}}. \ end {cases} }}

x ^ {n} = {\ begin {cases} x \, (x ^ {2}) ^ {\ frac {n-1} {2}}, {\ t_dv {if}} n {\ t_dv {нечетное}} \\ (x ^ {2}) ^ {\ frac {n} {2}}, {\ t_dv {if}} n {\ t_dv {четно}}. \ end {case}}

Этот метод использует биты экспоненты для определения вычисляемых мощностей.

В этом примере показано, как вычислить $x 13 {\ displaystyle x ^ {13}}$ ${\ displaystyle x ^ {13}}$ с помощью этого метода. Показатель степени 13 в двоичной системе равен 1101. Биты используются в порядке слева направо. У экспоненты 4 бита, поэтому есть 4 итерации.

Сначала инициализируйте результат равным 1: $r ← 1 (= x 0) {\ displaystyle r \ leftarrow 1 \, (= x ^ {0})}$ ${\ displaystyle r \ leftarrow 1 \, (= x ^ {0})}$ .

Шаг 1)

r ← r 2 (= x 0) {\ displaystyle r \ leftarrow r ^ {2} \, (= x ^ {0})}

{\ displaystyle r \ leftarrow r ^ {2} \, (= х ^ {0})}

; бит 1 = 1, поэтому вычисляем

r ← r ⋅ x (= x 1) {\ displaystyle r \ leftarrow r \ cdot x \, (= x ^ {1})}

{\ displaystyle r \ leftarrow r \ cdot x \, (= x ^ {1})}

;

Шаг 2)

r ← r 2 (= x 2) {\ displaystyle r \ leftarrow r ^ {2} \, (= x ^ {2})}

{\ displaystyle r \ leftarrow r ^ {2} \, (= x ^ {2})}

; бит 2 = 1, поэтому вычисляем

r ← r ⋅ x (= x 3) {\ displaystyle r \ leftarrow r \ cdot x \, (= x ^ {3})}

{\ displaystyle r \ leftarrow r \ cdot x \, (= x ^ {3})}

;

Шаг 3)

r ← r 2 (= x 6) {\ displaystyle r \ leftarrow r ^ {2} \, (= x ^ {6})}

{\ displaystyle r \ leftarrow r ^ {2} \, (= x ^ {6})}

; бит 3 = 0, поэтому мы закончили этот шаг (эквивалентно, это соответствует

r ← r ⋅ x 0 (= x 6) {\ displaystyle r \ leftarrow r \ cdot x ^ {0} \, (= x ^ {6})}

{\ displaystyle r \ leftarrow r \ cdot x ^ {0} \, (= x ^ {6})}

);

Шаг 4)

r ← r 2 (= x 12) {\ displaystyle r \ leftarrow r ^ {2} \, (= x ^ {12})}

{\ displaystyle r \ leftarrow r ^ {2} \, (= x ^ {12})}

; бит 4 = 1, поэтому вычисляем

r ← r ⋅ x (= x 13) {\ displaystyle r \ leftarrow r \ cdot x \, (= x ^ {13})}

{\ displaystyle r \ leftarrow r \ cdot x \, (= x ^ {13})}

Если мы напишем $n {\ displaystyle n}$ $n$ в двоичном формате как $bk ⋯ b 0 {\ displaystyle b_ {k} \ cdots b_ {0}}$ ${\ displaystyle b_ {k} \ cdots b_ {0}}$ , то это эквивалентно определению последовательность $rk + 1,…, r 0 {\ displaystyle r_ {k + 1}, \ ldots, r_ {0}}$ ${\ displaystyle r_ {k + 1}, \ ldots, r_ {0}}$ , позволяя $rk + 1 = 1 {\ displaystyle r_ {k + 1} = 1}$ ${\ displaystyle r_ {k + 1} = 1}$ , а затем определение $ri = ri + 1 2 xbi {\ displaystyle r_ {i} = r_ {i + 1} ^ {2} x ^ {b_ { i}}}$ ${\ displaystyle r_ {i} = r_ {i + 1} ^ {2} x ^ {b_ {i}}}$ для $i = k,…, 0 {\ displaystyle i = k, \ ldots, 0}$ ${\ displaystyle i = k, \ ldots, 0}$ , где $r 0 {\ displaystyle r_ {0}}$ $r_ { 0}$ будет равно $xn {\ displaystyle x ^ {n}}$ $x ^ {n}$ .

Это может быть реализовано как следующий рекурсивный алгоритм :

Функция exp_by_squaring (x, n) if n < 0 then return exp_by_squaring(1 / x, -n); else if n = 0 then return 1; else if n = 1 then return x ; else if n is even then return exp_by_squaring(x * x, n / 2); else if n is odd then return x * exp_by_squaring(x * x, (n - 1) / 2);

Хотя это и не хвостовая рекурсия, этот алгоритм можно переписать в хвостовой рекурсивный алгоритм путем введения вспомогательной функции:

Функция exp_by_squaring (x, n) return exp_by_squaring2 (1, x, n) Функция exp_by_squaring2 (y, x, n) if n < 0 then return exp_by_squaring2(y, 1 / x, - n); else if n = 0 then return y; else if n = 1 then return x * y; else if n is even then return exp_by_squaring2(y, x * x, n / 2); else if n is odd then return exp_by_squaring2(x * y, x * x, (n - 1) / 2).

A хвостовой рекурсивный вариант также может быть построен с использованием пары аккумуляторов вместо вспомогательной функции, как показано в примере F # ниже. Аккумуляторы a1 и a2 можно рассматривать как хранящие значения $xi {\ displaystyle x ^ {i}}$ $x ^ {i}$ и $xj {\ displaystyle x ^ {j}}$ $x ^ {j}$ , где i и j инициализируются значениями 1 и 0 соответственно. В четном случае i удваивается, а в нечетном случае j увеличивается на i. Конечный результат: $xi + j {\ displaystyle x ^ {i + j}}$ ${\ displaystyle x ^ {i + j}}$ где $i + j = n {\ displaystyle i + j = n}$ ${\ displaystyle i + j = n}$ .

let exp_by_squaring xn = let rec _exp xn 'a1 a2 = if n' = 0 then 1 elif n '= 1 then a1 * a2 elif n'% 2 = 0 then _exp x (n '/ 2) (a1 * a1) a2 else _exp x (n'-1) a1 (a1 * a2) _exp xnx 1

Итерационная версия алгоритма также использует ограниченное вспомогательное пространство и задается

функцией exp_by_squaring_iterative (x, n), если n < 0 then x := 1 / x; n := -n; if n = 0 then return 1 y := 1; while n>1 сделать, если n четно, то x: = x * x; n: = n / 2; иначе y: = x * y; х: = х * х; п: = (п - 1) / 2; return x * y

Вычислительная сложность

Краткий анализ показывает, что такой алгоритм использует $⌊ log 2 ⁡ n ⌋ {\ displaystyle \ lfloor \ log _ {2} n \ rfloor}$ $\ lfloor \ log _ {2} n \ rfloor$ квадраты и самое большее $⌊ log 2 ⁡ n ⌋ {\ displaystyle \ lfloor \ log _ {2} n \ rfloor}$ $\ lfloor \ log _ {2} n \ rfloor$ умножения, где $⌊ ⌋ {\ displaystyle \ lfloor \; \ rfloor}$ $\ lfloor \; \ rfloor$ обозначает функцию пола. Точнее, количество умножений на единицу меньше количества единиц, представленных в двоичном расширении числа n. Для n больше примерно 4 это более эффективно с вычислительной точки зрения, чем наивное многократное умножение основания на себя.

Каждое возведение в квадрат приводит примерно к удвоению количества цифр по сравнению с предыдущим, и поэтому, если умножение двух d-значных чисел реализовано за O (d) операций для некоторого фиксированного k, то сложность вычисления x задается формулой

∑ i = 0 O (log ⁡ n) (2 i O (log ⁡ x)) k = O ((n log ⁡ x) k). {\ displaystyle \ sum \ limits _ {i = 0} ^ {O (\ log n)} {\ big (} 2 ^ {i} O (\ log x) {\ big)} ^ {k} = O { \ big (} (n \ log x) ^ {k} {\ big)}.}

{\ displaystyle \ sum \ limits _ {i = 0} ^ {O (\ log n)} {\ big (} 2 ^ {i} O (\ log x) {\ big)} ^ {k} = O {\ big (} (n \ log x) ^ {k } {\ big)}.}

2-мерный метод

Этот алгоритм вычисляет значение x после раскрытия экспоненты по основанию 2. Это был впервые предложен Брауэром в 1939 году. В приведенном ниже алгоритме мы используем следующую функцию f (0) = (k, 0) и f (m) = (s, u), где m = u · 2 с нечетным u.

Алгоритм:

Вход: Элемент x из G, параметр k>0, неотрицательное целое число n = (n l − 1, n l − 2,..., n 0)2и предварительно вычисленные значения $x 3, x 5,..., x 2 k - 1 {\ displaystyle x ^ {3}, x ^ {5},..., x ^ {2 ^ {k} -1}}$ $x ^ {3}, x ^ {5},..., x ^ {2 ^ {k} -1}$ .

Выход: Элемент x в G

y: = 1; i: = l - 1 пока i ≥ 0 do (s, u): = f (n i) for j: = 1 to k - s do y : = yy: = y * x для j: = 1 tos doy: = yi: = i - 1 return y

Для оптимальной эффективности k должно быть наименьшим целым числом, удовлетворяющим

log ⁡ n < k ( k + 1) ⋅ 2 2 k 2 k + 1 − k − 2 + 1. {\displaystyle \log n<{\frac {k(k+1)\cdot 2^{2k}}{2^{k+1}-k-2}}+1.}

{\ displaystyle \ log n <{\ frac {k (k + 1) \ cdot 2 ^ {2k}} {2 ^ {k + 1} -k-2 }} + 1.}

Метод скользящего окна

Этот метод представляет собой эффективный вариант 2-мерного метода. Например, для вычисления степени 398, которая имеет двоичное расширение (110 001 110) 2, мы берем окно длиной 3, используя алгоритм 2-го метода, и вычисляем 1, x, x, x, x, x, x, x, x, x, x, x. Но мы может также вычислить 1, x, x, x, x, x, x, x, x, x, x, что экономит одно умножение и составляет оценку (110 001 110) 2

Вот общий алгоритм:

Алгоритм:

Вход: Элемент x из G, неотрицательное целое число n = (n l − 1, n l − 2,..., n 0)2, параметр k>0 и предварительно вычисленные значения $x 3, x 5,..., x 2 k - 1 {\ displaystyle x ^ {3}, x ^ {5},..., x ^ {2 ^ {k} -1}}$ $x ^ {3}, x ^ {5},..., x ^ {2 ^ {k} -1}$ .

Output: Элемент x ∈ G.

Алгоритм:

y: = 1; i: = l - 1 в то время как i>-1 doifni= 0 тогда y: = y 'i: = i - 1 else s: = max {i - k + 1, 0} пока ns= 0 do s: = s + 1 for h: = 1 to i - s + 1 do y: = yu: = (n i, n i-1,..., n s)2y: = y * xi: = s - 1 return y

лестничная техника Монтгомери

Многие алгоритмы возведения в степень не обеспечивают защиту от атак по побочным каналам. А именно, злоумышленник, наблюдающий Последовательность квадратов и умножений может (частично) восстановить экспоненту, участвующую в вычислении. Это проблема, если показатель степени должен оставаться в секрете, как и во многих криптосистемах с открытым ключом. Метод, называемый "Монтгомери" лестничная диаграмма "решает эту проблему.

Учитывая двоичное расширение положительного ненулевого целого числа n = (n k − 1... n 0)2с n k − 1 = 1, мы можем вычислить x следующим образом:

x1= x; x 2 = x для i = k - от 2 до 0 doIfni= 0, затем x2= x 1 * x 2 ; x 1 = x 1else x1= x 1 * x 2 ; x 2 = x 2return x1

Алгоритм выполняет фиксированную последовательность операций (от до log n): умножение и возведение в квадрат имеют место для каждого бита в экспоненте независимо от конкретного значения бита. Аналогичный алгоритм умножения на удвоение существует.

Эта конкретная реализация лестницы Монтгомери еще не защищена от кеш-атак тайминговых атак : злоумышленник может по-прежнему наблюдать задержки доступа к памяти, поскольку доступ к различным переменным зависит от значения битов секретный показатель. Современные криптографические реализации используют технику «разброса», чтобы гарантировать, что процессор всегда пропускает более быстрый кэш.

Показатель с фиксированной базой

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

Метод Яо

Метод Яо ортогонален двумерному методу, в котором показатель степени раскрывается по основанию b = 2, а вычисления выполняются в соответствии с приведенным выше алгоритмом. Пусть n, n i, b и b i являются целыми числами.

Пусть показатель степени n записывается как

n = ∑ i = 0 w - 1 ниби, {\ displaystyle n = \ sum _ {i = 0} ^ {w-1} n_ {i} b_ {i},}

{\ displaystyle n = \ sum _ {i = 0} ^ {w- 1} n_ {i} b_ {i},}

где $0 ⩽ ni < h {\displaystyle 0\leqslant n_{i}$ ${\ displaystyle 0 \ leqslant n_ {i} <h}$ для всех $i ∈ [0, w - 1] {\ displaystyle i \ in [0, w-1]}$ ${\ displaystyle i \ in [0, w-1]}$ .

Пусть x i = x.

Тогда алгоритм использует равенство

x n = ∏ i = 0 w - 1 x i n i = ∏ j = 1 h - 1 [∏ n i = j x i] j. {\ displaystyle x ^ {n} = \ prod _ {i = 0} ^ {w-1} x_ {i} ^ {n_ {i}} = \ prod _ {j = 1} ^ {h-1} { \ bigg [} \ prod _ {n_ {i} = j} x_ {i} {\ bigg]} ^ {j}.}

{\ displaystyle x ^ {n} = \ prod _ {i = 0} ^ {w-1} x_ {i} ^ {n_ {i}} = \ prod _ {j = 1 } ^ {h-1} {\ bigg [} \ prod _ {n_ {i} = j} x_ {i} {\ bigg]} ^ {j}.}

Учитывая элемент x группы G и показатель степени n, записанный в приведенной выше форме, Наряду с предварительно вычисленными значениями x... x элемент x вычисляется с использованием следующего алгоритма:

y = 1, u = 1, j = h - 1 пока j>0 doдля i = 0 от до w - 1 doifni= j затем u = u × xy = y × uj = j - 1 return y

Если мы установим h = 2 и b i = h, тогда значения n i будут просто цифрами n в базе h. Метод Яо собирает в u сначала те x i, которые появляются в наибольшей степени $h - 1 {\ displaystyle h-1}$ ${\ displaystyle h-1}$ ; в следующем раунде те, у кого мощность $h - 2 {\ displaystyle h-2}$ ${\ displaystyle h-2}$ , также собираются в u и т. д. Переменная y умножается на $h - 1 {\ displaystyle h- 1}$ ${\ displaystyle h-1}$ раз с начальным u, $h - 2 {\ displaystyle h-2}$ ${\ displaystyle h-2}$ раз со следующими наибольшими степенями и так далее. Алгоритм использует $w + h - 2 {\ displaystyle w + h-2}$ ${ \ displaystyle w + h-2}$ умножения, и $w + 1 {\ displaystyle w + 1}$ ${\ displaystyle w + 1}$ элементы должны быть сохраненным для вычисления x.

Евклидов метод

Евклидов метод был впервые представлен в Эффективном возведении в степень с использованием предварительных вычислений и цепочек сложения векторов PD Rooij.

Этот метод вычисления $xn {\ displaystyle x ^ {n}}$ $x ^ {n}$ в группе G, где n - натуральное целое число, алгоритм которого указан ниже рекурсивно используется следующее равенство:

x 0 n 0 ⋅ x 1 n 1 = (x 0 ⋅ x 1 q) n 0 ⋅ x 1 n 1 mod n 0, {\ displaystyle x_ {0} ^ { n_ {0}} \ cdot x_ {1} ^ {n_ {1}} = \ left (x_ {0} \ cdot x_ {1} ^ {q} \ right) ^ {n_ {0}} \ cdot x_ { 1} ^ {n_ {1} \ mod n_ {0}},}

{\ displaystyle x_ {0} ^ {n_ {0}} \ cdot x_ {1} ^ {n_ {1}} = \ left (x_ {0} \ cdot x_ {1} ^ {q} \ right) ^ {n_ {0}} \ cdot x_ {1} ^ {n_ {1} \ mod n_ {0}},}

где $q = ⌊ n 1 n 0 ⌋ {\ displaystyle q = \ left \ lfloor {\ frac {n_ {1}} {n_ {0}}} \ right \ rfloor}$ ${\ displaystyle q = \ left \ lfloor {\ frac {n_ {1}} {n_ {0}}} \ right \ rfloor}$ . Другими словами, евклидово деление экспоненты n 1 на n 0 используется для возврата частного q и остатка n 1 mod n 0.

Учитывая базовый элемент x в группе G и показатель степени $n {\ displaystyle n}$ $n$ , записанный, как в методе Яо, элемент $xn {\ displaystyle x ^ {n}}$ $x ^ {n}$ вычисляется с использованием $l {\ displaystyle l}$ $l$ предварительно вычисленных значений $xb 0,..., x b l i {\ displaystyle x ^ {b_ {0}},..., x ^ {b_ {l_ {i}}}}$ $x ^ {b_ {0}},..., x ^ {b_ {l_ {i}}}$ , а затем алгоритм ниже.

Начать цикл Найти  $M ∈ [0, l - 1] {\ displaystyle M \ in [0, l-1]}$  ${\ displaystyle M \ in [0, l-1]}$ , такое, что  $∀ i ∈ [0, l - 1], n M ≥ ni {\ displaystyle \ forall i \ in [0, l-1], n_ {M} \ geq n_ {i}}$  ${\ displaystyle \ forall i \ в [0, l-1], n_ {M} \ geq n_ {i}}$ . Найдите  $N ∈ ([0, l - 1] - M) {\ displaystyle N \ in {\ big (} [0, l-1] -M {\ big)}}$  ${\ displaystyle N \ in {\ big (} [0, l-1] -M {\ big)}}$ , такие, что  $∀ я ∈ ([0, l - 1] - M), n N ≥ ni {\ displaystyle \ forall i \ in {\ big (} [0, l-1] -M {\ big) }, n_ {N} \ geq n_ {i}}$  ${\ displaystyle \ forall i \ in {\ big (} [0, l-1] -M {\ big)}, n_ {N} \ geq n_ {i}}$ . Разрыв цикла, если  $n N = 0 {\ displaystyle n_ {N} = 0}$  ${\ displaystyle n_ {N} = 0}$ . Позвольте $q Знак равно ⌊ N M / n N ⌋ {\ displaystyle q = \ lfloor n_ {M} / n_ {N} \ rfloor}$  ${\ displaystyle q = \ lfloor n_ {M} / n_ {N} \ rfloor}$ , а затем пусть $n N = ( n M mod n N) {\ displaystyle n_ {N} = (n_ {M} {\ bmod {n}} _ {N})}$  ${\ displaystyle n_ {N} = (n_ {M} {\ bmod {n}} _ {N})}$ . Вычислить рекурсивно  $x M q {\ displaystyle x_ {M} ^ {q}}$  ${\ displaystyle x_ {M} ^ {q}}$ , а затем let $x N = x N ⋅ x M q {\ displaystyle x_ {N} = x_ {N} \ cdot x_ {M} ^ {q}}$  ${\ displaystyle x_ {N} = x_ {N} \ cdot x_ {M} ^ {q}}$ . Конечный цикл ; Возврат $xn = x M n M {\ displaystyle x ^ {n} = x_ {M} ^ {n_ {M}}}$  ${\ displaystyle x ^ {n} = x_ {M} ^ {n_ {M}}}$ .

Сначала алгоритм находит наибольшее значение среди n i, а затем супремум в наборе {n i \ i ≠ M}. Затем он возводит x M в степень q, умножает это значение на x N, а затем присваивает x N результат этого вычисления и n M значение n M по модулю n N.

Другие приложения

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

Power (x, −n) = (Power (x, n)).

Метод работает во всех полугруппа и часто используется для вычисления мощностей матриц.

. Например, оценка

13789 (mod 2345) = 2029

потребует очень много времени и много памяти. пробел, если использовался наивный метод: вычислите 13789, затем возьмите остаток при делении на 2345. Даже использование более эффективного метода займет много времени: возведите 13789 в квадрат, возьмите остаток при делении на 2345, умножьте результат на 13789 и так далее. Это займет менее $2 log 2 ⁡ (722340) ≤ 40 {\ displaystyle 2 \ log _ {2} (722340) \ leq 40}$ ${\ displaystyle 2 \ log _ {2} (722340) \ leq 40}$ модульных умножений.

Применение вышеуказанного алгоритма возведения в квадрат с "*", интерпретируемым как x * y = xy mod 2345 (то есть умножение с последующим делением на остаток) приводит только к 27 умножениям и делениям целых чисел., которые все могут храниться в одном машинном слове.

Примеры реализации

Вычисление по степеням 2

Это нерекурсивная реализация вышеуказанного алгоритма в Ruby.

n = n - 1является избыточным, когда n = n / 2неявно округляется до нуля, как это сделали бы строго типизированные языки с целочисленным делением. (n = n>>1 имеет тот же эффект.) n [0]- крайний правый бит двоичного представления n, поэтому если он равен 1, то число нечетное, а если оно равно нулю, то число четное. Это также nпо модулю 2. (n 1 имеет тот же эффект.)

def power (x, n) result = 1, а n.nonzero? если n [0]. ненулевое? результат * = xn - = 1 end x * = xn / = 2 end return result end

Пример выполнения: вычисление 3

параметр x = 3 параметр n = 10 результат: = 1 Итерация 1 n = 10 ->n четно x: = x = 3 = 9 n: = n / 2 = 5 Итерация 2 n = 5 ->n нечетно ->результат: = результат * x = 1 * x = 1 * 3 = 9 n: = n - 1 = 4 x: = x = 9 = 3 = 81 n: = n / 2 = 2 Итерация 3 n = 2 ->n четно x: = x = 81 = 3 = 6561 n: = n / 2 = 1 Итерация 4 n = 1 ->n нечетно ->результат: = результат * x = 3 * 3 = 3 = 9 * 6561 = 59049 n: = n - 1 = 0 вернуть результат

Пример выполнения: вычислить 3

результат: = 3 bin: = "1010" Итерация для цифры 4: результат: = результат = 3 = 9 101 0bin - цифра равна «0» Итерация для цифры 3: результат: = результат = (3) = 3 = 81 10 10bin - цифра равна «1» ->результат: = результат * 3 = (3) * 3 = 3 = 243 Итерация для цифры 2: результат: = результат = ( (3) * 3) = 3 = 59049 1 010bin - цифра равна «0», возвращаемый результат

Этот пример основан на алгоритм выше. При ручном расчете следует идти слева направо. Если начальный номер равен 1, просто игнорируйте его. Затем, если следующий - один, возведите в квадрат и умножьте. Если следующий - ноль, только квадрат.

Вычисление произведений степеней

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

Пример

Формула a × b может быть вычислена за 3 шага:

((a) × a) × a (4 умножения для вычисления a),

((b)) × b (3 умножения для вычисления b),

(a) × (b) (1 умножение для вычисления произведения двух),

, чтобы получить 8 умножений в общее.

Более быстрое решение - вычислить обе мощности одновременно:

((a × b) × a) × a × b,

для чего требуется всего 6 умножений. Обратите внимание, что a × b вычисляется дважды; результат может быть сохранен после первого вычисления, что уменьшает количество умножений до 5.

Пример с числами:

2 × 3 = ((2 × 3) × 2) × 2 × 3 = (6 × 2) × 6 = 72 × 6 = 31104.

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

Использование преобразования

Приведенный выше пример a × b также может быть вычислен только с 5 умножениями, если выражение преобразовано перед вычислением:

a × b = a × (ab), с ab: = a × b,

ab: = a × b (1 умножение),

a × (ab) = ((ab) × a) × ab (4 умножения).

Обобщение преобразования показывает следующую схему:

Для вычисления a × b ×... × m × n

Определите ab: = a × b, abc = ab × c,...
Вычислить преобразованное выражение a × ab ×... × abc..m × abc..mn.

Преобразование перед вычислением часто уменьшает количество умножений, но в некоторых случаях оно также увеличивает количество (см. последний из примеров ниже), поэтому может быть хорошей идеей проверить количество умножений, прежде чем использовать преобразованное выражение для расчета.

Примеры

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

Пример	a×b×c	a×b×c	a × b × c
отдельные	[(( a) × a) × a] × [((b)) × b] × [(c) × c]. (11умножения)	[((a)) × a] × [(( b)) × b] × [(c) × c]. (10умножения)	[((a) × a) × a] × [((b))] × [c]. (8умножения)
одновременное	((a × b) × a × c) × a × b × c. (8умножения)	((a × b) × c) × a × b × c. (7умножения)	((a × b) × a) × a × c. (6умножения)
преобразование	a: = a ab : = a × b abc: = ab × c. (2 умножения)	a: = a ab: = a × b abc: = ab × c. (2 умножения)	a: = a ab: = a × b abc: = ab × c. (2 умножения)
вычисление после этого	(a × ab × abc) × abc. (Всего 4 умножения ⇒ 6 )	(ab × abc) × abc. (всего 3 умножения ⇒ 5 )	(a × ab) × a × ab × abc. (всего 5 умножений ⇒ 7 )

Перекодирование знаковых цифр

В некоторых вычислениях может быть более эффективным разрешить отрицательные коэффициенты и, следовательно, использовать th Обратное к основанию, при условии, что инверсия в G является «быстрой» или была предварительно вычислена. Например, при вычислении x двоичный метод требует умножения k − 1 и возведения в квадрат k − 1. Однако можно выполнить k квадратов, чтобы получить x, а затем умножить на x, чтобы получить x.

С этой целью мы определяем представление цифр со знаком целого числа n в системе счисления b как

n = ∑ i = 0 l - 1 n i b i с | н я | < b. {\displaystyle n=\sum _{i=0}^{l-1}n_{i}b^{i}{\text{ with }}|n_{i}|

{ \ displaystyle n = \ sum _ {i = 0} ^ {l-1} n_ {i} b ^ {i} {\ text {with}} | n_ {i} | <b.}

Знаковое двоичное представление соответствует конкретному выбору b = 2 и $ni ∈ {- 1, 0, 1} {\ displaystyle n_ {i} \ in \ {- 1,0,1 \}}$ ${\ displaystyle n_ {i} \ in \ {- 1,0,1 \}}$ . Он обозначается $(n l - 1… n 0) s {\ displaystyle (n_ {l-1} \ dots n_ {0}) _ {s}}$ ${\ displaystyle ( п_ {l-1} \ точки n_ {0}) _ {s}}$ . Есть несколько методов вычисления этого представления. Представление не уникальное. Например, возьмем n = 478: два различных знаковых двоичных представления задаются как $(10 1 ¯ 1100 1 ¯ 10) s {\ displaystyle (10 {\ bar {1}} 1100 {\ bar {1}}) 10) _ {s}}$ $(10 {\ bar {1}} 1100 {\ bar {1}} 10) _ {s}$ и $(100 1 ¯ 1000 1 ¯ 0) s {\ displaystyle (100 {\ bar {1}} 1000 {\ bar {1}} 0) _ {s}}$ $(100 {\ bar {1}} 1000 { \ bar {1}} 0) _ {s}$ , где $1 ¯ {\ displaystyle {\ bar {1}}}$ ${\ bar {1}}$ используется для обозначения −1. Поскольку двоичный метод вычисляет умножение для каждой ненулевой записи в представлении n с основанием 2, мы заинтересованы в нахождении знаково-двоичного представления с наименьшим числом ненулевых записей, то есть с минимальным Вес Хэмминга. Один из способов сделать это - вычислить представление в несмежной форме или сокращенно NAF, которая удовлетворяет $nini + 1 = 0 для всех i ⩾ 0 {\ displaystyle n_ { i} n_ {i + 1} = 0 {\ text {для всех}} i \ geqslant 0}$ ${ \ displaystyle n_ {i} n_ {i + 1} = 0 {\ text {для всех}} i \ geqslant 0}$ и обозначается $(nl - 1… n 0) NAF {\ displaystyle (n_ { l-1} \ dots n_ {0}) _ {\ text {NAF}}}$ ${\ displaystyle (n_ {l-1} \ dots n_) {0}) _ {\ text {NAF}}}$ . Например, представление NAF для 478: $(1000 1 ¯ 000 1 ¯ 0) NAF {\ displaystyle (1000 {\ bar {1}} 000 {\ bar {1}} 0) _ {\ text {NAF }}}$ ${\ displaystyle (1000 {\ bar {1}} 000 {\ bar {1}} 0) _ {\ text {NAF}}}$ . Это представление всегда имеет минимальный вес Хэмминга. Простой алгоритм вычисления NAF-представления заданного целого числа $n = (nlnl - 1… n 0) 2 {\ displaystyle n = (n_ {l} n_ {l-1} \ dots n_ {0}) _ {2}}$ ${\ displaystyle n = (n_ {l} n_ {l-1} \ dots n_ {0}) _ {2}}$ с $nl = nl - 1 = 0 {\ displaystyle n_ {l} = n_ {l-1} = 0}$ ${\ displaystyle n_ {l} = n_ {l-1} = 0}$ выглядит следующим образом:

 $c 0 = 0 {\ displaystyle c_ {0} = 0}$  $c_ {0} = 0$ для i = от 0 до l - 1 do  $ci + 1 = ⌊ 1 2 (ci + ni + ni + 1) ⌋ {\ Displaystyle c_ {я + 1} = \ left \ lfloor {\ frac {1} {2}} (c_ {i} + n_ {i} + n_ {i + 1}) \ right \ rfloor}$  ${\ displaystyle c_ {i + 1} = \ left \ lfloor {\ frac {1} {2}} (c_ {i} + n_ {i} + n_ {i + 1}) \ right \ rfloor}$  $ni ′ = ci + ni - 2 ci + 1 {\ displaystyle n_ {i} '= c_ {i} + n_ {i} -2c_ {i + 1}}$  $n_{i}'=c_{i}+n_{i}-2c_{i+1}$ return  $(nl - 1 ′… n 0 ′) NAF {\ displaystyle (n_ {l-1} '\ dots n_ {0}') _ {\ text {NAF}}}$  $(n_{l-1}'\dots n_{0}')_{\text{NAF}}$

Другой алгоритм Коямы и Цуруока не требует условия что $ni = ni + 1 = 0 {\ displaystyle n_ {i} = n_ {i + 1} = 0}$ ${\ displaystyle п_ {я} = п_ {я + 1} = 0}$ ; он по-прежнему минимизирует вес Хэмминга.

Альтернативы и обобщения

Возведение в степень посредством возведения в квадрат можно рассматривать как субоптимальный алгоритм возведения в степень цепочки сложения : он вычисляет показатель степени с помощью цепочки сложения состоящий из повторяющихся удвоений показателя степени (возведения в квадрат) и / или увеличения показателя степени только на единицу (умножение на x). В более общем плане, если можно суммировать любые ранее вычисленные показатели степени (путем умножения этих степеней x), можно иногда выполнить возведение в степень, используя меньшее количество умножений (но обычно с использованием большего объема памяти). Наименьшая степень, где это происходит, имеет место для n = 15:

x 15 = x × (x × [x × x 2] 2) 2 {\ displaystyle x ^ {15} = x \ times (x \ times [x \ times x ^ {2}] ^ {2}) ^ {2}}

{\ displaystyle x ^ { 15} = х \ раз (х \ раз [х \ раз х ^ {2}] ^ {2}) ^ {2}}

(возведение в квадрат, 6 умножений),

x 15 = x 3 × ([x 3] 2) 2 {\ displaystyle x ^ {15} = x ^ {3} \ times ([x ^ {3}] ^ {2}) ^ {2}}

{\ displaystyle x ^ {15} = x ^ {3} \ times ([x ^ {3}] ^ {2}) ^ {2}}

(оптимальная цепочка сложения, 5 умножается, если x повторно-

В общем, поиск оптимальной цепочки сложения для заданного показателя степени является сложной задачей, для которой не известны эффективные алгоритмы, поэтому оптимальные цепочки обычно используются только для малых показателей (например, в компиляторах где цепочки для малых мощностей были предварительно сведены в таблицу). Однако существует ряд эвристических алгоритмов , которые, хотя и не являются оптимальными, имеют меньшее количество умножений, чем возведение в степень возведением в квадрат за счет дополнительной бухгалтерской работы и использования памяти. Тем не менее, количество умножений никогда не растет медленнее, чем Θ (log n), поэтому эти алгоритмы улучшаются только асимптотически при возведении в степень путем возведения в квадрат в лучшем случае постоянного множителя.

См. Также

Примечания

Ссылки