John Carmack memiliki fungsi khusus dalam kode sumber Quake III yang menghitung akar kuadrat terbalik dari pelampung, 4x lebih cepat dari biasanya (float)(1.0/sqrt(x))
, termasuk 0x5f3759df
konstanta ganjil . Lihat kode di bawah ini. Dapatkah seseorang menjelaskan baris demi baris apa yang sebenarnya terjadi di sini dan mengapa ini bekerja jauh lebih cepat daripada penerapan biasa?
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) );
#ifndef Q3_VM
#ifdef __linux__
assert( !isnan(y) );
#endif
#endif
return y;
}
Jawaban:
FYI. Carmack tidak menulisnya. Terje Mathisen dan Gary Tarolli sama-sama menganggapnya sebagian (dan sangat sederhana), serta memuji beberapa sumber lain.
Bagaimana konstanta mitos diturunkan adalah suatu misteri.
Mengutip Gary Tarolli:
Konstanta yang sedikit lebih baik, dikembangkan oleh ahli matematika ahli (Chris Lomont) yang mencoba mencari tahu bagaimana algoritme asli bekerja adalah:
Terlepas dari ini, percobaan awalnya versi matematis 'superior' dari id's sqrt (yang datang ke konstanta yang hampir sama) terbukti lebih rendah dari yang awalnya dikembangkan oleh Gary meskipun secara matematis jauh lebih 'murni'. Dia tidak bisa menjelaskan mengapa id sangat bagus.
sumber
Tentu saja saat ini, ternyata jauh lebih lambat daripada hanya menggunakan sqrt FPU (terutama pada 360 / PS3), karena pertukaran antara register float dan int menginduksi load-hit-store, sedangkan unit floating point dapat melakukan reciprocal square root di perangkat keras.
Ini hanya menunjukkan bagaimana pengoptimalan harus berkembang seiring dengan perubahan sifat perangkat keras yang mendasarinya.
sumber
Greg Hewgill dan IllidanS4 memberikan tautan dengan penjelasan matematika yang sangat baik. Saya akan mencoba merangkumnya di sini untuk mereka yang tidak ingin membahas terlalu banyak detail.
Fungsi matematika apa pun, dengan beberapa pengecualian, dapat diwakili oleh jumlah polinomial:
bisa persis diubah menjadi:
Dimana a0, a1, a2, ... adalah konstanta . Masalahnya adalah bahwa untuk banyak fungsi, seperti akar kuadrat, untuk nilai yang tepat jumlah ini memiliki jumlah anggota yang tidak terbatas, tidak berakhir pada beberapa x ^ n . Tetapi, jika kita berhenti di beberapa x ^ n kita masih akan mendapatkan hasil yang cukup presisi.
Jadi, jika kita memiliki:
Dalam kasus khusus ini, mereka memutuskan untuk membuang semua anggota polinom di atas detik, mungkin karena kecepatan penghitungan:
Dan sekarang tugasnya adalah menghitung a0 dan a1 agar y memiliki perbedaan terkecil dari nilai pastinya. Mereka telah menghitung bahwa nilai yang paling tepat adalah:
Jadi, saat Anda memasukkan ini ke dalam persamaan, Anda mendapatkan:
Yang sama dengan baris yang Anda lihat di kode:
Sunting: sebenarnya di sini
y = 0x5f375a86 - 0.5*x
tidak sama dengani = 0x5f375a86 - (i >> 1);
karena menggeser pelampung karena bilangan bulat tidak hanya membagi dua tetapi juga membagi eksponen dua dan menyebabkan beberapa artefak lainnya, tetapi masih turun untuk menghitung beberapa koefisien a0, a1, a2 ....Pada titik ini mereka telah menemukan bahwa ketepatan hasil ini tidak cukup untuk tujuan tersebut. Jadi mereka juga hanya melakukan satu langkah dari iterasi Newton untuk meningkatkan akurasi hasil:
Mereka bisa melakukan beberapa iterasi lagi dalam satu lingkaran, masing-masing meningkatkan hasil, sampai akurasi yang dibutuhkan terpenuhi. Inilah cara kerjanya di CPU / FPU! Tapi sepertinya hanya satu iterasi saja yang cukup, yang juga merupakan berkah untuk kecepatannya. CPU / FPU melakukan iterasi sebanyak yang diperlukan untuk mencapai akurasi angka floating point tempat hasil disimpan dan memiliki algoritme yang lebih umum yang berfungsi untuk semua kasus.
Jadi singkatnya, yang mereka lakukan adalah:
Gunakan (hampir) algoritme yang sama dengan CPU / FPU, manfaatkan peningkatan kondisi awal untuk kasus khusus 1 / sqrt (x) dan jangan menghitung sepenuhnya ke presisi CPU / FPU akan pergi tetapi berhenti lebih awal, jadi mendapatkan kecepatan kalkulasi.
sumber
Menurut artikel bagus ini yang ditulis beberapa waktu lalu ...
Bacaan yang sangat bagus. Ini hanya sebagian kecil saja.
sumber
Saya ingin tahu apa konstanta itu sebagai pelampung jadi saya cukup menulis sedikit kode ini dan mencari bilangan bulat yang muncul di Google.
Sepertinya konstanta adalah "Perkiraan bilangan bulat ke akar kuadrat 2 ^ 127 yang lebih dikenal dengan bentuk heksadesimal dari representasi titik mengambangnya, 0x5f3759df" https://mrob.com/pub/math/numbers-18.html
Di situs yang sama itu menjelaskan semuanya. https://mrob.com/pub/math/numbers-16.html#le009_16
sumber