Řetězec sčítání a odčítání - Addition-subtraction chain

An řetěz sčítání a odčítání, zobecnění adiční řetězce zahrnout odčítání, je a sekvence A₀, A₁, A₂, A₃, ... to uspokojuje

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

${displaystyle {ext {for}} k> 0, a_ {k} = a_ {i} pm a_ {j} {ext {pro některé}} 0 leq i, j$

Řetězec sčítání a odčítání pro n, délky L, je řetězec sčítání a odčítání takový, že ${displaystyle a_ {L} = n}$. To znamená, že tím lze počítat n podle L sčítání a / nebo odčítání. (Všimněte si, že n nemusí být pozitivní. V tomto případě lze také zahrnout A₋₁ = 0 v pořadí, takže n = -1 lze získat řetězcem délky 1.)

Podle definice je každý sčítací řetězec také řetězcem sčítání a odčítání, ale ne naopak. Proto je délka nejkratší řetěz sčítání a odčítání pro n je omezen výše délkou nejkratšího řetězce přidání pro n. Obecně je však stanovení řetězce minimálního sčítání a odčítání (jako problém stanovení řetězce minimálního sčítání) obtížným problémem, pro který nejsou v současné době známy žádné efektivní algoritmy. Související problém hledání optima sekvence přidání je NP-kompletní (Downey et al., 1981), ale není jisté, zda hledání optimálních řetězců sčítání nebo odčítání je NP-tvrdé.

Například jeden řetězec sčítání a odčítání je: ${displaystyle a_ {0} = 1}$, ${displaystyle a_ {1} = 2 = 1 + 1}$, ${displaystyle a_ {2} = 4 = 2 + 2}$, ${displaystyle a_ {3} = 3 = 4-1}$. To není minimální řetěz sčítání a odčítání pro n= 3, protože jsme si místo toho mohli vybrat ${displaystyle a_ {2} = 3 = 2 + 1}$. Nejmenší n pro které je řetězec sčítání a odčítání kratší než řetězec minimálního sčítání n= 31, které lze vypočítat pouze v 6 přídavcích (spíše než 7 pro řetězec minimálního přidání):

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

Jako sčítací řetězec lze použít i sčítací a odčítací řetězec umocňování přídavného řetězce: vzhledem k řetězci délky sčítání a odčítání L pro n, energie ${displaystyle x ^ {n}}$ lze vypočítat vynásobením nebo dělením X L krát, kde odčítání odpovídají rozdělení. To je potenciálně efektivní v problémech, kde je dělení nenákladná operace, zejména při umocňování eliptické křivky kde rozdělení odpovídá pouhé změně znaménka (jak navrhli Morain a Olivos, 1990).

Nějaký multiplikátory hardwaru vynásobit n pomocí adičního řetězce popsaného n v binárním formátu:

    n = 31 = 0 0 0 1 1 1 1 1 (binární).

Další multiplikátory hardwaru se vynásobí n pomocí řetězce sčítání a odčítání popsaného n v Kódování stánku:

    n = 31 = 0 0 1 0 0 0 0 −1 (kódování stánku).

Reference

• Volger, Hugo (8. dubna 1985). Msgstr "Některé výsledky na řetězcích sčítání / odčítání". Dopisy o zpracování informací. 20 (3): 155–160. doi:10.1016/0020-0190(85)90085-7.
• Morain, François; Olivos, Jorge (1990). "Zrychlení výpočtů na eliptické křivce pomocí řetězců sčítání a odčítání" (PDF). Informační technologie a aplikace. 24 (6): 531–543. CiteSeerX  10.1.1.56.347.
• Downey, Peter J .; Leong, Benton L .; Sethi, Ravi (1981). Msgstr "Výpočet sekvencí s adičními řetězci". SIAM J. Comput. 10 (3): 638–646. doi:10.1137/0210047.
• Sloane, N. J. A. (vyd.). "Pořadí A128998 (délka řetězce minimálního sčítání a odčítání)". The On-line encyklopedie celočíselných sekvencí. Nadace OEIS.