Напишите программу сборки GOLF , в которой 64-разрядное целое число без знака в регистре n
помещает ненулевое значение в регистр, s
если n
является квадратом, в противном случае - 0
в s
.
Ваш бинарный файл GOLF (после сборки) должен умещаться в 4096 байт.
Ваша программа будет оценена с использованием следующей программы Python3 (которая должна быть помещена в каталог 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)
Обязательно обновите GOLF до последней версии с git pull
. Запустите программу оценки, используя python3 score.py your_source.golf
.
Он использует статическое начальное число для генерации набора чисел, из которых примерно 1/16 является квадратом. Оптимизация в отношении этого набора чисел противоречит духу вопроса, я могу изменить семя в любой момент. Ваша программа должна работать с любым неотрицательным 64-битным входным числом, а не только с этим.
Самый низкий балл побеждает.
Так как GOLF очень новый, я включу несколько указателей здесь. Вы должны прочитать в ГОЛЬФ спецификацию со всеми инструкциями и расходов цикла . В репозитории Github можно найти примеры программ.
Для ручного тестирования скомпилируйте вашу программу в двоичный файл, запустив python3 assemble.py your_source.golf
. Затем запустите вашу программу с помощью python3 golf.py -p s your_source.bin n=42
, это должно запустить программу с n
установленным на 42, и печатает регистрs
и количество циклов после выхода. Просмотреть все значения содержимого регистра при выходе из программы с -d
флагом - используйте --help
для просмотра всех флагов.
git pull
. Я обнаружил ошибку в операнде левого сдвига, когда он неправильно переносился.Ответы:
Оценка: 22120 (3414 байт).
Мое решение использует таблицу поиска 3 КБ для заполнения решателя методов Ньютона, который выполняется от нуля до трех итераций в зависимости от размера результата.
источник
Счет: 27462
О времени, когда я буду соревноваться в игре в гольф : D
источник
Счет: 161558
227038259038260038263068Я взял самый быстрый алгоритм целочисленного квадратного корня, который я смог найти, и вернул, равен ли его остаток нулю.
РЕДАКТИРОВАТЬ 1: удален квадратный тест, вернуть! Остаток напрямую, сохранить 3 операции за тест
РЕДАКТИРОВАТЬ 2: использовать n как остаток непосредственно, сохранить 1 операцию на тест
РЕДАКТИРОВАТЬ 3: упростил условие цикла, сохранить 32 операции за тест
РЕДАКТИРОВАТЬ 4: развернул цикл, сэкономить около 65 операций на тест
источник
0x4000000000000000
как1 << 62
:)Счет: 344493
Выполняет простой двоичный поиск в интервале
[1, 4294967296)
для аппроксимацииsqrt(n)
, а затем проверяет,n
является ли квадрат идеальным.источник