加法鏈

在數學中，加法鏈（）是由一組由自然數所組成的序列，該序列以 1 開始，到目標數字 n 結束，例如：(1,2,3,6,12)，即為目標數字為 12 的加法鏈且序列中的每個數為序列出現過的兩數之和。而整個鏈所需要的加法次數則被稱作加法鏈的長度，通常記為 s，而 s 的值為數列內所包含的基數數量再減去一，以前面的例子來說 s = 4。

範例
這裡有個簡單的例子：(1,2,3,6,12,24,30,31) 就是一個目標數字 n 為 31 且 s = 7 的加法鏈
:2 = 1 + 1
:3 = 2 + 1
:6 = 3 + 3
:12 = 6 + 6
:24 = 12 + 12
:30 = 24 + 6
:31 = 30 + 1

在加法鏈求冪的方法中就有使用到加法鏈的方法，而這個方法允許我們將目標數字 n 設定為某任意數 A 的指數，進而計算出該數的冪；舉例來說，我們現有一數 A^x，則我們可以將加法鏈的目標數字 n 設定為 x，進而計算出其對應的加法鏈。更具體的說，假設我們現需要計算一自然數A^{31} 的冪，則可以擴展成求目標數字 n 為 31 的加法鏈的問題。就結果來說，總共就只需要計算七次乘法即可求出其冪，相較於不斷的連乘 n 所需的 30 次乘法以及平方求冪的 8 次乘法所需要的乘法次數要少：
:n^2 = n \cdot n
:n^3 = n^2 \cdot n
:n^6 = n^3 \cdot n^3
:n^{12} = n^6 \cdot n^6
:n^{24} = n^{12} \cdot n^{12}
:n^{30} = n^{24} \cdot n^6
:n^{31} = n^{30} \cdot n

對於加法鏈常見的誤區
計算最短的加法鏈並非一件易事，但我們依舊可以將這個問題分成兩部份：
: 給定多個整數 n_1, n_2, ..., n_m，接著找到一組由 1 開始並包含所有目標數字 n_1, n_2, ..., n_m 的最短加法鏈問題
: 給定一目標數字 n 且找到從 1 到目標數字 n 的最短加法鏈問題

其中部份一給予多個整數求最短加法鏈的問題已經被證明為是 NP完備；而部份二給予單一目標數字 n 且求最短加法鏈至今依舊未被任何論文嚴謹證明或是被普遍接受的文章指出其是 NP完備的。

許多消息來源會寫下類似「給予單一目標數字 n 並且找到最短加法鏈是 NP完備的......」等等語句，但它們多半在引用時混淆了兩件事：一、Computing sequences with addition chains(1981)。

針對上述第一點的論述，Achim Flammenkamp 曾經在其網頁「Shortest Addition Chains。

一種廣為人知的計算相對較短加法鏈的算法是二進制方法，類似於平方求冪。在這種方法中，目標數字 n 的加法鏈是由以下方式計算出來的：
: 先將目標數字 n 轉換至二進制
: 初始化加法鏈，其 x_0 = 0 且 i = 1
: 從左至右依序讀取位數，若為 0 則 x_i = x_{i-1} \cdot 2，否則 x_i = x_{i-1} \cdot 2 + 1
: i + 1
: 將 x_0 從結果中去除

以下使用二進制方法計算目標數字為 26 的加法鏈範例：
:先將目標數字 n 以二進制表示 26_{10} \to 11010_2
:初始化 x_0 = 0
開始從左而右讀取位數
:1 \to x_1 = (x_0 \times 2) + 1 = (0 \times 2) + 1 = 1
:1 \to x_2 = (x_1 \times 2) + 1 = (1 \times 2) + 1 = 3
:0 \to x_3 = x_2 \times 2 = 3 \times 2 = 6
:1 \to x_4 = (x_3 \times 2) + 1 = (6 \times 2) + 1 = 13
:0 \to x_5 = x_4 \times 2 = 13 \times 2 = 26
至此我們得到了一序列為 [0,1,3,6,13,26]。最後，去除 x_0 之後，我們就可得出目標數字為 26 以二進制方法所產生的加法鏈為 [1,3,6,13,26]。

我們同樣可以使用被稱作因數法的方法來嘗試尋找最短加法鏈，其底層邏輯是目標數字 n 的質因數分解。如果 n 有一個質因數p，則可以先找到目標數字為 n/p 的加法鏈，接著與一個目標數字 p 的加法鏈串接，同時透過將序列內每個元素乘以 n/p 來重構該加法鏈，最終得到目標數字 n 的加法鏈。

而因數法和二進位方法可以結合成 Brauer 的 m 進位方法，其方法是透過隨機選擇一自然數 m（無論是否能整除 n），先計算目標數字 m 的加法鏈，接著計算目標數字 \lfloor n/m\rfloor 的加法鏈，最後將兩加法鏈串接起來獲得目標數字為 m\lfloor n/m\rfloor 的加法鏈，最後加上餘數來得到最終的結果。

正因為有新方法持續不斷的被提出，而成就了一系列被稱為滑動窗口方法的算法。

可以在為目標數字 n 的加法鏈末尾加入一個新的值 2n = n + n，從而將目標數字 n 的加法鏈轉換為目標數字 2n 的加法鏈，從而得到不等式 l(2n) \leq l(n) + 1，然而目標數字 n 和目標數字 2n 的加法鏈長度並非總是符合前述的不等式，在某些情況下，目標數字 2n 是有可能可以透過某些方法獲得更短的加法鏈。如 Knuth 就觀察到 l(382) = l(191) = 11。

當 12509 > n 時，l(n) = l^*(n)等式成立。Neill Clift 也進一步驗證了當 n \le 64 時， l(2^n-1) = n - 1 + l(n)。

查看更多

• Addition-subtraction chain
• Vectorial addition chain
• Lucas chain

參考文獻
外部連結

• . Note that the initial "1" is not counted (so element #1 in the sequence is 0).

*[http://www.numdam.org/item?id=JTNB_1994__6_1_21_0 F. Bergeron, J. Berstel. S. Brlek "Efficient computation of addition chains"]