Karatsuba算法是否必要？基于AVX并行的大整数乘法能否超越其性能？

开发者阿泽

2026-6-14

大整数乘法算法优化疑问

我正在开发一款大整数乘法算法，当前采用LeftLength×RightLength的直接乘法实现，而Karatsuba算法所需的乘法次数更少。以.NET的BigInteger作为参照，我的算法在处理1234位以内的十进制数时效率更高，但当处理位数更多时会出现性能下降。

项目仓库：BigIntMultiplication

以下是核心汇编实现代码：

等长整数乘法实现

; esi: length
; r8: left
; r9: right
; rdi: result

.code
; r10d: leftIndex
; r11d: rightIndex
; r12d: resultIndex


MultiplyByEqualLength proc export
;length1
    cmp ecx, 1
    jnz length1_end
    mov rax, [rdx]
    mov rdx, [r8]
    mul rdx
    mov [r9], rax
    cmp rdx, 0
    jz retLength1
    mov [r9 + 8], rdx
    mov eax, 2
    ret
retLength1:
    mov eax, 1
    ret
length1_end:



    mov esi, ecx
    mov rdi, r9 
    mov r9, r8
    mov r8, rdx

    xor r12, r12

    xor r13, r13
    xor r14, r14
    xor r15, r15


    
    
    mov ecx, esi
start:
    xor r10d, r10d
    mov r11d, r12d

start_inner:
    mov rax, [r8 + r10 * 8]
    mov rdx, [r9 + r11 * 8]
    mul rdx

;add_rax
    add r13, rax
;add_rax_end

;add_rdx_start
    adc r14, rdx
    jnc add_rdx_start_end
;carry
    inc r15d
add_rdx_start_end:

    inc r10d
    dec r11d
    jns start_inner
;start_inner_end
    mov [rdi], r13
    mov r13, r14
    mov r14, r15
    xor r15, r15    


    inc r12d
    lea rdi, [rdi + 8]
    dec ecx
    jnz start
;start_end




    dec esi
    mov ecx, esi
    mov r12d, 1
finish:

    mov r10d, r12d
    mov r11d, esi
finish_inner:
    mov rax, [r8 + r10 * 8]
    mov rdx, [r9 + r11 * 8]
    mul rdx

;add_rax
    add r13, rax
;add_rax_end

;add_rdx_finish
    adc r14, rdx
    jnc add_rdx_finish_end
;carry
    inc r15d
add_rdx_finish_end: 

    inc r10d
    dec r11d
    cmp r11d, r12d
    jae finish_inner
;finish_inner_end
    mov [rdi], r13
    mov r13, r14
    mov r14, r15
    xor r15, r15    



    inc r12d
    lea rdi, [rdi + 8]
    dec ecx
    jnz finish
;finish_end


    mov eax, esi
    add eax, eax
    inc eax

;add_r13
    cmp r13, 0
    jz add_r13_end
    inc eax
    mov [rdi], r13
add_r13_end:

;add_r14
    cmp r14, 0
    jz add_r14_end
    inc eax
    mov [rdi + 8], r14
add_r14_end:


    ret
MultiplyByEqualLength endp

end

不等长整数乘法实现

; esi: leftLength
; ebp: rightLength
; r8: left
; r9: right
; rdi: result

.code
; r10d: leftIndex
; r11d: rightIndex
; r12d: resultIndex


MultiplyByGreaterLength proc export
    mov rdi, [rsp + 40]

;rightLength1
    cmp edx, 1
    jnz rightLength1_end
    push rcx
    mov r9, [r9]
    xor r13, r13
do_while:
    mov rax, [r8]
    mov rdx, r9
    mul rdx

;add_rax
    add r13, rax
    mov [rdi], r13
;add_rax_end

    mov r13, rdx

    lea r8, [r8 + 8]
    lea rdi, [rdi + 8]
        
    dec ecx
    jnz do_while
;do_while_end
    pop rax
;add_rdx
    cmp rdx, 0
    jz add_rdx_end
    inc eax
    mov [rdi], rdx
add_rdx_end:    
    ret
rightLength1_end:


    push rbp

    mov esi, ecx    
    mov ebp, edx

    xor r12, r12

    xor r13, r13
    xor r14, r14
    xor r15, r15


    
    
    mov ecx, ebp
start:
    xor r10d, r10d
    mov r11d, r12d

start_inner:
    mov rax, [r8 + r10 * 8]
    mov rdx, [r9 + r11 * 8]
    mul rdx

;add_rax
    add r13, rax
;add_rax_end

;add_rdx_start:
    adc r14, rdx
    jnc add_rdx_start_end
;carry
    inc r15d
add_rdx_start_end:

    inc r10d
    dec r11d
    jns start_inner
;start_inner_end
    mov [rdi], r13
    mov r13, r14
    mov r14, r15
    xor r15, r15


    inc r12d
    lea rdi, [rdi + 8]
    dec ecx
    jnz start
;start_end






    mov ecx, esi
    sub ecx, ebp
    dec ebp
    mov r12d, 1
middle:
    mov r10d, r12d
    mov r11d, ebp
middle_inner:   
    mov rax, [r8 + r10 * 8]
    mov rdx, [r9 + r11 * 8]
    mul rdx

;add_rax
    add r13, rax
;add_rax_end

;add_rdx_middle
    adc r14, rdx
    jnc add_rdx_middle_end
;carry
    inc r15d
add_rdx_middle_end:

    inc r10d
    dec r11d
    jns middle_inner
;middle_inner_end
    mov [rdi], r13
    mov r13, r14
    mov r14, r15
    xor r15, r15

    inc r12d
    lea rdi, [rdi + 8]
    dec ecx
    jnz middle
;middle_end




    mov ecx, ebp
finish:

    mov r10d, r12d
    mov r11d, ebp
finish_inner:
    mov rax, [r8 + r10 * 8]
    mov rdx, [r9 + r11 * 8]
    mul rdx

;add_rax
    add r13, rax
;add_rax_end

;add_rdx_finish
    adc r14, rdx
    jnc add_rdx_finish_end
;carry
    inc r15d
add_rdx_finish_end:

    inc r10d
    dec r11d
    cmp r10d, esi
    jb finish_inner
;finish_inner_end
    mov [rdi], r13
    mov r13, r14
    mov r14, r15
    xor r15, r15

    inc r12d
    lea rdi, [rdi + 8]
    dec ecx
    jnz finish
;finish_end

    mov eax, esi
    add eax, ebp

;add_r13
    cmp r13, 0
    jz add_r13_end
    inc eax
    mov [rdi], r13
add_r13_end:

;add_r14
    cmp r14, 0
    jz add_r14_end
    inc eax
    mov [rdi + 8], r14
add_r14_end:

    pop rbp
    ret
MultiplyByGreaterLength endp

end

疑问

若我的算法有效利用AVX并行处理技术，能否超越Karatsuba算法的性能？

回答

能否超越Karatsuba算法，取决于几个关键因素：

并行化的实际收益
你的当前实现是标量汇编，每次只完成一组64位整数乘法和累加。AVX（尤其是AVX2/AVX-512）可以一次性完成多组64位乘法——比如AVX2的vpmuludq可以同时计算2组64位无符号整数乘积，AVX-512则能扩展到4组。如果能把乘法-累加循环重构为向量化操作，理论上能将单周期吞吐量提升2-4倍，直接缩小和Karatsuba的复杂度差距。

但要注意：大整数乘法的瓶颈不止是乘法运算，进位传播和内存访问模式同样关键。你的代码中依赖逐位累加后处理进位，向量化时需要设计高效的打包进位处理逻辑，否则并行化的收益会被后续的串行进位操作抵消。

Karatsuba的交叉点阈值
Karatsuba的优势是算法复杂度从O(n²)降到O(n^{log₂3)≈O(n}1.585)，但它的常数因子更高——递归分割、额外的加法/减法操作都会带来开销。你的当前实现在1234位以内更快，说明这个场景下直接乘法的低常数因子盖过了复杂度劣势。

用AVX优化后，直接乘法的常数因子会进一步降低，交叉点阈值（即Karatsuba反超的位数）会大幅后移。如果你的目标场景是千万位以内的大整数，优化后的直接乘法完全有可能在更大范围内保持领先；但当位数增长到非常大（比如百万位以上），Karatsuba的复杂度优势最终还是会显现，除非你进一步结合FFT类的算法。

实现细节的优化程度

内存对齐：确保大整数数组按AVX寄存器的对齐要求（256位或512位）分配，避免未对齐访问带来的性能损失。
循环展开：结合向量化进行循环展开，减少分支预测开销，让CPU的指令流水线更高效。
进位延迟：尝试将进位处理和乘法累加并行，比如使用“延迟进位”策略，在完成多组乘法后再批量处理进位，而不是每次累加后立即处理。

硬件支持
AVX-512的收益比AVX2更显著，但并非所有CPU都支持。如果你的目标平台是主流服务器或较新的消费级CPU，AVX-512的优化能带来更大提升；如果需要兼容老平台，AVX2是更稳妥的选择。

总结：在中低位数范围（比如几万位以内），AVX优化后的直接乘法完全有可能超越Karatsuba的性能；但当位数突破某个阈值后，Karatsuba的复杂度优势会逐渐显现。如果你能将AVX优化和分治策略结合（比如在小位数用AVX直接乘法，大位数切换到Karatsuba），可以覆盖更广泛的性能最优区间。

内容的提问来源于stack exchange，提问作者Fatih Doganay

Karatsuba算法是否必要？基于AVX并行的大整数乘法能否超越其性能？

等长整数乘法实现 #

不等长整数乘法实现 #

疑问 #

回答 #

等长整数乘法实现

不等长整数乘法实现

疑问

回答