用长乘法相乘大数

Question

三周前，我发布了用Karatsuba法乘法大数，其中我提到了我的经典长乘法版本。这就是我今天发的帖子，这样人们就可以自己比较了。同时，我希望有人仍能找到进一步改进代码的方法！

下面介绍的多精度mpMul过程需要在堆栈上传递4个参数.

• 第一个参数指定两个输入的精度(以位为单位)，这需要64的倍数。
• 第二个param指向第一个输入，也就是乘法。
• 第三个参数指向第二个输入，也就是乘法器。
• 第四个参数指向double长度结果需要到达的位置。

在EAX寄存器中返回双长度乘积的地址，如果结果超出精度，将设置进位标志。

我采用了以下想法：

• 我预先探测到前导和尾随零。所有前导零都可以简单地忽略。对于乘法器或乘法器中的每个尾随零，结果中插入一个新的尾随零。
• 由于检测嵌入式零没有明显的成本，所以安装了适当的快捷键。
• 我让较短的数字控制外循环，从而减少了成本较高的内环运行的次数。
• 我尽量避免进入进位循环。

计算MAX_UINT^2时，乘数为{4}^{(n-5)}\$其中\$n=\log_2\text{精度}\$

; -------------------------------------
; Multiplying using long multiplication
; -------------------------------------
; IN () OUT (eax,CF)
mpMul:  pushad
        mov     ebp, esp
        mov     edx, [ebp+32+4]      ;IntSize {64, 128, 192, ...}
        shr     edx, 5               ;Bits -> dwords

        mov     edi, [ebp+32+4+12]   ;BufferC (double length result)
        mov     [ebp+28], edi        ;pushad.EAX
        push    edx edi              ;(1)

        imul    eax, edx, 8
        pxor    xmm0, xmm0
.Wipe:  sub     eax, 16              ;Clear result buffer
        movdqu  [edi+eax], xmm0
        jnz     .Wipe

        mov     esi, [ebp+8+32+4+8]  ;BufferB (default multiplier)
        mov     ebx, [ebp+8+32+4+4]  ;BufferA (default multiplicand)
        call    .Prune               ; -> ECX ESI EDI
        xchg    ebx, esi
        mov     ebp, ecx
        call    .Prune               ; -> ECX ESI EDI

        cmp     ebp, ecx
        jbe     .MultiplierLoop      ;Multiplier 'is shorter' Multiplicand
        xchg    esi, ebx
        xchg    ecx, ebp
; - - - - - - - - - - - - - - - - - -
.MultiplierLoop:
        cmp     dword [ebx], 0       ;Embedded zero in multiplier
        je      .Zero

        push    ecx esi edi          ;(2)
.MultiplicandLoop:
        add     edi, 4
        lods    dword [esi]
        test    eax, eax             ;Embedded zero in multiplicand
        jz      .Done
        mul     dword [ebx]
        add     [edi-4], eax
        adc     [edi], edx
        jnc     .Done
        adc     dword [edi+4], 0     ;(*) Avoid entering the carry-loop
        jnc     .Done
        mov     eax, edi
.Carry: add     eax, 4               ;The carry-loop
        add     dword [eax+4], 1     ;(*) +4
        jc      .Carry
.Done:  dec     ecx
        jnz     .MultiplicandLoop
        pop     edi esi ecx          ;(2)

.Zero:  add     edi, 4
        add     ebx, 4
        dec     ebp
        jnz     .MultiplierLoop
; - - - - - - - - - - - - - - - - - -
.END:   pop     edi ecx              ;(1)
        lea     edi, [edi+ecx*4]     ;Middle of double length result
        xor     eax, eax
        repe scas dword [edi]        ;Defines CF

        popad
        ret     16
; - - - - - - - - - - - - - - - - - -
; IN (eax=0,edx,esi,edi) OUT (ecx,esi,edi)
.Prune: mov     ecx, edx             ;Precision expressed as dwords (2+)
.Lead:  dec     ecx                  ;Skip leading zeroes
        js      .Quit                ;Multiplier and/or Multiplicand is 0
        cmp     [esi+ecx*4], eax     ;EAX=0
        je      .Lead
        inc     ecx                  ;Significant dwords
        cmp     [esi], eax           ;EAX=0
        jne     .Ready
.Trail: dec     ecx                  ;Skip trailing zeroes
        add     esi, 4               ;Skip low dwords that are zero
        add     edi, 4               ; by moving starting points upwards
        cmp     [esi], eax           ;EAX=0
        je      .Trail
.Ready: ret
.Quit:  pop     eax                  ;Forget 'call .Prune'
        jmp     .END
; -----------------------------------

Answer 1

A这些EBP相对位移是错误的。如果在ESP相对地址中使用，它们将是正确的。

mov esi, [ebp+8+32+4+8] ;BufferB (default multiplier) mov ebx, [ebp+8+32+4+4] ;BufferA (default multiplicand)

B。英特尔优化手册提到：

所有分支目标应该是16字节对齐。

您可以应用此方法，并查看它对代码的作用。

C。我看不出检查嵌入式零有什么好处。我认为这将是非常罕见的。

.MultiplicandLoop:添加edi，4个lods dword测试eax，eax；嵌入零在乘法和jz .Done mul dword中。

如果从上述代码中删除test和jz指令，则应插入其他(有用)指令。为什么？暗示就在你自己说的话里：

...detecting嵌入式零没有明显的代价.

这意味着lods和mul之间的代码是免费执行的！

.MultiplicandLoop:
    lods    dword [esi]
    add     edi, 4
    mul     dword [ebx]

Answer 2

一些特别的想法：

• 使用xchg reg，reg比您预期的要贵。
• 推沙德也不是很棒。
• 我不知道它在这里有多有用，但您也可以看看这。这与与addc链相关的问题有关。
• 虽然人们对疑心的看法是关于repe scas的，但在这里它可能不是一个问题。
• 通过IACA运行这个程序也可能很有趣。像倒转两条指令这样简单的事情可以产生可衡量的不同。人类很难再写高效的asm了。如果你是人工智能的话，很抱歉。今天的情况不像以前那样不可能了。

用x64编写这篇文章可能也很有趣。更多寄存器，每个寄存器更多位。在某些地方一定有一些好处，而x64现在已经是标准的了。

你可能希望对算法本身有更多的分析，但这就是我所得到的。

Edit1：

一个很晚才开始的想法。既然您已经有了输入needs to be a multiple of 64的要求，那么添加另一个说明您的内存指针必须对齐64字节的方法怎么样？这允许您将movdqu替换为movdqa。很小，但还是很小。

可能更小:我可能会尝试将imul eax, edx, 8更改为mov eax, edx ; shl eax, 3或lea eax, [edx * 8]。从“指令长度”的角度来看，imul是明显的赢家。从“延迟”的角度来看，也许不是这样。IACA可能会给你这个答案。它很适合回答这样的问题：add esi, 4对我的代码来说比lea esi, [esi + 4]更好吗？