ottimizzazione rapida della radice quadrata?

Question

Se si seleziona questa molto bella pagina:

http://www.codeproject.com/Articles/69941/Best-Square-Root-Method-Algorithm-Function-Precisi

Vedrai questo programma:

#define SQRT_MAGIC_F 0x5f3759df 
float sqrt2(const float x) 
{ 
    const float xhalf = 0.5f*x; 

    union // get bits for floating value 
    { 
    float x; 
    int i; 
    } u; 
    u.x = x; 
    u.i = SQRT_MAGIC_F - (u.i >> 1); // gives initial guess y0 
    return x*u.x*(1.5f - xhalf*u.x*u.x);// Newton step, repeating increases accuracy 
} 

La mia domanda è: C'è un motivo particolare per cui questo non è implementato come:

#define SQRT_MAGIC_F 0x5f3759df 
float sqrt2(const float x) 
{ 

    union // get bits for floating value 
    { 
    float x; 
    int i; 
    } u; 
    u.x = x; 
    u.i = SQRT_MAGIC_F - (u.i >> 1); // gives initial guess y0 

    const float xux = x*u.x; 

    return xux*(1.5f - .5f*xux*u.x);// Newton step, repeating increases accuracy 
} 

quanto, da smontaggio, vedo uno MUL meno. C'è qualche motivo per avere lo xhalf visualizzato?

Answer 1

Potrebbe essere che la matematica in virgola mobile legacy, che utilizzava registri a 80 bit, era più precisa quando i moltiplicatori in cui erano collegati insieme nell'ultima riga come risultati intermedi dove erano tenuti in registri a 80 bit.

La prima moltiplicazione nell'implementazione superiore avviene in parallelo al calcolo matematico intero che segue, utilizzano diverse risorse di esecuzione. La seconda funzione invece sembra più veloce ma è difficile dire se è davvero a causa di quanto sopra. Inoltre, il const float xux = x * u.x; L'istruzione riduce il risultato a 32 bit float, il che può ridurre la precisione complessiva.

È possibile testare queste funzioni testa a testa e confrontarle con la funzione sqrt in math.h (utilizzare double not float). In questo modo puoi vedere quale è più veloce e che è più preciso.