folder Tahribat.com Forumları
linefolder C - C++
linefolder Fast Inverse Square Root (0X5f3759df Sayısının Gizemi)



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

  1. KısayolKısayol reportŞikayet pmÖzel Mesaj
    Fatih54
    Fatih54's avatar
    Kayıt Tarihi: 16/Ağustos/2012
    Erkek

    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?

  2. KısayolKısayol reportŞikayet pmÖzel Mesaj
    Tarikat Şeyhi
    HolyOne
    HolyOne's avatar
    Kayıt Tarihi: 01/Haziran/2002
    Erkek

    Hocam bildiğim kadarıyla kitaplarda yazan hiçbirşeyden ilham alarak yapılmamış, Programcılardan birinin kendi buluşuymuş bu

  3. KısayolKısayol reportŞikayet pmÖzel Mesaj
    Buremba
    Buremba's avatar
    Kayıt Tarihi: 16/Haziran/2006
    Erkek

    düşündüm düşündüm o kod nasıl çalışıyor bir türlü çözemedim. :/

  4. KısayolKısayol reportŞikayet pmÖzel Mesaj
    asa42
    asa42's avatar
    Kayıt Tarihi: 17/Eylül/2009
    Erkek
    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");

    }
  5. KısayolKısayol reportŞikayet pmÖzel Mesaj
    XCoder
    XCoder's avatar
    Kayıt Tarihi: 15/Haziran/2007
    Erkek

    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.

     

     

  6. KısayolKısayol reportŞikayet pmÖzel Mesaj
    wert
    wert's avatar
    Kayıt Tarihi: 19/Eylül/2005
    Erkek

    koddaki işlemlerin ne olduğunu anlatacak biri varsa belki çözebiliriz

  7. KısayolKısayol reportŞikayet pmÖzel Mesaj
    asa42
    asa42's avatar
    Kayıt Tarihi: 17/Eylül/2009
    Erkek
    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 :|

  8. KısayolKısayol reportŞikayet pmÖzel Mesaj
    Fatih54
    Fatih54's avatar
    Kayıt Tarihi: 16/Ağustos/2012
    Erkek

    Aslında sormak istediğim 0x5f3759df sayısını nereden ve nasıl bulmuşlar?

  9. KısayolKısayol reportŞikayet pmÖzel Mesaj
    wert
    wert's avatar
    Kayıt Tarihi: 19/Eylül/2005
    Erkek
    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

  10. KısayolKısayol reportŞikayet pmÖzel Mesaj
    smok3
    smok3's avatar
    Kayıt Tarihi: 09/Nisan/2007
    Erkek

    matematiksel açıklaması burada mevcut:

    http://blog.quenta.org/2012/09/0x5f3759df.html

  11. KısayolKısayol reportŞikayet pmÖzel Mesaj
    Fatih54
    Fatih54's avatar
    Kayıt Tarihi: 16/Ağustos/2012
    Erkek
    smok3 bunu yazdı

    matematiksel açıklaması burada mevcut:

    http://blog.quenta.org/2012/09/0x5f3759df.html

    Çok teşekkürler.

Toplam Hit: 1243 Toplam Mesaj: 12