Fast Inverse Square Root (0X5f3759df Sayısının Gizemi)
-
Bu sayıyı Terje Mathisen adlı bir kişi bir bilim deneyini çabuk bulmak için bulmuş, bu sayı 1995~ yıllarda daha FPU 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?
-
Hocam bildiğim kadarıyla kitaplarda yazan hiçbirşeyden ilham alarak yapılmamış, Programcılardan birinin kendi buluşuymuş bu
-
düşündüm düşündüm o kod nasıl çalışıyor bir türlü çözemedim. :/
-
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; }
help
{
cout("beyler şu olayı birileri anlatabilir mi :S");}
-
Adam mailde söylemiş benim kodum değil diye. MIT paperlarından bulmuşlardır heralde demiş.
Inverse sqrt kodunu da ışıklandırma ve gölge işleri için yüzey normalini bulmak amacıyla hesaplıyorlar.
Şurada açıklamalı anlatmış kodun nasıl çalıştığını. http://en.wikipedia.org/wiki/Fast_inverse_square_root
Genel olarak olay float sayıların memoryde nasıl saklandığı üzerinden çözülmüş. ,
örn. 0.15625 -> binary 0.00101 -> 1.01*2^-3
right shift (number) = number / 2
son adımda da tek basamakta newton raphson ile sonuca gidiyor.
-
koddaki işlemlerin ne olduğunu anlatacak biri varsa belki çözebiliriz
-
XCoder bunu yazdı
Adam mailde söylemiş benim kodum değil diye. MIT paperlarından bulmuşlardır heralde demiş.
Inverse sqrt kodunu da ışıklandırma ve gölge işleri için yüzey normalini bulmak amacıyla hesaplıyorlar.
Şurada açıklamalı anlatmış kodun nasıl çalıştığını. http://en.wikipedia.org/wiki/Fast_inverse_square_root
Genel olarak olay float sayıların memoryde nasıl saklandığı üzerinden çözülmüş. ,
örn. 0.15625 -> binary 0.00101 -> 1.01*2^-3
right shift (number) = number / 2
son adımda da tek basamakta newton raphson ile sonuca gidiyor.
abi türkçe olsa belki gene anlamayacağım bi olayı ingilzce hiç anlayamam :|
-
Aslında sormak istediğim 0x5f3759df sayısını nereden ve nasıl bulmuşlar?
-
Fatih54 bunu yazdı
Aslında sormak istediğim 0x5f3759df sayısını nereden ve nasıl bulmuşlar?
fonksiyondaki işlemleri anlatsa biri belki anlarız
-
matematiksel açıklaması burada mevcut:
-
smok3 bunu yazdı
matematiksel açıklaması burada mevcut:
Çok teşekkürler.