Hızlı ters karekök algoritması hakkında bilmeniz gereken her şey

Hızlı ters karekök algoritması hakkında her şey

Algoritma

• Hızlı ters karekök algoritması, Quake 3 kaynak koduyla ün kazanan ve John Carmack tarafından kullanılan bir algoritmadır.
• Bu algoritma, kayan noktalı sayıların bitlerini manipüle ederek ters karekökü hızlıca hesaplar.
• Kod örneği:

  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;
  }
  

32 bit kayan nokta: gösterim

• IEEE-754 32 bit kayan nokta 3 bileşenden oluşur:
  • İşaret: 1 bit, sayının pozitif/negatif olduğunu gösterir.
  • Üs: 8 bit, sayının aralığını belirler.
  • Mantissa: 23 bit, sayıdaki konumu bu aralık içinde belirtir.
• Gerçek değer şu şekilde hesaplanır:

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

32 bit kayan nokta: bitlerin yorumlanması

• Kayan noktanın iç gösterimi normalde programcılar için önemli değildir.
• Ancak bu gösterimi iyi anlamak, verimli algoritmalar tasarlamayı mümkün kılar.
• Kayan noktanın bit desenini tamsayı olarak yorumlamak, log fonksiyonunun yaklaşık bir değerini verir.

  log2(x) ≈ Ix / L - B
  

Newton yöntemi

• Başlangıç yaklaşık değerini iyileştirmek için Newton yöntemi (Newton's method) kullanılır.
• Newton yöntemi, verilen bir fonksiyonun yaklaşık değerini yinelemeli olarak iyileştiren bir algoritmadır.
• Kod örneği:

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

Sonuç

• Bu algoritma, kayan nokta sisteminin iç matematiksel ayrıntılarını derinlemesine anlayarak ve bilgisayarda hızlı çalışan işlemlerden yararlanarak tasarlanmıştır.
• Algoritmanın kökeni kesin olarak bilinmese de, son derece verimli ve iyi tasarlanmış bir mühendislik örneğidir.

GN⁺ görüşü

• Tarihsel önem: Bu algoritma, dönemin donanım kısıtlarını aşmak için geliştirilmiş yenilikçi bir yöntemdir.
• Eğitsel değer: Kayan noktanın iç yapısını ve matematiksel ilkelerini anlamaya büyük katkı sağlar.
• Modern uygulama: Modern donanımlarda daha az gerekli olabilir, ancak algoritmanın prensipleri hâlâ yararlıdır.
• Optimizasyon potansiyeli: Algoritmadaki sabit değer optimize edilebilir; bu da ek araştırma için alan bırakır.
• Eleştirel bakış: Modern donanımlarda daha iyi yöntemler olabilir; bu yüzden her zaman güncel teknolojilerle karşılaştırmak önemlidir.

[joyfui]

İnsan unuturken bir anda yeniden ortaya çıkan o ilginç kod.. heh

[GN⁺]

Hacker News yorumu

• SSE komut desteği: 1999'dan sonra üretilen bilgisayarlar SSE komut setini destekler ve _mm_rsqrt_ps komutu üzerinden ters karekök hızlıca hesaplanabilir.

• Modern donanımın gelişimi: Modern donanımda ters karekök hesabı CPU üzerinde hızlıca yapılabilir; tüm kayan nokta işlemlerinin GPU'ya offload edildiği düşüncesi bir yanlış anlamadır.

• MMIX implementasyonu: MMIX dilinde ters karekök hesabını gerçekleştiren örnek kod vardır. Bu kod, başlangıçtaki sayının 2^-1021'den büyük olduğunu varsayar.

• Formüldeki yazım hatası: Kayan nokta formülünde bir yazım hatası var. (-1)^S olarak düzeltilmeli.

• Logaritmanın yorumu: Ham bit desenini yorumlamak, logaritmanın parçalı doğrusal bir yaklaşımı değildir. Veri noktaları arasındaki çizgiler gerçekte mevcut değildir.

• Wikipedia referansı: Bu fonksiyon ve geçmişi hakkında Wikipedia'da iyi bir tartışma var. Wikipedia bağlantısı

• GitHub kod derlemesi: İlgili bazı kodlar GitHub'da bir araya getirilmiş. GitHub bağlantısı

• StackOverflow referansı: Optimize edilmiş düşük hassasiyetli yaklaşım için bir StackOverflow sorusuna da bakmaya değer. StackOverflow bağlantısı

• 3D motor optimizasyon deneyimi: Quake'den önce 3D motorlar geliştirirken optimizasyon deneyimi biriktirildi ve algoritma optimizasyonunun her zaman kazandığı görüldü.

• YouTube video önerisi: Bu konu hakkında ilgi çekici bir video var. YouTube bağlantısı

• Üretkenlik zaman hırsızı: Bu konuya kapılıp çok fazla üretken zaman kaybedildi.

• En iyi sihirli sayı: Ünlü kod parçasındaki sihirli sayı en iyi sabit değildir. Daha iyi bir sabit bulmak mümkündür ve Jupyter notebook ile en iyi sihirli sayı bulunabilir.