Fast Inverse Square Root (0x5f3759df Sayısının Gizemi)

Fatih54102

Binbaşı

1089 Mesaj

Tüm Başarılarını Gör

Bu sayıyı Terje Mathisen adlı bir kişi bir bilim deneyini çabuk bulmak için bulmuş, bu sayı 1995~ yıllarda daha FPU(CPU nun içindeki bir bölüm, kök alma gibi karmaşık işlemleri yapar) nun şuanki kadar gelişmediği dönemde çok çok hızlı bir şekilde 1/kök bulmaya yarıyor.

C++:

float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;

x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed

return y;
}

Quake3 Arena(O dönemin bir oyunu, 3D hızlı hesaplama yapabilmek için CPU software render motoruna koyulmuş.) nın kaynak kodlarından alınan bu fonksiyonda sayının nasıl kullanıldığı belirtiliyor, bu sayı sayesinde bir sayının karekökü yaklaşık şekilde bulunabiliyor.

Örnek:

256 sayısı karekökü -> 16.0271 olarak buluyor bu da çok yaklaşık bir değer.

679856 sayısının karesi -> 462204180736 karekökü -> 680912 olarak buluyor.

---

-----Original Message-----
From: Terje Mathisen
Sent: 22 August 2005 07:49
Subject: Re: FW: Origin of fast approximated inverse square root

ryszard wrote:

> Hey Terje,
>
> This question has come up again since id released the source to Quake
> 3 Arena.
> > Are you the guy who wrote that fast implementation of inverse square root?
> If so, do you have a history of where it came from and how you came up
> with it? A whole bunch of hackers and geeks would love to know and
> since John says it wasn't him or likely Michael, was it you?

Hello Ryszard, and hello again John, it's been a few years since we last met. :-(

Thanks for giving me as a possible author, when I first saw the subject I did
indeed think it was some of my code that had been used. :-)

I wrote a very fast (pipelineable) & accurate invsqrt() 5+ years ago, to help
a Swede with a computational fluid chemistry problem.

His simulation runs used to take about a week on either Alpha or x86 systems,
with my modifications they ran in HALF THE TIME, while delivering the exact
same final printed results (8-10 significant digits).

The code shown below is not the same as what I wrote, I would guess it mostly
stays within a fraction of a percent? The swede needed at least 48 sigificant
bits in his results, so I employed a much more straightforward table lookup
plus NR-iteration. Since water molecules contain three atoms it was quite
straightforward to calculate three such invsqrt() values in parallel, this was
enough to avoid almost all bubbles in the fp pipelines.

I do think I recognize the style of the Q3A code however, it looks a lot like
something you'll find in the old HAKMEM documents from MIT. :-)

Regards,

Terje
"almost all programming can be viewed as an exercise in caching"

---

http://www.beyond3d.com/content/articles/8/

http://en.wikipedia.org/wiki/Fast_inverse_square_root

Peki 0x5f3759df sayısı yani 1,597,463,007 nasıl bir sayının 1/karekök bulunmasında yardımcı olabiliyor?

< Bu ileti mobil sürüm kullanılarak atıldı >

Fast Inverse Square Root (0x5f3759df Sayısının Gizemi)

Benzer içerikler