ベクトル加算連鎖

数学では、正の整数kとsに対して、ベクトル加算チェーンは、− k + 1 ≤ i ≤ sの非負整数のk次元ベクトルv _iの列Vと、次のような列wからなる。

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

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

⋮

⋮

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

すべての 1 ≤ i ≤ sに対してv _i = v _j + v _rが − k + 1 ≤ j、r ≤ i − 1 で成り立つ。

v _s = [ n ₀ , ..., n _{k −1} ],

w = ( w ₁ , ..., w _s ), w _i = ( 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))

ベクトル加算チェーンは多重べき乗を実行するのに適しています: ^{[ 1 ]}

入力:アーベル群Gの要素x ₀、 ...、x _{k −1と、次元}kのベクトル加算チェーン[ n ₀、 ...、n _{k −1} ]を計算する

出力: 要素x ₀ ^{n ₀} ... x _{k −1} ^{n _{r −1}}

1. i = − k + 1から0までy _i → x _{i + k −1}を実行する
2. i = 1からsまでy _i → y _j × y _{r を}実行する
3. y _sを返す

整数の集合S = { n ₀ , ..., n _{r −1} }に対する加算列は、 Sのすべての要素を含む加算チェーンvです。

例えば、加算シーケンスを計算する

{47, 117, 343, 499}

は

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

ベクトル加算連鎖から加算シーケンスを見つけることが可能であり、その逆も可能なので、ある意味で双対関係にある。^{[ 2 ]}

• 連鎖反応
• 加算連鎖指数
• 2乗による指数計算
• 非隣接形式