Escreva um programa de montagem GOLF que, dado um número inteiro não assinado de 64 bits, registre n
um valor diferente de zero no registrador, s
se n
for um quadrado, caso contrário, 0
em 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 n
42, e imprime o registro s
e 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 -d
sinalizador - use --help
para ver todos os sinalizadores.
git pull
. Encontrei um bug no operando à esquerda, que não era encapsulado corretamente.Respostas:
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.
fonte
Pontuação: 27462
Na hora de competir em um desafio de golfe : D
fonte
Pontuação: 161558
227038259038260038263068Peguei o algoritmo de raiz quadrada inteira mais rápido que consegui encontrar e retorne se o restante é zero.
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
fonte
0x4000000000000000
como1 << 62
:)Pontuação: 344493
Faz uma pesquisa binária simples dentro do intervalo
[1, 4294967296)
para aproximarsqrt(n)
e verifica sen
é um quadrado perfeito.fonte