Векториальная цепочка сложения

В математике для положительных целых чисел k и s векторная цепочка сложения представляет собой последовательность V k -мерных векторов неотрицательных целых чисел v _i для − k + 1 ≤ i ≤ s вместе с последовательностью w ,такой, что

v _{− k +1} = [1,0,0,...0,0]

v _{− k +2} = [0,1,0,...0,0]

⋮

⋮

v ₀ = [0,0,0,,...0,1]

v _i = v _j + v _r для всех 1≤ i ≤ s с - k +1≤ j , r ≤ i -1

v _s знак равно [ п ₀ ,..., п _{k -1} ]

ш знак равно ( ш ₁ ,... ш _s ), ш _я = ( j, r ).

Например, векторная цепочка сложения для [22,18,3] равна

V =([1,0,0],[0,1,0],[0,0,1],[1,1,0],[2,2,0],[4,4,0],[5,4,0],[10,8,0],[11,9,0],[11,9,1],[22,18,2],[22,18,3])

w =((-2,-1),(1,1),(2,2),(-2,3),(4,4),(1,5),(0,6),(7 ,7),(0,8))

Векторные цепочки сложения хорошо подходят для выполнения многократного возведения в степень :

данные : элементы x ₀ ,..., x _{k -1} абелевой группы G и векторная цепочка сложения размерности k, вычисляющая [ n ₀ ,..., nk _{Входные -1} ]

Выход : элемент x _0. ^{п ₀} ... х _{к -1} ^{н _{р -1}}

1. для i = -k +1 до 0 do y _i → x _{i + k -1}
2. для i = 1 до s do y _i → y _j × y _r
3. вернуть y _​

Последовательность добавления

Последовательность сложения для набора целых чисел S = { n ₀ , ..., n _{r -1} } представляет собой цепочку сложения v , которая содержит каждый элемент S .

Например, вычисление последовательности сложения

{47,117,343,499}

является

(1,2,4,8,10,11,18,36, 47 ,55,91,109, 117 ,226, 343 ,434,489, 499 ).

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

См. также

• Дополнительная цепочка
• Возведение в степень по цепочке сложения
• Возведение в степень возведением в степень
• Несмежная форма