Cadena de suma y resta

Una cadena de suma-resta , una generalización de las cadenas de suma para incluir la resta, es una secuencia a ₀ , a ₁ , a ₂ , a ₃ , ... que satisface

${\displaystyle a_{0}=1,\,}$

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

Una cadena de suma-resta para n , de longitud L , es una cadena de suma-resta tal que . Es decir, se puede calcular n mediante L sumas y/o restas. (Tenga en cuenta que n no necesita ser positivo. En este caso, también se puede incluir un ₋₁ = 0 en la secuencia, de modo que se pueda obtener n = −1 mediante una cadena de longitud 1). ${\displaystyle a_{L}=n}$

Por definición, cada cadena de adición es también una cadena de adición-sustracción, pero no al revés. Por lo tanto, la longitud de la cadena de adición-sustracción más corta para n está limitada por encima de la longitud de la cadena de adición más corta para n . Sin embargo, en general, la determinación de una cadena de adición-sustracción mínima (como el problema de determinar una cadena de adición mínima) es un problema difícil para el que actualmente no se conocen algoritmos eficientes. El problema relacionado de encontrar una secuencia de adición óptima es NP-completo (Downey et al., 1981), pero no se sabe con certeza si encontrar cadenas de adición o de adición-sustracción óptimas es NP-difícil .

Por ejemplo, una cadena de suma-resta es: , , , . Sin embargo, esta no es una cadena de suma-resta mínima para n = 3, porque podríamos haber elegido . El n más pequeño para el cual una cadena de suma-resta es más corta que la cadena de adición mínima es n = 31, que se puede calcular en solo 6 sumas (en lugar de 7 para la cadena de adición mínima): ${\displaystyle a_{0}=1}$ ${\displaystyle a_{1}=2=1+1}$ ${\displaystyle a_{2}=4=2+2}$ ${\displaystyle a_{3}=3=4-1}$ ${\displaystyle a_{2}=3=2+1}$

${\displaystyle 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.}$

Al igual que una cadena de adición, una cadena de adición-resta se puede utilizar para la exponenciación de cadena de adición : dada la cadena de adición-resta de longitud L para n , la potencia se puede calcular multiplicando o dividiendo por x L veces, donde las restas corresponden a las divisiones. Esto es potencialmente eficiente en problemas donde la división es una operación barata, más notablemente para la exponenciación en curvas elípticas donde la división corresponde a un mero cambio de signo (como propusieron Morain y Olivos, 1990). ${\displaystyle x^{n}}$

Algunos multiplicadores de hardware multiplican por n utilizando una cadena de adición descrita por n en binario:

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

Otros multiplicadores de hardware multiplican por n utilizando una cadena de suma-resta descrita por n en la codificación de Booth :

n = 31 = 0 0 1 0 0 0 0 −1 (codificación de Booth).

Referencias

• Volger, Hugo (8 de abril de 1985). "Algunos resultados sobre cadenas de adición/sustracción". Information Processing Letters . 20 (3): 155–160. doi :10.1016/0020-0190(85)90085-7.
• Morain, François; Olivos, Jorge (1990). "Acelerar los cálculos en una curva elíptica mediante cadenas de suma y resta" (PDF) . Informática teórica y aplicaciones . 24 (6): 531–543. CiteSeerX  10.1.1.56.347 .
• Downey, Peter J.; Leong, Benton L.; Sethi, Ravi (1981). "Cálculo de secuencias con cadenas de adición". SIAM J. Comput. 10 (3): 638–646. doi :10.1137/0210047.
• Sloane, N. J. A. (ed.). "Secuencia A128998 (longitud de la cadena mínima de adición-sustracción)". La enciclopedia en línea de secuencias de números enteros . Fundación OEIS.