大整數算法系列（13）：單精度乘法優化實現詳解

大整數算法系列（13）：單精度乘法優化實現詳解

大整數乘法系列第十三篇，專注於「大整數 × 單精度整數」的單精度乘法。與 Comba、Karatsuba 適合大數乘大數不同，單精度乘法僅需 O(n) 次單精度乘法，無嵌套循環進位，通過循環展開、內聯彙編等技巧可極致優化。本文給出完整算法流程、關鍵宏定義實現（雙精度/單精度/內聯彙編三版本）及代碼註釋。

一、算法核心思路

計算 z = x * y，其中 x、z 為大整數，y 為無符號單精度數（bn_digit）。

1. olduse = z->used 記錄原長度，用於高位清零。
2. z->used = x->used + 1 目標精度 +1（可能產生進位）。
3. z->sign = x->sign 符號同 x（y 為無符號）。
4. 初始化進位 u = 0。
5. 循環 i = 0 .. x->used-1：
   r = u + x[i] * y（雙精度 bn_udbl）
   z[i] = r & BN_MASK0 取低半字
   u = r >> biL 取高半字作進位
6. z[x->used] = u 寫入最終進位。
7. 清零殘留高位，bn_clamp(z) 壓縮前導零。

若需乘負數，計算完翻轉 z->sign 即可。

二、總體框架代碼

int bn_mul_word(bignum *z, const bignum *x, const bn_digit y) {
    int ret; size_t i, olduse; bn_digit u, *px, *pz;
    olduse = z->used;
    z->sign = x->sign;
    BN_CHECK(bn_grow(z, x->used + 1));
    u = 0; px = x->dp; pz = z->dp;
    for (i = x->used; i >= 32; i -= 32) { MULADDC_WORD_INIT MULADDC_WORD_CORE×32 MULADDC_WORD_STOP }
    for (; i >= 16; i -= 16) { MULADDC_WORD_INIT MULADDC_WORD_CORE×16 MULADDC_WORD_STOP }
    for (; i >= 8; i -= 8) { MULADDC_WORD_INIT MULADDC_WORD_CORE×8 MULADDC_WORD_STOP }
    for (; i >= 4; i -= 4) { MULADDC_WORD_INIT MULADDC_WORD_CORE×4 MULADDC_WORD_STOP }
    for (; i > 0; i--) { MULADDC_WORD_INIT MULADDC_WORD_CORE MULADDC_WORD_STOP }
    *pz++ = u;
    for (i = x->used + 1; i < olduse; i++) *pz++ = 0;
    z->used = x->used + 1;
    bn_clamp(z);
clean:
    return ret;
}

關鍵優化：按 32/16/8/4/1 循環展開，消除循環控制開銷，核心運算封裝在宏中適配不同平台。

三、三種平台宏實現

1. 雙精度變量可用（最簡單）

#define MULADDC_WORD_INIT { bn_udbl r; }
#define MULADDC_WORD_CORE \
    r = u + (bn_udbl)(*px++) * y; \
    *pz++ = (bn_digit)r; \
    u = (bn_digit)(r >> biL);
#define MULADDC_WORD_STOP }

2. 僅單精度變量（模擬雙精度乘法）

將單精度乘法拆解為 4 次半精度乘法（Comba 乘法器思想），處理進位傳播：

#define MULADDC_WORD_INIT { bn_digit a0,a1,b0,b1,t0,t1,r0,r1; }
#define MULADDC_WORD_CORE \
    a0 = (*px << biLH) >> biLH;  b0 = (y << biLH) >> biLH; \
    a1 = *px++ >> biLH;          b1 = y >> biLH; \
    r0 = a0 * b0; \
    r1 = a1 * b1; \
    t0 = a1 * b0;  t1 = a0 * b1; \
    r1 += (t0 >> biLH);  r1 += (t1 >> biLH); \
    t0 <<= biLH;  t1 <<= biLH; \
    r0 += t0;  r1 += (r0 < t0); \
    r0 += t1;  r1 += (r0 < t1); \
    r0 += u;   r1 += (r0 < u); \
    *pz++ = r0;  u = r1;
#define MULADDC_WORD_STOP }

3. 內聯彙編版本（極致性能）

• VC x86：lodsd/mul/add/adc/stosd 指令序列操作 esi/edi/ecx/eax/edx。
• GCC x86：AT&T 語法 lodsl/mull/addl/adcl/stosl，輸入輸出約束 "=m"(px),"=m"(pz),"=m"(u)。
• GCC x64：lodsq/mulq/addq/adcq/stosq，寄存器 rsi/rdi/rcx/rax/rdx。

彙編版直接使用硬體乘法指令 mul 產生雙精度結果，adc 處理進位，單指令完成核心運算，性能最強。

四、總結與下期預告

• 單精度乘法 = 基線乘法特例，O(n) 複雜度，無嵌套循環。
• 關鍵優化：循環展開（32/16/8/4/1）+ 平台適配宏（C/單精度模擬/內聯彙編）。
• 下一篇將講解大整數平方運算優化（利用對稱性減半乘法次數）。

五、系列目錄

大整數算法系列：https://www.cnblogs.com/starrybird/category/大整數算法
本文原始地址：https://www.cnblogs.com/starrybird/p/4489859.html