Akar Kuadrat Terbalik Cepat yang Tidak Biasa dari John Carmack (Quake III)

112

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 0x5f3759dfkonstanta 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;
}
Alex
sumber
10
Ini telah ditulis berkali-kali. Lihat: google.com/search?q=0x5f3759df
Greg Hewgill
15
Terimakasih Meskipun. Ini adalah pertanyaan yang jauh lebih menarik daripada "bagaimana Anda membuat bilangan positif menjadi negatif di C #?"
MusiGenesis
7
Sialan, ini hanya peretasan berdasarkan metode newton, ini bukan cawan suci dari algoritma, berhenti membicarakannya
mohon

Jawaban:

75

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:

Yang sebenarnya melakukan perhitungan floating point dalam bilangan bulat - butuh waktu lama untuk mencari tahu bagaimana dan mengapa ini bekerja, dan saya tidak dapat mengingat detailnya lagi.

Konstanta yang sedikit lebih baik, dikembangkan oleh ahli matematika ahli (Chris Lomont) yang mencoba mencari tahu bagaimana algoritme asli bekerja adalah:

float InvSqrt(float x)
{
    float xhalf = 0.5f * x;
    int i = *(int*)&x;              // get bits for floating value
    i = 0x5f375a86 - (i >> 1);      // gives initial guess y0
    x = *(float*)&i;                // convert bits back to float
    x = x * (1.5f - xhalf * x * x); // Newton step, repeating increases accuracy
    return x;
}

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.

Rushyo
sumber
4
Apa yang dimaksud dengan "lebih murni secara matematis"?
Tara
1
Saya membayangkan di mana tebakan pertama dapat diturunkan dari konstanta yang dapat dibenarkan, alih-alih tampak sewenang-wenang. Meskipun jika Anda menginginkan deskripsi teknis, Anda dapat mencarinya. Saya bukan ahli matematika, dan diskusi semantik tentang terminologi matematika tidak termasuk dalam SO.
Rushyo
7
Itulah tepatnya alasan saya dirumuskan bahwa kata dalam tanda kutip menakut-nakuti, untuk mencegah semacam ini omong kosong. Itu mengasumsikan bahwa pembaca sudah familiar dengan tulisan bahasa Inggris sehari-hari, saya rasa. Anda akan berpikir akal sehat sudah cukup. Saya tidak menggunakan istilah yang tidak jelas karena saya pikir "Anda tahu, saya benar-benar ingin ditanyai tentang ini oleh seseorang yang tidak mau repot mencari sumber aslinya yang akan memakan waktu dua detik di Google".
Rushyo
2
Nah, Anda sebenarnya belum menjawab pertanyaan itu.
BJovke
1
Bagi mereka yang ingin tahu di mana dia menemukannya: Beyond3d.com/content/articles/8
mr5
52

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.

Crashworks
sumber
4
Ini masih jauh lebih cepat daripada std :: sqrt ().
Tara
2
Apakah anda memiliki sumber? Saya ingin menguji runtime tetapi saya tidak memiliki kit pengembangan Xbox 360.
DucRP
31

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:

y = f(x)

bisa persis diubah menjadi:

y = a0 + a1*x + a2*(x^2) + a3*(x^3) + a4*(x^4) + ...

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:

y = 1/sqrt(x)

Dalam kasus khusus ini, mereka memutuskan untuk membuang semua anggota polinom di atas detik, mungkin karena kecepatan penghitungan:

y = a0 + a1*x + [...discarded...]

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:

a0 = 0x5f375a86
a1 = -0.5

Jadi, saat Anda memasukkan ini ke dalam persamaan, Anda mendapatkan:

y = 0x5f375a86 - 0.5*x

Yang sama dengan baris yang Anda lihat di kode:

i = 0x5f375a86 - (i >> 1);

Sunting: sebenarnya di sini y = 0x5f375a86 - 0.5*xtidak sama dengan i = 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:

x = x * (1.5f - xhalf * x * x)

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.

BJovke
sumber
2
Mentransmisikan penunjuk ke posisi panjang adalah perkiraan dari log_2 (float). Menuangnya kembali adalah perkiraan panjang 2 ^. Ini berarti Anda dapat membuat rasio tersebut mendekati linier.
wizzwizz4
22

Menurut artikel bagus ini yang ditulis beberapa waktu lalu ...

Keajaiban kode, bahkan jika Anda tidak dapat mengikutinya, menonjol sebagai i = 0x5f3759df - (i >> 1); baris. Sederhananya, Newton-Raphson adalah perkiraan yang dimulai dengan tebakan dan menyempurnakannya dengan iterasi. Mengambil keuntungan dari sifat prosesor 32-bit x86, i, sebuah bilangan bulat, awalnya disetel ke nilai bilangan titik mengambang yang ingin Anda ambil kuadratnya, menggunakan pemeran integer. saya kemudian disetel ke 0x5f3759df, minus itu sendiri bergeser satu bit ke kanan. Pergeseran kanan menjatuhkan sedikit i yang paling tidak signifikan, pada dasarnya membelahnya.

Bacaan yang sangat bagus. Ini hanya sebagian kecil saja.

Dillie-O
sumber
19

Saya ingin tahu apa konstanta itu sebagai pelampung jadi saya cukup menulis sedikit kode ini dan mencari bilangan bulat yang muncul di Google.

    long i = 0x5F3759DF;
    float* fp = (float*)&i;
    printf("(2^127)^(1/2) = %f\n", *fp);
    //Output
    //(2^127)^(1/2) = 13211836172961054720.000000

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

ThisIsAReallyOldQuestion
sumber
6
Ini membutuhkan lebih banyak perhatian. Semuanya masuk akal setelah menyadari bahwa itu hanya akar kuadrat dari 2 ^ 127 ...
u8y7541