Tulis program perakitan GOLF yang bertuliskan integer dari stdin (diikuti oleh trailing newline), dan output faktor prima yang dipisahkan oleh newlines, diikuti oleh trailing newline di stdout.
Faktor utama tidak harus dalam urutan tertentu. 1
bukan faktor utama.
Biner GOLF Anda (setelah perakitan) harus sesuai dengan 8192 byte.
Program Anda akan dinilai dengan menjalankannya 10 kali, masing-masing dengan salah satu dari input berikut:
8831269065180497
2843901546547359024
6111061272747645669
11554045868611683619
6764921230558061729
16870180535862877896
3778974635503891117
204667546124958269
16927447722109721827
9929766466606501253
Angka-angka ini diurutkan secara kasar dalam hal kesulitan. Yang pertama harus dengan mudah dipecahkan oleh divisi percobaan.
Optimalisasi terhadap rangkaian angka ini bertentangan dengan semangat pertanyaan, saya dapat mengubah set angka di titik mana pun. Program Anda harus bekerja untuk semua nomor input 64-bit yang positif, bukan hanya ini.
Skor Anda adalah jumlah siklus CPU yang digunakan untuk memperhitungkan angka-angka di atas.
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. Khususnya lihat contoh program faktorial , yang menunjukkan input / output.
Kompilasi program Anda ke biner dengan menjalankan python3 assemble.py your_source.golf
. Kemudian jalankan program Anda menggunakan python3 golf.py your_source.bin
, ini harus mencetak jumlah siklus juga. Lihat nilai isi register pada saat keluar dari program dengan -d
flag - gunakan --help
untuk melihat semua flag.
1
bukan merupakan faktor utama, haruskah hanya mencetak bilangan bulat input?Jawaban:
2.279.635 siklus — 7373 byte (deterministik)
Satu per satu:
Ringkasan:
Saya menggunakan kombinasi divisi percobaan dan algoritma Brent-Pollard rho untuk faktorisasi, dan pencarian tabel plus Miller-Rabin untuk pengujian primality. Saya akan menambahkan beberapa penjelasan lagi besok.
Perhatikan bahwa karena batas karakter pada panjang posting, tabel data kedua terpotong. Inti ini termasuk tabel lengkap.
sumber
mov o, 42
adalah hadiah mati.Total 36.757.269.913 siklus
830B dirakit
Faktorisasi oleh divisi percobaan, dengan beberapa optimasi. Mungkin bukan yang tercepat, tetapi karena belum ada yang memposting, saya akan memulai.
Output penuh dari loop waktu saya, kalau-kalau ada yang ingin memeriksa hasil dan / atau copy-paste dan matematika saya.
sumber
divu
: stackoverflow.com/questions/5558492/… . Adapun jawaban Anda - pertanyaan ini tidak dimaksudkan untuk diselesaikan dengan menggunakan divisi percobaan: Pfactor * factor < number
- tidak ada angka yang dapat memiliki faktor lebih besar dari akar kuadrat.skor = 378.867.816 siklus
[acak - hasil Anda dapat bervariasi]
Menggunakan uji primitif Miller-Rabin (versi deterministik yang dapat menangani hingga 2 ^ 64), sedikit anjak percobaan, dan anjak ECM . Semua operasi aljabar ada di sana, termasuk penambahan modular, pengurangan, multiplikasi, eksponensial, dan inversi (mod n <2 ^ 64).
Penggandaan modular adalah suboptimal - ia melakukan pencarian biner untuk hasil bagi. Menghitung sisa dari 128 dengan 64 membagi itu sulit tanpa instruksi bawaan yang cocok. Percepat itu dan semuanya akan berjalan lebih cepat.
2290 byte dikompilasi
Keluaran:
sumber