Tulis program perakitan GOLF yang memberikan bilangan bulat unsigned 64-bit dalam register n
memberikan nilai bukan nol ke dalam register s
jika n
berbentuk bujur sangkar, sebaliknya 0
ke dalam s
.
Biner GOLF Anda (setelah perakitan) harus sesuai dengan 4096 byte.
Program Anda akan dinilai menggunakan program Python3 berikut (yang harus dimasukkan ke dalam direktori 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)
Pastikan untuk memperbarui GOLF ke versi terbaru dengan git pull
. Jalankan program skor menggunakan python3 score.py your_source.golf
.
Ia menggunakan seed statis untuk menghasilkan sekumpulan angka yang kira-kira 1/16 persegi. Optimalisasi terhadap serangkaian angka ini bertentangan dengan semangat pertanyaan, saya dapat mengubah seed kapan saja. Program Anda harus bekerja untuk semua nomor input 64-bit non-negatif, bukan hanya ini.
Skor terendah menang.
Karena GOLF sangat baru, saya akan memasukkan beberapa petunjuk di sini. Anda harus membaca dengan GOLF spesifikasi dengan semua instruksi dan biaya siklus . Dalam repositori contoh program Github dapat ditemukan.
Untuk pengujian manual, kompilasi program Anda ke biner dengan menjalankan python3 assemble.py your_source.golf
. Kemudian jalankan program Anda menggunakan python3 golf.py -p s your_source.bin n=42
, ini harus memulai program dengan n
set ke 42, dan mencetak register s
dan jumlah siklus setelah keluar. Lihat semua nilai isi register di program keluar dengan -d
bendera - gunakan --help
untuk melihat semua bendera.
git pull
. Saya menemukan bug di operan pergeseran kiri di mana itu tidak dibungkus dengan benar.Jawaban:
Nilai: 22120 (3414 bytes)
Solusi saya menggunakan tabel pencarian 3kB untuk seed pemecah metode Newton yang berjalan untuk nol hingga tiga iterasi tergantung pada ukuran hasilnya.
sumber
Nilai: 27462
Tentang waktu saya akan bersaing dalam tantangan GOLF : D
sumber
Nilai: 161558
227038259038260038263068Saya mengambil algoritma root integer kuadrat tercepat yang dapat saya temukan dan mengembalikan apakah sisanya nol.
EDIT 1: tes kuadrat dihapus, langsung kembali! Sisanya, menghemat 3 ops per tes
EDIT 2: gunakan n sebagai sisanya secara langsung, simpan 1 op per tes
EDIT 3: menyederhanakan kondisi loop, menghemat 32 ops per tes
EDIT 4: membuka gulungannya, menghemat sekitar 65 ops per tes
sumber
0x4000000000000000
sebagai1 << 62
:)Nilai: 344493
Lakukan pencarian biner sederhana dalam interval
[1, 4294967296)
untuk perkiraansqrt(n)
, lalu periksa apakahn
kuadrat sempurna.sumber