Siapa penemu trik di InvSqrt() ?

Nostalgia lagi…. sore ini menemukan sebuah artikel di Beyond3D yang berjudul Origin of Quake3’s Fast InvSqrt().

Secara ringkas; di source code game Quake 3, ada code berikut ini :

float InvSqrt (float x){
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f3759df – (i>>1);
x = *(float*)&i;
x = x*(1.5f – xhalf*x*x);
return x;
}

Ini adalah implementasi algorithma Newton-Raphson untuk menemukan inverse square-root (apa ya bahasa Indonesianya? satu per akar dari X ?) dari suatu angka bertipe float (pecahan?)

Kebanyakan prosesor komputer melakukan perhitungan bilangan bulat (integer) JAUH lebih cepat daripada melakukan perhitungan bilangan tipe float. Function InvSqrt() diatas melakukan ini — dengan satu trik yang membuatnya memiliki performa jauh lebih cepat dibandingkan biasanya.

Algoritma Newton-Raphson menghitung inverse square-root dengan cara memulai perhitungan dari suatu angka, dan kemudian melakukan iterasi sampai akhirnya ditemukan hasil yang sebenarnya. Nah, pada kode diatas, angka awalnya ini ternyata terbukti memang selalu memberikan hasil dalam waktu yang PALING singkat (sampai 4x lipat lebih cepat).

Kode ini kemudian banyak digunakan di berbagai software, dengan hasil yang sangat memuaskan.

Banyak orang kemudian tergelitik dan berusaha menemukan siapa penemu konstanta tersebut. Terutama untuk mengetahui bagaimana ybs menemukan konstanta itu – apakah melalui coba-coba? Atau dengan perhitungan?

Cerita yang panjang dipersingkat – ternyata kode ini sudah cukup tua umurnya. Terakhir berhasil dilacak ke Gary Tarolli, yang menggunakannya ketika masih bekerja di 3dfx.
Sayangnya Gary pun tidak tahu siapa pembuatnya, namun dia menyebutkan bahwa dia sudah menemukan code tersebut sejak 10 tahun sebelumnya ! Maka paling tidak, code tersebut sudah ada sejak 15 tahun yang lalu. Dan sampai saat ini masih terus menjadi misteri tentang siapa penemunya.

Kisah ini juga adalah satu lagi alasan mengapa open source baik bagi kemajuan teknologi dunia. Kalau saja John Carmack tidak membukakan source code ke game Quake 3 nya, maka belum tentu code ini akan menjadi populer, dan banyak dimanfaatkan oleh berbagai pihak.
Dengan open source, banyak orang mendapatkan keuntungan, bahkan pemegang hak cipta software tersebut sendiri.

2 thoughts on “Siapa penemu trik di InvSqrt() ?

  1. I think there’s already an easier code for it, I forgot which article did I read it before. Yes, I was also intrigued with whom is behind ‘constant’. Thanks for sharing your knowledgeable post.

    Sarah
    To visit my website, kindly click here.

Leave a Reply

Your email address will not be published. Required fields are marked *