Tolong jangan bercabang

14

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 - 5juga 4294967294, bahkan sebagai bagian dari pernyataan yang lebih besar.

Tugas 1: Maks

Dua nilai, Adan B, ada dalam ruang lingkup, membuat RESULTvariabel berisi nilai-nilai terbesar saat program berakhir.

Tugas 2: Median

Tiga nilai, A, Bdan C, ada di ruang lingkup, membuat RESULTvariabel mengandung median dari nilai-nilai ketika program berakhir.

Tugas 3: Root kuadrat

Satu nilai,, Aada dalam lingkup, membuat RESULTvariabel 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.

aaaaaaaaaaaa
sumber
Di mana operator unary? Saya tidak peduli -tetapi ~bisa bersikap baik (bahkan jika saya tidak tahu untuk apa).
John Dvorak
Tentu, 0xFFFF_FFFF_FFFF_FFFF ^ xdan 0 - x. Bagaimana saya bisa lupa?
John Dvorak
@JanDvorak Hal itu membuat deskripsi singkat, untuk logika kelengkapan tidak !juga cukup sepele: x == 0.
aaaaaaaaaaaa
Apa perilaku pembagian dengan nol?
John Dvorak
Dalam Mathematica (a> b) mengembalikan Benar atau Salah. Boole mengkonversi False menjadi 0 dan True ke 1. Apakah legal untuk digunakan Boole[a-b]?
DavidC

Jawaban:

5

Tugas 3, 23 ops

x = (A >> 16) + A / ((A >> 13) + 511) + 15
x = (x + A/x) >> 1
x = (x + A/x) >> 1
x = (x + A/x) >> 1
RESULT = x - (x > A/x)

Menggunakan metode Newton, seperti solusi lainnya, dengan benih yang lebih dipilih secara bijaksana. Bit pertama A >> 16membuat bagian atas rentang senang, bit kedua A / ((A >> 13) + 511)membuat bagian tengah kisaran senang, dan bit terakhir 15bagian bawah, dan juga mencegah pembagian dengan kesalahan nol (15 adalah nilai terbesar yang memungkinkan 0untuk melakukan konvergensi dengan benar - membagi dua koreksi minus tiga kali sama dengan nol). Untuk nilai input 225, 275625, 82137969, 2908768489(dan nilai terdekat), seed awal tepat. Semua case edge (kotak sempurna, kotak sempurna + 1, dan kotak sempurna - 1) pada kisaran 0 .. 2**32-1telah 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:

x = x * (3*A + x*x) / (A + 3*x*x)

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*xakan 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:

x = x + x*(v - x**n)/(v*n)
x = (x*(n+1) - x**(n+1)/v)/n
x = ((n-2)*x + (4*v*x)/(v + x**n))/n
x = x*((n+2)*v + (n-2)*x**n)/(v + x**n)/n
x = ((n-2)*x + (n*x*v)/(v + (n-1)*x**n))/(n-1)
x = ((n-2)*x + x*((n*2-1)*v + x**n)/(v + (n*2-1)*x**n))/(n-1)

x = x + 2*x*(v - x**n)/(v + x**n)/n
x = x + x*31*(v - x**n)/(10*v + 21*x**n)/n
x = x + x*561*(v - x**n)/(181*v + 380*x**n)/n
x = x + x*1153*(v - x**n)/(372*v + 781*x**n)/n

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.

primo
sumber
Cukup bagus, tetapi gagal untuk 4294967295. Adapun aturannya, mereka harus ketat untuk membuatnya menarik. Anda dapat memperdebatkan premis apa yang membuat tantangan terbaik, tetapi pada akhirnya jauh lebih penting bahwa aturannya jelas dan tidak ambigu, daripada apa yang sebenarnya mereka izinkan.
aaaaaaaaaaaa
Saya tidak berpikir Halley akan tetap layak, dari perkiraan jauh itu akan meningkat sedikit kurang dari faktor 3, Newton melakukan sedikit kurang dari faktor 2. Demikian pula dari tebakan yang baik Halley akan tiga kali lipat akurasinya, Newton akan menggandakannya. Jadi satu iterasi Halley bernilai iterasi yang persis sama dengan log(3)/log(2) ~= 1.585Newton.
aaaaaaaaaaaa
@ eBusiness Saya awalnya memiliki 2 Halley's dengan benih yang dipilih sama dengan total 25 ops - dengan kesalahan saat 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.
primo
@eBusiness diperbaiki.
primo
Akar kuadrat terkecil dari paket itu, pekerjaan yang bagus, dan lencana kemenangan resmi.
aaaaaaaaaaaa
5

65 (61) operasi (5 + 13 + 47 (43))

Tugas 1 - Max (A, B)

RESULT = A + (B - A) * (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)

RESULT = A                               \
       + (B - A) * (A > B) ^ (B <= C)    \
       + (C - A) * (A > C) ^ (C <  B)

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)

X1     = 1024 + A / 2048
X2     = (X1  + A / X1 ) / 2
...
X10    = (X9 + A / X9 ) / 2
RESULT = X16 - (X16 * X16 > 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.

John Dvorak
sumber
Saya pikir baris pertama dari Tugas 3 tidak benar: konstanta kedua harus 4 kali konstanta pertama (untuk memiliki "murni" Newton).
Reinstate Monica
@ Wolfolf Tebak awal yang lebih baik mungkin menjelaskan mengapa saya membuang-buang siklus. Di mana Anda datang dengan 4 *? Ini terlihat seperti dua iterasi yang digulung menjadi satu.
John Dvorak
(1024 + A/1024)/2 == (512 + A/2048)(yang seperti X0 = 1024, dan kemudian mulai Newton).
Reinstate Monica
Solusi yang bagus untuk Tugas 1. Telur Columbus.
DavidC
@ DavidVarraher tentu saja, solusi yang tepat adalah MOV RESULT, A; CMP A,B; CMOVA RESULT, B;-)
John Dvorak
5

1: 5 operator

RESULT = B ^ (A ^ B)*(A > B)

2: 13 operator

RESULT = B ^ (A ^ B)*(A > B) ^ (A ^ C)*(A > C) ^ (B ^ C)*(B > C)

3: 27 operator

g = 47|((0x00ffffff & A)>>10)|(A>>14)
r = (g + A/g)/3
r = (r + A/r)>>1
r = (r + A/r)>>1
r = (r + A/r)>>1
RESULT = r - (r*r-1>=A)
aaaaaaaaaaaa
sumber
5

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 hak RESULTuntuk A=0(yang tidak akan menjadi kasus untuk 1024bukannya 1022).

r = (511 + A/2044)
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
r = (r + A/r) / 2
RESULT = r - (r > A/r)
Pasang kembali Monica
sumber
Haruskah saya menyimpan salinan metode newton saya yang lebih rendah yang dioptimalkan secara paralel dengan Anda dan memposting waktu yang layak nanti? Pikiran yang hebat berpikir sama dan memiliki solusi yang terbagi menjadi dua jawaban itu buruk, tetapi itulah keadaan saat ini, karena Anda belum menjawab # 2.
John Dvorak
@ JanDvorak: Terima kasih telah bertanya. Tidak apa-apa jika Anda memasukkan metode saya yang sedikit lebih pendek ke dalam jawaban Anda. Juga, terima kasih telah memberikan kredit kepada saya :-)
Reinstate Monica
Percobaan yang bagus, tetapi gagal untuk input 4294965360 hingga 4294967295.
aaaaaaaaaaaa
@eBusiness: Apa hasil yang Anda dapatkan dari input tersebut? Saya mendapatkan 65535 dalam tes saya, yang OK.
Reinstate Monica
Saya mendapatkan 65.536. Mungkin Anda tidak menggunakan format integer yang ditentukan.
aaaaaaaaaaaa