Wektorowy łańcuch dodawania

W matematyce dla liczb całkowitych dodatnich k i s łańcuch dodawania wektorów jest sekwencją V k - wymiarowych wektorów nieujemnych liczb całkowitych v _i dla − k + 1 ≤ i ≤ s wraz z sekwencją w , taką, że

v - k +1 = [1,0,0,...0,0]

v - k +2 = [0,1,0,...0,0]

⋮

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

v _ja = v _j + v _r dla wszystkich 1≤ i ≤ s gdzie - k +1≤ j , r ≤ i -1

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

w = ( w ₁ ,... w _s ), w _ja = ( j, r ).

Na przykład wektorowy łańcuch dodawania dla [22,18,3] to

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))

Wektorowe łańcuchy dodawania dobrze nadają się do wykonywania wielokrotnego potęgowania : ^{[ potrzebne źródło ]}

₀ ₀ Wejście : Elementy x ,..., x _{k -1} grupy abelowej G i wektorowego łańcucha dodawania wymiaru k obliczenie [ n ,..., n _{k -1} ]

₀ Dane wyjściowe : Element x ^{n ₀} ... x _{k -1}^{n _{r -1}}

0 dla i = -k +1 zrobić y _ja → x _{ja + k -1} _
dla i = 1 do s do y _ja → y _j × y _r
wróć s _{_}

Sekwencja dodawania

₀ Sekwencja dodawania dla zbioru liczb całkowitych S ={ n , ..., n _{r -1} } jest łańcuchem dodawania v zawierającym każdy element zbioru S .

Na przykład obliczanie sekwencji dodawania

{47117343499}

Jest

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

Możliwe jest znalezienie sekwencji dodawania z wektorowych łańcuchów dodawania i odwrotnie, więc są one w pewnym sensie dualne.

Zobacz też