Цепочка сложения-вычитания

Цепочка сложения-вычитания , обобщение цепочек сложения , включающее вычитание, представляет собой последовательность a ₀ , a ₁ , a ₂ , a ₃ , ... которая удовлетворяет

$a_{0}=1,\,$

${\text{for }}k>0,\ a_{k}=a_{i}\pm a_{j}{\text{ for some }}0\leq i,j<k.$

Цепочка сложения-вычитания для n длины L — это цепочка сложения-вычитания такая, что $a_{L}=n$. То есть, таким образом, можно вычислить n с помощью L сложений и/или вычитаний. (Обратите внимание, что n не обязательно должно быть положительным. В этом случае можно также включить a _-1 в последовательность = 0, так что n = -1 можно получить с помощью цепочки длины 1.)

По определению, каждая цепочка сложения является также цепочкой сложения-вычитания, но не наоборот. Следовательно, длина кратчайшей цепочки сложения-вычитания для n ограничена сверху длиной самой короткой цепочки сложения для n . Однако в целом определение минимальной цепочки сложения-вычитания (как и задача определения минимальной цепочки сложения) представляет собой сложную задачу, для которой в настоящее время не известны эффективные алгоритмы. Связанная с этим проблема поиска оптимальной последовательности сложения является NP-полной (Downey et al., 1981), но неизвестно наверняка, является ли нахождение оптимальных цепочек сложения или сложения-вычитания NP-трудным .

Например, одна цепочка сложения-вычитания: $a_{0}=1$, $a_{1}=2=1+1$, $a_{2}=4=2+2$, $a_{3}=3=4-1$. Однако это не минимальная цепочка сложения-вычитания для n = 3, поскольку вместо этого мы могли бы выбрать $a_{2}=3=2+1$. Наименьшее n, для которого цепочка сложения-вычитания короче минимальной цепочки сложения, составляет n = 31, что можно вычислить только за 6 сложений (а не за 7 для минимальной цепочки сложения):

$a_{0}=1,\ a_{1}=2=1+1,\ a_{2}=4=2+2,\ a_{3}=8=4+4,\ a_{4}=16=8+8,\ a_{5}=32=16+16,\ a_{6}=31=32-1.$

Как и цепочка сложения, цепочка сложения-вычитания может использоваться для возведения в степень цепочки сложения : учитывая цепочку сложения-вычитания длины L для n , степень $x^{n}$ можно вычислить путем умножения или деления на x L раз, где вычитания соответствуют делениям. Это потенциально эффективно в задачах, где деление является недорогой операцией, особенно при возведении в степень эллиптических кривых , где деление соответствует простой смене знака (как предложили Морейн и Оливос, 1990).

Некоторые аппаратные множители умножаются на n, используя цепочку сложения, описываемую n в двоичном формате:

n = 31 = 0  0  0  1   1  1  1  1 (binary).

Другие аппаратные множители умножаются на n, используя цепочку сложения-вычитания, описанную n в кодировке Бута :

n = 31 = 0  0  1  0   0  0  0 −1 (Booth encoding).

Ссылки

• Волгер, Хьюго (8 апреля 1985 г.). «Некоторые результаты о цепочках сложения и вычитания». Письма об обработке информации . 20 (3): 155–160. дои : 10.1016/0020-0190(85)90085-7 .
• Морен, Франсуа; Оливос, Хорхе (1990). «Ускорение вычислений на эллиптической кривой с помощью цепочек сложения-вычитания» (PDF) . Теоретическая информатика и приложения . 24 (6): 531–543. CiteSeerX   10.1.1.56.347 .
• Дауни, Питер Дж.; Леонг, Бентон Л.; Сетхи, Рави (1981). «Вычисление последовательностей с цепочками сложения». СИАМ Дж. Компьютер. 10 (3): 638–646. дои : 10.1137/0210047 .
• Слоан, Нью-Джерси (ред.). «Последовательность A128998 (длина минимальной цепочки сложения-вычитания)» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.