Segala Pengetahuan tentang Algoritma Inverse Square Root Cepat

Segala Hal tentang Inverse Square Root Cepat

Algoritma

• Algoritma inverse square root cepat adalah algoritma yang menjadi terkenal lewat source code Quake 3, dan digunakan oleh John Carmack.
• Algoritma ini memanipulasi bit bilangan floating-point untuk menghitung inverse square root dengan cepat.
• Contoh kode:

  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 ) );  // 1차 반복
  
    return y;
  }
  

Floating-point 32-bit: representasi

• Floating-point 32-bit IEEE-754 terdiri dari 3 komponen:
  • Tanda: 1 bit, menunjukkan apakah angka bernilai positif atau negatif.
  • Eksponen: 8 bit, menentukan rentang angka.
  • Mantisa: 23 bit, menentukan posisi angka di dalam rentang tersebut.
• Nilai sebenarnya dihitung sebagai berikut:

  N = -1^S * 2^(E-127) * (1 + M/2^23)
  

Floating-point 32-bit: interpretasi bit

• Representasi internal floating-point biasanya tidak penting bagi programmer.
• Namun, jika representasi ini dipahami dengan baik, perancangan algoritma yang efisien menjadi mungkin.
• Jika pola bit floating-point diinterpretasikan sebagai bilangan bulat, hasilnya menjadi nilai aproksimasi dari fungsi logaritma.

  log2(x) ≈ Ix / L - B
  

Metode Newton

• Untuk memperbaiki nilai aproksimasi awal, digunakan metode Newton (Newton's method).
• Metode Newton adalah algoritma yang secara iteratif memperbaiki nilai aproksimasi dari fungsi yang diberikan.
• Contoh kode:

  y = y * ( threehalfs - ( x2 * y * y ) ); // 1차 반복
  

Kesimpulan

• Algoritma ini dirancang dengan memahami secara mendalam detail matematis internal dari sistem floating-point, serta memanfaatkan operasi yang berjalan cepat di komputer.
• Asal-usul algoritma ini tidak diketahui secara pasti, tetapi ini adalah contoh rekayasa yang sangat efisien dan dirancang dengan baik.

Opini GN⁺

• Penting secara historis: Algoritma ini adalah metode inovatif yang dirancang untuk mengatasi keterbatasan hardware pada masanya.
• Nilai edukatif: Sangat membantu untuk memahami struktur internal floating-point dan prinsip-prinsip matematisnya.
• Penerapan modern: Pada hardware modern mungkin tidak lagi terlalu diperlukan, tetapi prinsip algoritmanya tetap berguna.
• Potensi optimasi: Nilai konstanta dalam algoritma ini dapat dioptimalkan, dan masih ada ruang untuk penelitian lebih lanjut.
• Sudut pandang kritis: Pada hardware modern mungkin ada metode yang lebih baik, sehingga penting untuk selalu membandingkannya dengan teknologi terbaru.

[joyfui]

Kode unik yang suka muncul lagi tiap kali hampir terlupakan.. hehe

[GN⁺]

Komentar Hacker News

• Dukungan instruksi SSE: Komputer yang dibuat setelah 1999 mendukung set instruksi SSE, dan dapat menghitung inverse square root dengan cepat melalui instruksi _mm_rsqrt_ps.

• Perkembangan hardware modern: Pada hardware modern, perhitungan inverse square root dapat dilakukan dengan cepat di CPU, dan anggapan bahwa semua operasi floating point di-offload ke GPU adalah keliru.

• Implementasi MMIX: Ada contoh kode yang mengimplementasikan perhitungan inverse square root dalam bahasa MMIX. Kode ini mengasumsikan bahwa angka asal lebih besar dari 2^-1021.

• Salah ketik pada rumus: Ada typo pada rumus floating point. Harus diperbaiki menjadi (-1)^S.

• Interpretasi logaritma: Menafsirkan pola bit mentah bukanlah pendekatan linear sepotong-sepotong terhadap logaritma. Garis di antara titik-titik data sebenarnya tidak ada.

• Rujukan Wikipedia: Ada pembahasan yang bagus tentang fungsi ini dan sejarahnya di Wikipedia. Tautan Wikipedia

• Kumpulan kode di GitHub: Beberapa kode terkait telah dikumpulkan di GitHub. Tautan GitHub

• Rujukan StackOverflow: Pertanyaan StackOverflow tentang pendekatan teroptimasi dengan akurasi rendah juga layak dilihat. Tautan StackOverflow

• Pengalaman optimasi engine 3D: Sebelum Quake, ada pengalaman membangun engine 3D sambil mengasah optimasi, dan optimasi algoritma selalu menang.

• Rekomendasi video YouTube: Ada video menarik tentang topik ini. Tautan YouTube

• Pencuri waktu produktif: Terlalu tenggelam dalam topik ini hingga banyak waktu produktif tersita.

• Angka ajaib optimal: Angka ajaib dalam cuplikan kode terkenal itu bukan konstanta yang optimal. Dimungkinkan menemukan konstanta yang lebih baik, dan angka ajaib optimal bisa dicari melalui notebook Jupyter.