Testando se um número é um quadrado

16

Escreva um programa de montagem GOLF que, dado um número inteiro não assinado de 64 bits, registre num valor diferente de zero no registrador, sse nfor um quadrado, caso contrário, 0em s.

Seu binário GOLF (após a montagem) deve caber em 4096 bytes.


Seu programa será pontuado usando o seguinte programa Python3 (que deve ser colocado dentro do diretório GOLF ):

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)

Certifique-se de atualizar o GOLF para a versão mais recente com git pull. Execute o programa de pontuação usando python3 score.py your_source.golf.

Ele usa uma semente estática para gerar um conjunto de números dos quais aproximadamente 1/16 é quadrado. A otimização em relação a esse conjunto de números é contrária ao espírito da pergunta. Posso mudar a semente a qualquer momento. Seu programa deve funcionar para qualquer número de entrada não negativo de 64 bits, não apenas esses.

Menor pontuação ganha.


Como o GOLF é muito novo, incluirei alguns indicadores aqui. Você deve ler a especificação GOLF com todas as instruções e custos de ciclo . No repositório Github, exemplos de programas podem ser encontrados.

Para teste manual, compile seu programa para um binário executando python3 assemble.py your_source.golf. Em seguida, execute o programa usando python3 golf.py -p s your_source.bin n=42, isso deve iniciar o programa com n42, e imprime o registro se a contagem do ciclo após a saída. Veja todos os valores do conteúdo do registro na saída do programa com o -dsinalizador - use --helppara ver todos os sinalizadores.

orlp
fonte
Desenrolei um loop de 32 iterações para salvar ~ 64 operações por teste. Provavelmente isso está fora do espírito do desafio. Talvez isso funcionasse melhor como velocidade dividida por código de tamanho?
Sparr
O desenrolar do @Sparr Loop é permitido, desde que o seu binário se ajuste a 4096 bytes. Você sente que esse limite é muito alto? Estou disposto a abaixá-lo.
Orlp
@Sparr Seu binário agora é de 1,3k, mas acho que o desenrolar do loop de 32 iterações é um pouco demais. Como soa um limite binário de 1024 bytes?
orlp
Aviso a todos os participantes! Atualize seu intérprete GOLF com git pull. Encontrei um bug no operando à esquerda, que não era encapsulado corretamente.
orlp
Não tenho certeza. 1024 exigiria apenas um loop uma vez; Eu ainda salvaria ~ 62 ops por teste ao desenrolar. Suspeito que alguém também possa usar muito esse espaço como uma tabela de pesquisa. Eu vi alguns algoritmos que desejam 2-8k de tabelas de pesquisa para raízes quadradas de 32 bits.
Sparr

Respostas:

2

Pontuação: 22120 (3414 bytes)

Minha solução usa uma tabela de pesquisa de 3kB para propagar um solucionador de métodos de Newton que executa de zero a três iterações, dependendo do tamanho do resultado.

    lookup_table = bytes(int((16*n)**0.5) for n in range(2**10, 2**12))

    # use orlp's mod-64 trick
    and b, n, 0b111111
    shl v, 0xc840c04048404040, b
    le q, v, 0
    jz not_square, q
    jz is_square, n

    # x will be a shifted copy of n used to index the lookup table.
    # We want it shifted (by a multiple of two) so that the two most 
    # significant bits are not both zero and no overflow occurs.
    # The size of n in bit *pairs* (minus 8) is stored in b.
    mov b, 24
    mov x, n 
    and c, x, 0xFFFFFFFF00000000
    jnz skip32, c
    shl x, x, 32
    sub b, b, 16
skip32:
    and c, x, 0xFFFF000000000000
    jnz skip16, c
    shl x, x, 16
    sub b, b, 8
skip16:
    and c, x, 0xFF00000000000000
    jnz skip8, c
    shl x, x, 8
    sub b, b, 4
skip8:
    and c, x, 0xF000000000000000
    jnz skip4, c
    shl x, x, 4
    sub b, b, 2
skip4:
    and c, x, 0xC000000000000000
    jnz skip2, c
    shl x, x, 2
    sub b, b, 1
skip2:

    # now we shift x so it's only 12 bits long (the size of our lookup table)
    shr x, x, 52

    # and we store the lookup table value in x
    add x, x, data(lookup_table)
    sub x, x, 2**10
    lbu x, x

    # now we shift x back to the proper size
    shl x, x, b

    # x is now an intial estimate for Newton's method.
    # Since our lookup table is 12 bits, x has at least 6 bits of accuracy
    # So if b <= -2, we're done; else do an iteration of newton
    leq c, b, -2
    jnz end_newton, c
    divu q, r, n, x
    add x, x, q
    shr x, x, 1

    # We now have 12 bits of accuracy; compare b <= 4
    leq c, b, 4
    jnz end_newton, c
    divu q, r, n, x
    add x, x, q
    shr x, x, 1

    # 24 bits, b <= 16
    leq c, b, 16
    jnz end_newton, c
    divu q, r, n, x
    add x, x, q
    shr x, x, 1

    # 48 bits, we're done!

end_newton:

    # x is the (integer) square root of n: test x*x == n
    mulu x, h, x, x
    cmp s, n, x
    halt 0

is_square:
    mov s, 1

not_square:
    halt 0
2012rcampion
fonte
10

Pontuação: 27462

Na hora de competir em um desafio de golfe : 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
orlp
fonte
Se eu roubar sua ideia de pesquisa, minha pontuação cai de 161558 para 47289. Seu algoritmo ainda vence.
Sparr
Você já tentou desenrolar o loop newton? Quantas iterações são necessárias para o pior caso?
Sparr
@Sparr Sim, não é mais rápido desenrolar porque há uma grande variação no número de iterações.
orlp 27/05
ele é concluído em zero ou uma iterações? qual é o max?
Sparr 27/05
A ideia da tabela de pesquisa também estava na resposta stackoverflow.com/a/18686659/4339987 .
lirtosiast
5

Pontuação: 161558 227038 259038 260038 263068

Peguei o algoritmo de raiz quadrada inteira mais rápido que consegui encontrar e retorne se o restante é zero.

# based on http://www.cc.utah.edu/~nahaj/factoring/isqrt.c.html
# converted to GOLF assembly for http://codegolf.stackexchange.com/questions/49356/testing-if-a-number-is-a-square

# unrolled for speed, original source commented out at bottom
start:
    or u, t, 1 << 62
    shr t, t, 1
    gequ v, n, u
    jz nope62, v
    sub n, n, u
    or t, t, 1 << 62
    nope62:

    or u, t, 1 << 60
    shr t, t, 1
    gequ v, n, u
    jz nope60, v
    sub n, n, u
    or t, t, 1 << 60
    nope60:

    or u, t, 1 << 58
    shr t, t, 1
    gequ v, n, u
    jz nope58, v
    sub n, n, u
    or t, t, 1 << 58
    nope58:

    or u, t, 1 << 56
    shr t, t, 1
    gequ v, n, u
    jz nope56, v
    sub n, n, u
    or t, t, 1 << 56
    nope56:

    or u, t, 1 << 54
    shr t, t, 1
    gequ v, n, u
    jz nope54, v
    sub n, n, u
    or t, t, 1 << 54
    nope54:

    or u, t, 1 << 52
    shr t, t, 1
    gequ v, n, u
    jz nope52, v
    sub n, n, u
    or t, t, 1 << 52
    nope52:

    or u, t, 1 << 50
    shr t, t, 1
    gequ v, n, u
    jz nope50, v
    sub n, n, u
    or t, t, 1 << 50
    nope50:

    or u, t, 1 << 48
    shr t, t, 1
    gequ v, n, u
    jz nope48, v
    sub n, n, u
    or t, t, 1 << 48
    nope48:

    or u, t, 1 << 46
    shr t, t, 1
    gequ v, n, u
    jz nope46, v
    sub n, n, u
    or t, t, 1 << 46
    nope46:

    or u, t, 1 << 44
    shr t, t, 1
    gequ v, n, u
    jz nope44, v
    sub n, n, u
    or t, t, 1 << 44
    nope44:

    or u, t, 1 << 42
    shr t, t, 1
    gequ v, n, u
    jz nope42, v
    sub n, n, u
    or t, t, 1 << 42
    nope42:

    or u, t, 1 << 40
    shr t, t, 1
    gequ v, n, u
    jz nope40, v
    sub n, n, u
    or t, t, 1 << 40
    nope40:

    or u, t, 1 << 38
    shr t, t, 1
    gequ v, n, u
    jz nope38, v
    sub n, n, u
    or t, t, 1 << 38
    nope38:

    or u, t, 1 << 36
    shr t, t, 1
    gequ v, n, u
    jz nope36, v
    sub n, n, u
    or t, t, 1 << 36
    nope36:

    or u, t, 1 << 34
    shr t, t, 1
    gequ v, n, u
    jz nope34, v
    sub n, n, u
    or t, t, 1 << 34
    nope34:

    or u, t, 1 << 32
    shr t, t, 1
    gequ v, n, u
    jz nope32, v
    sub n, n, u
    or t, t, 1 << 32
    nope32:

    or u, t, 1 << 30
    shr t, t, 1
    gequ v, n, u
    jz nope30, v
    sub n, n, u
    or t, t, 1 << 30
    nope30:

    or u, t, 1 << 28
    shr t, t, 1
    gequ v, n, u
    jz nope28, v
    sub n, n, u
    or t, t, 1 << 28
    nope28:

    or u, t, 1 << 26
    shr t, t, 1
    gequ v, n, u
    jz nope26, v
    sub n, n, u
    or t, t, 1 << 26
    nope26:

    or u, t, 1 << 24
    shr t, t, 1
    gequ v, n, u
    jz nope24, v
    sub n, n, u
    or t, t, 1 << 24
    nope24:

    or u, t, 1 << 22
    shr t, t, 1
    gequ v, n, u
    jz nope22, v
    sub n, n, u
    or t, t, 1 << 22
    nope22:

    or u, t, 1 << 20
    shr t, t, 1
    gequ v, n, u
    jz nope20, v
    sub n, n, u
    or t, t, 1 << 20
    nope20:

    or u, t, 1 << 18
    shr t, t, 1
    gequ v, n, u
    jz nope18, v
    sub n, n, u
    or t, t, 1 << 18
    nope18:

    or u, t, 1 << 16
    shr t, t, 1
    gequ v, n, u
    jz nope16, v
    sub n, n, u
    or t, t, 1 << 16
    nope16:

    or u, t, 1 << 14
    shr t, t, 1
    gequ v, n, u
    jz nope14, v
    sub n, n, u
    or t, t, 1 << 14
    nope14:

    or u, t, 1 << 12
    shr t, t, 1
    gequ v, n, u
    jz nope12, v
    sub n, n, u
    or t, t, 1 << 12
    nope12:

    or u, t, 1 << 10
    shr t, t, 1
    gequ v, n, u
    jz nope10, v
    sub n, n, u
    or t, t, 1 << 10
    nope10:

    or u, t, 1 << 8
    shr t, t, 1
    gequ v, n, u
    jz nope8, v
    sub n, n, u
    or t, t, 1 << 8
    nope8:

    or u, t, 1 << 6
    shr t, t, 1
    gequ v, n, u
    jz nope6, v
    sub n, n, u
    or t, t, 1 << 6
    nope6:

    or u, t, 1 << 4
    shr t, t, 1
    gequ v, n, u
    jz nope4, v
    sub n, n, u
    or t, t, 1 << 4
    nope4:

    or u, t, 1 << 2
    shr t, t, 1
    gequ v, n, u
    jz nope2, v
    sub n, n, u
    or t, t, 1 << 2
    nope2:

    or u, t, 1 << 0
    shr t, t, 1
    gequ v, n, u
    jz nope0, v
    sub n, n, u
    nope0:

end:
    not s, n        # return !remainder
    halt 0


# before unrolling...
#
# start:
#     mov b, 1 << 62  # squaredbit = 01000000...
# loop:               # do {
#     or u, b, t      #   u = squaredbit | root
#     shr t, t, 1     #   root >>= 1
#     gequ v, n, u    #   if remainder >= u:
#     jz nope, v
#     sub n, n, u     #       remainder = remainder - u
#     or t, t, b      #       root = root | squaredbit
# nope:
#     shr b, b, 2     #   squaredbit >>= 2
#     jnz loop, b      # } while (squaredbit > 0)
# end:
#     not s, n        # return !remainder
#     halt 0

EDIT 1: teste de quadratura removido, retorne! O restante diretamente, economize 3 ops por teste

EDIT 2: use n como o restante diretamente, economize 1 op por teste

EDIT 3: simplificou a condição do loop, economize 32 ops por teste

EDIT 4: desenrolou o loop, economize cerca de 65 operações por teste

Sparr
fonte
11
Você pode usar expressões completos Python em instruções, para que possa escrever 0x4000000000000000como 1 << 62:)
orlp
3

Pontuação: 344493

Faz uma pesquisa binária simples dentro do intervalo [1, 4294967296)para aproximar sqrt(n)e verifica se né um quadrado perfeito.

mov b, 4294967296
mov c, -1

lesser:
    add a, c, 1

start:
    leu k, a, b
    jz end, k

    add c, a, b
    shr c, c, 1

    mulu d, e, c, c

    leu e, d, n
    jnz lesser, e
    mov b, c
    jmp start

end:
    mulu d, e, b, b
    cmp s, d, n

    halt 0
es1024
fonte
Boa resposta inicial! Você tem algum feedback sobre a programação na montagem do GOLF , as ferramentas que criei para o GOLF ou o desafio? Este tipo de desafio é muito novo, e eu estou ansioso para ouvir o feedback :)
orlp
Sua resposta está grampeada para n = 0, infelizmente, 0 é 0 quadrado :)
orlp
@orlp corrigido para n = 0. Além disso, sugiro adicionar uma instrução para imprimir o valor de um registro no meio da execução, o que poderia facilitar a depuração de programas GOLF .
es1024
Não vou adicionar essa instrução (isso significaria que os desafios precisam adicionar regras extras sobre instruções de depuração não permitidas); em vez disso, tenho a depuração interativa planejada, com pontos de interrupção e exibindo todo o conteúdo do registro.
orlp
talvez você possa acelerar isso ponderando sua pesquisa binária para pousar em outro lugar que não seja o ponto médio. a média geométrica dos dois valores, talvez?
Sparr