2,000,000以下的所有素数之和--汇编中的Euler #10项目

Question

我目前正在为大学学习集会，我想听听关于我写的东西的一些反馈意见。目前我已经实现了来自ProjectEuler的问题1、2、3和10。目标是将所有素数相加，从0到2,000,000。

对于问题10，我使用公式6n +- 1来检查素数。为了检查它们，我测试除数2，3，5，7，.我目前只使用x64体系结构的通用寄存器。

你对这段代码有什么反馈吗？我能做点更好的事吗？优化什么？

我在x64模式下使用NASM。这是我目前的实现：

; CurrentPrime          Current prime to test
; Sum               Sum
; CurrentN              n of 6n +- 1
; PrimeMode             Wether we're doing + or - 1 (0 means -)
%define Sum r9
%define CurrentPrime r8
%define CurrentN r10
%define PrimeMode r12

section .text
global main
main:
    mov Sum, 5 ; 2+3 not included in 6n +- 1
    mov CurrentN, 0 ; This gets inc'ed below

loop:

    ; Increase n
    inc CurrentN

    ; Break every 10000 Ns for debugging reasons
    mov rax, CurrentN
    mov rbx, 10000
    mov rdx, 0
    div rbx
    cmp rdx, 0
    jne _debug_next
    nop ; Break here
_debug_next:

    ; multiply it by 6 and save it to CurrentPrime
    mov rax, CurrentN
    mov rbx, 6
    mul rbx
    mov CurrentPrime, rax

    ; Start with 6n-1
    dec CurrentPrime

    ; Reset registers for testing
    mov PrimeMode, 0
    ; This is our divisor
    mov rcx, 2

next_prime_test:

    ; When the number to test is >= 2000000, then exit
    cmp CurrentPrime, 2000000
    jge finish

    ; When divisor_to_test > (number_to_test/2), then this is prime
    mov rax, CurrentPrime
    mov rbx, 2
    mov rdx, 0
    div rbx
    cmp rax, rcx
    jl is_prime

    ; Test divisor for divisor
    mov rax, CurrentPrime
    mov rbx, rcx
    mov rdx, 0
    div rbx
    cmp rdx, 0
    je check_next_prime

    ; We only check odd numbers. 
    ; But to get from 2 to 3, we may not inc when we're at 2.
    cmp rcx, 2
    je skip_add

    inc rcx

skip_add:

    ; This divisor isn't a divisor of our number. Let's try with the next divisor.
    inc rcx
    jmp next_prime_test

is_prime:
    ; This number is prime, add it to our result.
    add Sum, CurrentPrime

check_next_prime:

    ; If we're doing 6n-1, increase by 2 to get 6n+1, then check again
    cmp PrimeMode, 0
    ; If we've done 6n+1, then go for the next n
    jne loop

    mov PrimeMode, 1 ; Set plus
    mov rcx, 2 ; Reset rcx to start over with a new prime
    add CurrentPrime, 2 ; 6n-1 +2 = 6n+1

    ; Check 6n+1
    jmp next_prime_test

finish:
    ; Result is in rax
    mov rax, Sum

    ret

Answer 1

因为所有变量Sum、CurrentPrime、CurrentN和PrimeMode都驻留在寄存器中，所以代码可以/应该从这一事实中受益。

您使用以下方法计算了CurrentPrime = CurrentN * 6 - 1：

mov rax，CurrentN；乘以6，保存到CurrentPrime mov rax，6 mul rax mov CurrentPrime，rax dec CurrentPrime；从6n-1开始。

这不仅使寄存器rax、rbx和rdx崩溃，还使用了生成128位结果的mul指令变体。当不需要结果的上64位时，Intel建议不要使用这种形式，这在您的程序中是这样的。一个更好的乘法来自使用2操作数形式的imul。

mov  CurrentPrime, CurrentN
imul CurrentPrime, 6
dec  CurrentPrime

这个更短更快的解决方案也不使用任何附加寄存器！

当您重置变量和注册时，您始终使用mov指令。

mov CurrentN，0；下面是mov PrimeMode，0 mov rdx，0

由于这些变量实际上也是寄存器，并且由于对寄存器进行零化的首选方法是将其与其本身xor，所以您应该编写：

xor  CurrentN, CurrentN
xor  PrimeMode, PrimeMode
xor  rdx, rdx

这会产生更短的代码。

这是检查PrimeMode是否为零的方法。

cmp PrimeMode，0 jne循环

因为这个变量实际上是一个寄存器，并且由于判断寄存器是否为零的首选方法是将其与其本身test，所以您应该编写：

test PrimeMode, PrimeMode
jnz  loop

在下一个片段中，当找到6n-1的质数时，您希望切换PrimeMode。

cmp PrimeMode，0；如果我们已经完成了6n+1，那么转到下一个done循环移动PrimeMode，1；Set +

这很好，但是您可以利用这样一个事实，即PrimeMode在这里等于零，它只是递增，而不是使用占用空间的即时值：

test PrimeMode, PrimeMode
jnz  loop
inc  PrimeMode             ;Set plus

分裂是昂贵的。

为了得出当前数是素数的结论，您可以执行2的除法。

；当divisor_to_test > (number_to_test/2)时，这是素mov rax，CurrentPrime mov rcx，2 mov rdx，0 div rcx rax，rcx jl is_prime。

您应该将这个浪费的div替换为一个简单的右转：

mov  rax, CurrentPrime
shr  rax, 1
cmp  rax, rcx
jl   is_prime

为什么在代码的下一部分中，您的部门不立即使用rcx寄存器？为什么首先将rcx中的除数移到rbx？那只是个多余的指令！

；除数mov rax，CurrentPrime mov rdx，rcx mov rdx，0 div rdx rdx，0 je check_next_prime的测试除数。

不再破坏rbx寄存器并应用上述许多提示提供：

mov  rax, CurrentPrime
xor  rdx, rdx
div  rcx
test rdx, rdx
jz   check_next_prime

避免重复操作。

在您的最内环中，您一直在检查CurrentPrime是否超过2000000，但是您忘记了CurrentPrime的值在这个内环中没有变化。最好将测试移到next_prime_test标签之上，引入一个附加的标签MAYBE_next_prime_test。

    mov  PrimeMode, 0             ; Reset registers for testing
    ;;;mov  rcx, 2     <----- Remove this line
MAYBE_next_prime_test:
    cmp  CurrentPrime, 2000000    ; When the number to test is >= 2000000, then exit
    jge  finish
    mov  rcx, 2     <----- This line replaces both others
next_prime_test:

    ...

    inc rcx
    jmp next_prime_test

    ...

    ;;;mov  rcx, 2     <----- Remove this line 
    add  CurrentPrime, 2          ; 6n-1 +2 = 6n+1
    jmp  MAYBE_next_prime_test    ; Check 6n+1
finish:
    mov  rax, Sum                 ; Result is in rax

我还避免了重复您已经在程序顶部的mov rcx, 2指令。刮掉一些字节！