装配最短形式中的科拉茨猜想 [英] Collatz Conjecture in Assembly shortest form

问题描述

我们有一个作业，必须在 64 位 nasm 汇编中编写 collat​​z 猜想，其中只有 13 个或更少的命令(包括 RET).现在我们想知道您实际上可以减少多少.我们目前在 9.
下面是伪代码中的collat​​z猜想，供参考:

We had an assignment where we had to write the collatz conjecture in 64bit nasm assembly with only 13 commands or less (RET included). Now we are wondering how much you can actually reduce it. We are currently on 9.
Heres the collatz conjecture in pseudo code for reference:

这是我们目前的代码.一些注意事项:
我们的一位导师说我们可以删除 XOR rax，因为某些调用约定，rax 已经为零.不过它在我的电脑上不起作用，所以我把它包括在这里.
我知道这两个 LEA 可能是最明显要减少的东西，但我们想不出办法，因为 *6 似乎是 LEA 几乎不可能做的唯一事情.

Heres the code we have so far. A few notes:
A tutor of us said we can remove the XOR rax, rax because of some calling convention it's already zero. It doesn't work on my computer though so I've included it here.
I'm aware the two LEA's are probably the most obvious thing to reduce, but we can't think of a way since *6 seems to be the only thing thats literally impossible to do with LEA.

GLOBAL collatz
SECTION .text

collatz:
    XOR rax, rax

    .while:
        SHR rdi, 1
        JNC .even
            LEA rdi, [rdi*2+1]
            LEA rdi, [rdi*2+rdi+1]
        .even:

        INC rax

        CMP rdi, 1
        JA .while
    RET

推荐答案

这个有点短:

collatz:
        or     $-1,%eax
.loop:  inc    %eax
        lea    1(%rdi,%rdi,2),%rsi
        shr    %rdi
        cmovc  %rsi,%rdi
        jnz    .loop
        ret

或者，在 nasm 语法中:

or, in nasm syntax:

collatz:
        or     eax,-1
.loop:  inc    eax
        lea    rsi,[rdi+rdi*2+1]
        shr    rdi
        cmovc  rdi,rsi
        jnz    .loop
        ret

要理解此代码，请密切注意进位标志 (CF) 和零标志 (ZF).

To understand this code, pay close attention to the carry flag (CF) and zero flag (ZF).

这篇关于装配最短形式中的科拉茨猜想的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！