Testing if a number is a square Write a GOLF assembly program that given a 64-bit unsigned integer in register n puts a non-zero value into register s if n is a square, otherwise 0 into s.

Your GOLF binary (after assembling) must fit in 4096 bytes.



Your program will be scored using the following Python3 program (which must be put inside the GOLF directory):

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)


Make sure to update GOLF to the latest version with git pull. Run the score program using python3 score.py your_source.golf.

It uses a static seed to generate a set of numbers of which roughly 1/16 is square. Optimization towards this set of numbers is against the spirit of the question, I may change the seed at any point. Your program must work for any non-negative 64-bit input number, not just these.

Lowest score wins.



Because GOLF is very new I'll include some pointers here. You should read the  GOLF specification with all instructions and cycle costs. In the Github repository example programs can be found.

For manual testing, compile your program to a binary by running python3 assemble.py your_source.golf. Then run your program using python3 golf.py -p s your_source.bin n=42, this should start the program with n set to 42, and prints register s and the cycle count after exiting. See all the values of the register contents at program exit with the -d flag - use --help to see all flags.
Score: 27462
About time I'd compete in a GOLF challenge :D
    # 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