XProfan

Deutsch

p.specht

Berühmter bit-hack-Algorithmus aus QUAKE III
zum Invertieren von Quadratwurzeln
... wird bei der Normierung der Länge von 3D-Vektoren in Single precision float-Variablen eingesetzt. In Assembler über drei mal schneller als 1/Sqrt() !, Fehler max. 1 %:

Youtube-Link (engl.): [...]

Computer: Gerät, daß es in Mikrosekunden erlaubt, 50.000 Fehler zu machen, zB 'daß' statt 'das'...

03.01.2021 ▲

Vollständiges Zitat

Absatzweise zitieren Zeilenweise zitieren

« Dieser Beitrag wurde als Lösung gekennzeichnet. »

Michael
W.

Nun ja, den sollten wir eigentlich nachbilden können.

Da die (Microsoft-)Floats ja mittels Single() in einem Longint gespeichert werden können...

Kompilieren Markieren Separieren


// Inverse Square Root

// Def !threehalfs 1.5  // oder als wirkliche Konstante, dann als Präfix

Proc Q_rsqrt
   Parameters number!
   Declare i&, x2!, y!
   Var threehalfs! = 1.5  // mit richtiger Konstante wird diese Zeile dann entfernt

   x2! = number! * 0.5
   y!  = number!

   i&  = Single(y!)
   i&  = $5F3759DF - (i& >> 1)
   y!  = Double(i&)

   y!  = y! * (threehalfs! - (x2! * y! * y!))  // y! * (threehalfs! - (x2! * Sqr(y!)))
// y!  = y! * (threehalfs! - (x2! * y! * y!))  // y! * (threehalfs! - (x2! * Sqr(y!)))
   Return y!
EndProc

Ich habe nur bis zur Formel geschaut.
Einfach mal testen.

Alle Sprachen
System: Windows 8/10, XProfan X4
Programmieren, das spannendste Detektivspiel der Welt.

06.01.2021 ▲

Vollständiges Zitat

Absatzweise zitieren Zeilenweise zitieren

p.specht

Mutiger Versuch, großes DANKE!

Sieht gut aus:

Kompilieren Markieren Separieren

// Inverse Square Root
// Def !threehalfs 1.5  // oder als wirkliche Konstante, dann als Präfix

Proc Q_rsqrt

    Parameters number!
    Declare i&, x2!, y!
    Var threehalfs! = 1.5// mit richtiger Konstante wird diese Zeile dann entfernt
    x2! = number! * 0.5
    y!  = number!
    i&  = Single(y!)
    i&  = $5F3759DF - (i& >> 1)
    y!  = Double(i&)
    y!  = y! * (threehalfs! - (x2! * y! * y!))// y! * (threehalfs! - (x2! * Sqr(y!)))
    '//y!  = y! * (threehalfs! - (x2! * y! * y!))  // y! * (threehalfs! - (x2! * Sqr(y!)))
    Return y!

EndProc

WindowTitle "Testbench für Michael Wodrichs Quake-Trick"
AppendMenubar 100,"   Testwert           Quake-Output          1/Sqrt()         Abs.Fehler         Rel.Err %"
cls:Set("decimals",7):Print
Declare w!

WhileLoop 1,999999,50:w!=&Loop/100//generiert 5000 test steps

    Print "  ",w!,Q_rsqrt(w!),1/Sqrt(w!),(Q_rsqrt(w!)-1/Sqrt(w!)),(Abs(Q_rsqrt(w!)-1/Sqrt(w!))/(1/Sqrt(w!)))*100,"%"

    If %csrlin>27:WaitInput 8000:cls:Print:EndIf

    EndWhile

    Print:Print "---":Beep
    WaitInput
    End

Computer: Gerät, daß es in Mikrosekunden erlaubt, 50.000 Fehler zu machen, zB 'daß' statt 'das'...

06.01.2021 ▲

Vollständiges Zitat

Absatzweise zitieren Zeilenweise zitieren

Sven
Bader

Da ich gerade mit der Generierung von Normalen arbeite, habe ich auch mal den Hack hier ausprobiert. Für das gezeigte Beispiel konnte ich keinen optischen Unterschied feststellen.

Ob es in XProfan tatsächlich schneller ist habe ich noch nicht ausprobiert.

Im nächsten Schritt müsste ich übrigens noch die je 4 Normalen, die sich in den Schnittpunkten treffen zusammenfassen, dann ist die Schattierung geglättet.