测试一个数字是否为正方形

Question

编写一个高尔夫汇编程序，在寄存器n中给定64位无符号整数，如果n是正方形，则将非零值放入寄存器s，否则将0放入s。

您的高尔夫二进制文件(组装后)必须容纳4096字节.

您的程序将使用以下Python3程序进行评分(必须放在高尔夫目录中)：

import random, sys, assemble, golf, decimal

def is_square(n):
    nd = decimal.Decimal(n)
    with decimal.localcontext() as ctx:
        ctx.prec = n.bit_length() + 1
        i = int(nd.sqrt())
        return i*i == n

with open(sys.argv[1]) as in_file:
    binary, debug = assemble.assemble(in_file)

score = 0
random.seed(0)
for i in range(1000):
    cpu = golf.GolfCPU(binary)

    if random.randrange(16) == 0: n = random.randrange(2**32)**2
    else:                         n = random.randrange(2**64)

    cpu.regs["n"] = n
    cpu.run()
    if bool(cpu.regs["s"]) != is_square(n):
        raise RuntimeError("Incorrect result for: {}".format(n))
    score += cpu.cycle_count
    print("Score so far ({}/1000): {}".format(i+1, score))

print("Score: ", score)

确保用git pull更新高尔夫的最新版本。使用python3 score.py your_source.golf运行评分程序。

它使用一个静态种子生成一组数字，其中大约1/16是平方的。优化这组数字违背了问题的精神，我可以在任何时候改变种子。您的程序必须为任何非负64位输入号码工作，而不仅仅是这些.

最低分获胜.

因为高尔夫是很新的，所以我会在这里给出一些建议。你应该读这个高尔夫规格说明及所有指示及循环费用。在Github存储库中，可以找到一些程序。

对于手动测试，通过运行python3 assemble.py your_source.golf将程序编译成二进制文件。然后使用python3 golf.py -p s your_source.bin n=42运行您的程序，这将启动n设置为42的程序，并在退出后打印寄存器s和循环计数。使用-d标志查看程序退出处寄存器内容的所有值-使用--help查看所有标志。

Answer 1

评分: 27462

我是时候参加高尔夫球比赛了

    # First we look at the last 6 bits of the number. These bits must be
    # one of the following:
    #
    #     0x00, 0x01, 0x04, 0x09, 0x10, 0x11,
    #     0x19, 0x21, 0x24, 0x29, 0x31, 0x39
    #
    # That's 12/64, or a ~80% reduction in composites!
    #
    # Conveniently, a 64 bit number can hold 2**6 binary values. So we can
    # use a single integer as a lookup table, by shifting. After shifting
    # we check if the top bit is set by doing a signed comparison to 0.

    and b, n, 0b111111
    shl v, 0xc840c04048404040, b
    le q, v, 0
    jz no, q
    jz yes, n

    # Hacker's Delight algorithm - Newton-Raphson.
    mov c, 1
    sub x, n, 1
    geu q, x, 2**32-1
    jz skip32, q
    add c, c, 16
    shr x, x, 32
skip32:
    geu q, x, 2**16-1
    jz skip16, q
    add c, c, 8
    shr x, x, 16
skip16:
    geu q, x, 2**8-1
    jz skip8, q
    add c, c, 4
    shr x, x, 8
skip8:
    geu q, x, 2**4-1
    jz skip4, q
    add c, c, 2
    shr x, x, 4
skip4:
    geu q, x, 2**2-1
    add c, c, q

    shl g, 1, c
    shr t, n, c
    add t, t, g
    shr h, t, 1

    leu q, h, g
    jz newton_loop_done, q
newton_loop:
    mov g, h
    divu t, r, n, g
    add t, t, g
    shr h, t, 1
    leu q, h, g
    jnz newton_loop, q
newton_loop_done:
    
    mulu u, h, g, g
    cmp s, u, n 
    halt 0
yes:
    mov s, 1
no:
    halt 0