Radix 2^51 分肢以延遲進位擊敗進位加法鏈

相加寬度超過 64 位元的數字本應很簡單：把每個 256 位元整數拆成四個 64 位元片段，相加，再把任何溢位向上傳遞。問題出在溢位——不處理進位，答案就是錯的，所以正確版本會從最低有效分肢開始，串接 x86 的進位加法指令（adc）。在現代亂序處理器上，這條鏈比不正確的平行程式碼還慢：adc 是較重的指令，而且每一條都依賴前一條產生的進位旗標。Haswell CPU 每週期最多可發出四個獨立的加法，但串接的 adc 會序列執行。

反直覺的修正方法在密碼學文獻中稱為 radix 2^51 表示法：使用更多分肢，而每個分肢都小於一個暫存器。顯而易見的做法是把 256 位元拆成四個以 2^64 為基的數位，這種做法則拆成五個以 2^51 為基的數位；每個 64 位元分肢仍容納其數位，但頂端 12–13 位元保持空白，作為進位可累積的空間。由於有這塊餘裕，相加正規化後的值完全不會產生進位，直到備用位元填滿為止——大約可達 2^13 次加法——因此每次加法都獨立，處理器可平行排程。

進位並未被消除，只是被延遲。當餘裕用盡時，一次正規化遍會把每個分肢的溢位移入上一分肢並清空餘裕；減法同理，把分肢視為有號數，代價是少一個餘裕位元。作者在 Haswell 機器上的快速基準測試發現，radix-2^51 加法在少至三次加法時就已快於 radix-2^64 加法，且已計入轉入與轉出該表示法的成本，隨著加法累積越多，節省越大。

文章先在紙上建立直覺：在十進位中，把每個數位的範圍加寬，使其能數超過 9，就能在任何數位溢位前相加數個正規化數字，最後再以一次正規化遍把結果轉回。移到二進位暫存器後，同樣原理正是該表示法在密碼學中成為標準的原因——也是為什麼反直覺地，把數字分散到更多暫存器並發出更多指令，反而讓算術更快。本文最初發表於 2017 年，於 2020 年 5 月被貼上 Hacker News，獲得 518 點與 83 則留言。

把分肢縮小到 51 位元，讓備用位元吸收進位：加法保持獨立且可平行，正規化只在最後進行一次

進位就是依賴關係：串接的 adc 指令會序列化，因為每一條都等待前一個進位旗標，而獨立的普通加法在 Haswell 上每週期可發出四個。

空餘裕是關鍵：64 位元暫存器內的 51 位元數位留下 12–13 位元空閒，因此大約 2^13 次加法後才必須傳播進位。

一次延遲遍勝過多次立即處理：最後才正規化是固定的一次掃描，而不是每次運算都背負進位依賴。

多出的分肢值得付出：五個普通加法在少至三次加法時就勝過四條 adc 鏈，即使計入轉換成本亦然。

要打破序列依賴，就加入日後再償還的餘裕：保留餘裕讓熱路徑運算自由執行，然後以一次遍結算延遲的工作。

本文發表於 2017 年，於 2020 年 5 月被貼上 Hacker News，獲得 518 點與 83 則留言。實務工作者把這個技巧錨定到真實程式碼：留言者指出 Curve25519 的體算術以 2^255−19 為模運算，因此數值可容納於 51 位元分肢，在 32 位元 CPU 上則有 radix-2^25.5 變體；其他人討論 Broadwell 的 ADCX/ADOX 指令與部分暫存器停滯，還有一人指出文章對最高分肢的解釋有誤。這項技術仍是文章所稱的樣子：密碼學中標準的 radix-2^51 表示法，用於體算術必須快速且常數時間的場合。