Siapa pun yang sedang dalam optimalisasi kode tingkat rendah tahu tentang bahaya percabangan, baik itu diimplementasikan sebagai jika-pernyataan, loop atau pilih-pernyataan kemungkinan salah prediksi cabang adalah hal yang membuang-buang waktu yang mengerikan.
Masalah sederhana dapat diselesaikan lebih baik dengan aritmatika sederhana, jadi mari kita lakukan itu.
Untuk masalah-masalah berikut, semua variabel adalah bilangan bulat 32 bit yang tidak ditandai dan satu-satunya kode yang diperbolehkan adalah pernyataan himpunan sederhana yang hanya melibatkan operator berikut:
+ addition
- subtraction
* multiplication
/ integer division, rounds down, division by 0 not allowed
% modulo
& binary and
| binary or
^ binary exclusive or
>> bitshift right
<< bitshift left
Logic operators, return 1 if the expression is true and 0 if it is false.
== equal
!= not equal
< less than
<= less than or equal
> greater than
>= greater than or equal
Set operator
=
Setiap baris harus terdiri dari pengenal variabel diikuti oleh operator yang ditetapkan, diikuti oleh ekspresi.
Ekspresi mungkin tidak mengandung operator set tambahan, tetapi dapat berisi pengidentifikasi variabel, angka literal dan tanda kurung.
Skor golf hanya akan menghitung jumlah operator.
Contoh:
myvar = ( ( ( foo + 5 ) * bar ) % 7 ) == 3
Memiliki skor 5 operator.
Suatu solusi dapat mencakup banyak variabel sesuai keinginan penulis.
Variabel yang belum disetel memiliki nilai 0
.
Overflow dan underflow diperbolehkan, semua angka negatif underflow, demikian 3 - 5
juga 4294967294
, bahkan sebagai bagian dari pernyataan yang lebih besar.
Tugas 1: Maks
Dua nilai, A
dan B
, ada dalam ruang lingkup, membuat RESULT
variabel berisi nilai-nilai terbesar saat program berakhir.
Tugas 2: Median
Tiga nilai, A
, B
dan C
, ada di ruang lingkup, membuat RESULT
variabel mengandung median dari nilai-nilai ketika program berakhir.
Tugas 3: Root kuadrat
Satu nilai,, A
ada dalam lingkup, membuat RESULT
variabel berisi akar kuadrat A
, dibulatkan ke bawah, ketika program berakhir.
Tidak apa-apa untuk mengirim jawaban hanya satu atau dua pertanyaan, bagi sebagian dari Anda hanya menemukan solusi yang valid akan menjadi tantangan.
sumber
-
tetapi~
bisa bersikap baik (bahkan jika saya tidak tahu untuk apa).0xFFFF_FFFF_FFFF_FFFF ^ x
dan0 - x
. Bagaimana saya bisa lupa?!
juga cukup sepele:x == 0
.Boole[a-b]
?Jawaban:
Tugas 3, 23 ops
Menggunakan metode Newton, seperti solusi lainnya, dengan benih yang lebih dipilih secara bijaksana. Bit pertama
A >> 16
membuat bagian atas rentang senang, bit keduaA / ((A >> 13) + 511)
membuat bagian tengah kisaran senang, dan bit terakhir15
bagian bawah, dan juga mencegah pembagian dengan kesalahan nol (15 adalah nilai terbesar yang memungkinkan0
untuk melakukan konvergensi dengan benar - membagi dua koreksi minus tiga kali sama dengan nol). Untuk nilai input225, 275625, 82137969, 2908768489
(dan nilai terdekat), seed awal tepat. Semua case edge (kotak sempurna, kotak sempurna + 1, dan kotak sempurna - 1) pada kisaran0 .. 2**32-1
telah diuji dan sudah benar.Beberapa komentar tentang aturan:
Overflow dan underflow diperbolehkan, semua angka negatif underflow, jadi 3 - 5 adalah 4294967294, bahkan sebagai bagian dari pernyataan yang lebih besar .
Bit terakhir itu ternyata adalah pembunuh inovasi. Saya awalnya mencoba solusi menggunakan bentuk umum dari metode Halley , tetapi menyadari bahwa itu tidak valid mengingat pembatasan di atas. Iterasi (sebagaimana diterapkan pada akar kuadrat) adalah ini:
Iterasi ini memiliki kualitas bagus yang tidak dimiliki Newton. Ia menyatu secara kubik (bukan secara kuadratik), menyatu dari atas atau bawah (bukan hanya dari atas), dan tidak peka terhadap benih yang dipilih secara buruk (jika iterasi Newton diberikan benih yang terlalu rendah, ia akan sangat-menembak titik konvergensi, dan kemudian perlu bekerja kembali).
Metode Newton juga memiliki masalah (setidaknya ketika berhadapan dengan bilangan bulat) bahwa ia akan cukup sering mencapai x sehingga A / x - x = 2 - dalam hal ini, ia akan konvergen ke nilai yang lebih besar dari akar integer yang tepat, yang perlu diperbaiki untuk; Metode Halley tidak perlu koreksi seperti itu. Namun sayangnya, nilai
3*A + x*x
akan cukup sering lebih besar dari ruang integer yang diizinkan 32-bit.Ada sejumlah umum n lainnya th algoritma root, tetapi mereka semua berbagi karakteristik yang sama:
dll. Sebagian besar menampilkan konvergensi kubik atau kuadratik. Empat yang terakhir adalah bagian dari serangkaian iterasi yang bertemu pada konvergensi kuartik. Tetapi dalam praksis, metode Newton akan memberi Anda apa yang Anda butuhkan dengan operasi yang lebih sedikit, kecuali jika Anda perlu menghitung ratusan digit.
sumber
log(3)/log(2) ~= 1.585
Newton.A = 0
- jadi ini sebenarnya lebih pendek. Tentang 4294967295 , itu adalah kekhilafan: karena 65536² ≡ 0 , iterasi koreksi gagal untuk mengoreksi. Saya akan melihat apakah saya dapat menemukan alternatif.65 (61) operasi (5 + 13 + 47 (43))
Tugas 1 - Max (A, B)
Ini adalah solusi yang jelas. Anda perlu penugasan, Anda perlu perbandingan, Anda perlu mengalikan perbandingan dengan sesuatu, multiplikasi dan tidak bisa menjadi salah satu variabel dan produk tidak bisa menjadi hasilnya.
Tugas 2 - Pertengahan (A, B, C)
Ini adalah peningkatan dibandingkan solusi 15-op saya sebelumnya, yang mengkondisikan ketiga variabel - ini menghemat dua pengurangan, tetapi memperkenalkan tes sentralitas lain. Tes itu sendiri sederhana: sebuah elemen berada di tengah jika tepat satu dari dua lainnya berada di atas.
Tugas 3 - sqrt (A)
Sebelas putaran pendekatan newton. Konstanta ajaib 1024 sudah dikalahkan oleh WolframW (dan 512 menyebabkan pembagian dengan nol untuk a = 0 sebelum a = 2 ** 32 konvergen), tetapi jika kita dapat mendefinisikan 0/0 sebagai nol, sepuluh iterasi akan bekerja dengan nilai awal dari 512. Saya mengakui bahwa klaim saya tentang sepuluh iterasi tidak sepenuhnya bersih, tetapi saya masih mengklaimnya dalam tanda kurung.
Saya harus menyelidiki apakah sembilan itu mungkin.Solusi WolframH adalah sembilan iterasi.sumber
(1024 + A/1024)/2 == (512 + A/2048)
(yang sepertiX0 = 1024
, dan kemudian mulai Newton).MOV RESULT, A; CMP A,B; CMOVA RESULT, B
;-)1: 5 operator
2: 13 operator
3: 27 operator
sumber
Tugas 3, 39 Operasi
EDIT: Mengubah baris terakhir; lihat komentar.
Ini adalah implementasi dari metode Newthon. Diuji dengan semua kotak positif, dan juga dengan kotak positif minus satu, dan juga satu juta angka acak dalam kisaran dari 0 hingga 2 ^ 32-1. Nilai awal yang tampaknya lucu adalah kependekan
(1022 + A/1022) / 2
, yang membutuhkan jumlah iterasi paling sedikit (saya pikir), dan juga membuat hakRESULT
untukA=0
(yang tidak akan menjadi kasus untuk1024
bukannya1022
).sumber