Escriba un programa de ensamblaje GOLF que, dado un entero sin signo de 64 bits en el registro, n
ponga un valor distinto de cero en el registro s
si n
es un cuadrado, de lo contrario, 0
en s
.
Su binario GOLF (después del ensamblaje) debe caber en 4096 bytes.
Su programa se puntuará utilizando el siguiente programa Python3 (que debe colocarse dentro del directorio 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)
Asegúrese de actualizar GOLF a la última versión con git pull
. Ejecute el programa de puntuación usando python3 score.py your_source.golf
.
Utiliza una semilla estática para generar un conjunto de números de los cuales aproximadamente 1/16 es cuadrado. La optimización hacia este conjunto de números está en contra del espíritu de la pregunta, puedo cambiar la semilla en cualquier momento. Su programa debe funcionar para cualquier número de entrada de 64 bits no negativo, no solo estos.
La puntuación más baja gana.
Como GOLF es muy nuevo, incluiré algunos consejos aquí. Debe leer la especificación GOLF con todas las instrucciones y los costos del ciclo . En el repositorio de Github se pueden encontrar programas de ejemplo.
Para pruebas manuales, compile su programa en un binario ejecutando python3 assemble.py your_source.golf
. Luego ejecute su programa usando python3 golf.py -p s your_source.bin n=42
, esto debería iniciar el programa con el n
conjunto a 42, e imprime el registro s
y el conteo de ciclos después de salir. Vea todos los valores de los contenidos del registro a la salida del programa con la -d
bandera - use --help
para ver todas las banderas.
git pull
. Encontré un error en el operando de desplazamiento a la izquierda donde no se ajustaba correctamente.Respuestas:
Puntuación: 22120 (3414 bytes)
Mi solución utiliza una tabla de búsqueda de 3kB para sembrar un solucionador de métodos de Newton que se ejecuta de cero a tres iteraciones dependiendo del tamaño del resultado.
fuente
Puntuación: 27462
Ya era hora de competir en un desafío de GOLF : D
fuente
Puntuación: 161558
227038259038260038263068Tomé el algoritmo de raíz cuadrada entera más rápido que pude encontrar y devolví si su resto es cero.
EDITAR 1: eliminó la prueba de cuadratura, devuelve el resto directamente, ahorre 3 operaciones por prueba
EDIT 2: usa n como el resto directamente, ahorra 1 operación por prueba
EDITAR 3: simplificó la condición del bucle, ahorre 32 operaciones por prueba
EDIT 4: desenrolla el bucle, ahorra alrededor de 65 operaciones por prueba
fuente
0x4000000000000000
como1 << 62
:)Puntuación: 344493
Hace una búsqueda binaria simple dentro del intervalo
[1, 4294967296)
para aproximarsesqrt(n)
, luego verifica sin
es un cuadrado perfecto.fuente