如何计算 0 到 1x10^6 之间的斐波那契数的奇数之和

Question

我在创建一个计算奇数之和结果的 x64 masm 程序时遇到了问题。答案在 RAX 中为 109E82h (1089154d)。我很难弄清楚 masm 是如何工作的，但它太令人困惑了。到目前为止，这是我尝试过的方法，但是 RAX 寄存器中的值不正确。我已经尽我所能，但我不知道我哪里错了。

extrn ExitProcess: proc

.data
fib1 QWORD 0
fib2 QWORD 1
sum QWORD 0
  
.code
_main PROC

    ; calculate the Fibonacci sequence up to 10^7
    mov rax, 10000000
    mov rcx, fib1
    mov rdx, fib2
FIB_LOOP:
    add rcx, rdx
    mov fib1, rdx
    mov fib2, rcx
    cmp rcx, rax
    jle FIB_LOOP
    ; add odd numbers to the sum
    mov rcx, fib1
    add rcx, rdx  ; rdx contains the last even Fibonacci number
SUM_LOOP:
    test cl, 1    ; check if the current number is odd
    jz SKIP_ADD
    add sum, rcx
SKIP_ADD:
    add rcx, rdx
    mov rdx, rcx
    cmp rcx, rax
    jle SUM_LOOP

    ; exit the program
    mov rax, sum
    call ExitProcess

_main ENDP
END

Answer 1

但我不知道我哪里错了。

嗯，我不明白为什么你的程序的第一部分是计算斐波那契数列到 10^7，当标题提到你需要处理 [0,10^6] 范围内的数字时.这比需要的高 10 倍！在那之后，求和循环进入更大的数字，幸运的是 RAX 限制没有改变，所以这部分很快就退出了。

• 您需要在运行创建它们的循环时对奇数斐波那契数求和。
• 您可以避免在此代码中使用基于内存的变量。你有很多寄存器可以使用。
• 虽然你想要 64 位代码，但并不总是需要使用 64 位寄存器。任务的有限数值范围允许您使用更高效的 32 位寄存器。由于写入 64 位寄存器的低位双字会自动将高位双字归零，因此最终将由 RAX 保存结果 1089154。

  xor  eax, eax     ; RAX=0 is Number1 (Fibonacci)
  lea  ecx, [rax+1] ; RCX=1 is Number2
  cdq               ; RDX=0 is SumOfOdds

More:
  xchg eax, ecx     ; -> RCX = 0,  1,  1,  2,  3,  5,   8, ...
  add  eax, ecx     ; -> RAX = 1,  1,  2,  3,  5,  8,  13, ...
  test al, 1
  jz   isEven
  add  edx, eax     ; -> RDX  +1, +1,     +3, +5,     +13, ...
isEven:
  cmp  eax, 1000000
  jb   More

  test al, 1        ; Keep this one-time correction outside of the loop
  jz   Done
  sub  edx, eax     ; Take back last addition of an odd Fib
Done:
  xchg eax, edx     ; Final result in RAX

这可能是一个有趣的选择（未经测试）：

  xor  eax, eax     ; RAX=0 is Number1 (Fibonacci)
  lea  ecx, [rax+1] ; RCX=1 is Number2
  cdq               ; RDX=0 is SumOfOdds

SumIt:
  add  edx, eax     ; -> RDX  +1, +1,     +3, +5,     +13, ...
More:
  xchg eax, ecx     ; -> RCX = 0,  1,  1,  2,  3,  5,   8, ...
  add  eax, ecx     ; -> RAX = 1,  1,  2,  3,  5,  8,  13, ...
  test al, 1
  jz   More
  cmp  eax, 1000000
  jb   SumIt

  xchg eax, edx     ; Final result in RAX