Divisione veloce 1/X (reciproco)

Question

C'è un modo per migliorare il reciproco (divisione 1 su X) rispetto alla velocità, se la precisione non è cruciale?

Quindi, ho bisogno di calcolare 1/X. C'è qualche soluzione, quindi perdo la precisione ma lo faccio più velocemente?

Answer 1

Innanzitutto, assicurarsi che questo non sia un caso di ottimizzazione prematura. Sai che questo è il collo di bottiglia?

Come dice Mystical, 1/x può essere calcolato molto rapidamente. Assicurati di non utilizzare il tipo di dati double per 1 o il divisore. I galleggianti sono molto più veloci.

Detto questo, benchmark, benchmark, benchmark. Non sprecare il tuo tempo a spendere ore in teoria numerica solo per scoprire la fonte della scarsa performance è l'accesso IO.

Answer 2

Prima di tutto, se si attivano le ottimizzazioni del compilatore, è probabile che il compilatore ottimizzi il calcolo, se possibile (per estrarlo da un ciclo, ad esempio). Per vedere questa ottimizzazione, è necessario creare ed eseguire in modalità di rilascio.

La divisione può essere più pesante della moltiplicazione (ma un commentatore ha sottolineato che i reciproci sono veloci quanto la moltiplicazione sulle CPU moderne, nel qual caso, questo non è corretto per il tuo caso), quindi se hai 1/X da qualche parte all'interno di un ciclo (e più di una volta), è possibile assistere memorizzando nella cache il risultato all'interno del ciclo (float Y = 1.0f/X;) e quindi utilizzando Y. (L'ottimizzazione del compilatore potrebbe farlo in ogni caso.)

Inoltre, alcune formule possono essere ridisegnate per rimuovere la divisione o altri calcoli inefficienti. Per questo, potresti pubblicare il calcolo più grande che viene eseguito. Anche lì, il programma o l'algoritmo stesso può a volte essere ristrutturato per evitare di dover colpire frequentemente i loop che richiedono tempo.

Quanta precisione può essere sacrificata? Se per caso hai solo bisogno di un ordine di grandezza, puoi farlo facilmente usando l'operatore modulo o operazioni bit a bit.

Tuttavia, in generale, non c'è modo di accelerare la divisione. Se ci fossero, i compilatori lo farebbero già.

Answer 3

Il modo più veloce che conosco è utilizzare le operazioni SIMD. http://msdn.microsoft.com/en-us/library/796k1tty(v=vs.90).aspx

Answer 4

Credo che quello che cercava sia un modo più efficiente di approssimare 1.0/x invece di una definizione tecnica di approssimazione che afferma che si potrebbe usare 1 come risposta molto impercisa. Credo anche che questo lo soddisfi.

__inline__ double __attribute__((const)) reciprocal(unsigned long long x) { 
    //The type is unsigned long long, but you are restricted to a max value of 2^32-1, not 
    // 2^64-1 like the unsigned long long is capable of storing 
    union { 
     double dbl; 
     unsigned long long ull; 
    } u = {.dbl=(x*=x)};  // x*x = pow(x, 2) 
    u.ull = (0xbfcdd6a18f6a6f52ULL - u.ull) >> (unsigned char)1; 
           // pow(pow(x,2), -0.5) = pow(x, -1) = 1.0/x 
           // This is done via the 'fast' inverse square root trick 
    return u.dbl; 
} 

__inline__ double __attribute__((const)) reciprocal(double x) { 
    union { 
     double dbl; 
     unsigned long long ull; 
    } u; 
    u.dbl = x; 
    u.ull = (0xbfcdd6a18f6a6f52ULL - u.ull) >> (unsigned char)1; 
            // pow(x, -0.5) 
    u.dbl *= u.dbl;     // pow(pow(x,-0.5), 2) = pow(x, -1) = 1.0/x 
    return u.dbl; 
} 

__inline__ float __attribute__((const)) reciprocal(float x) { 
    union { 
     float dbl; 
     unsigned uint; 
    } u; 
    u.dbl = x; 
    u.uint = (0xbe6eb3beU - u.uint) >> (unsigned char)1; 
            // pow(x, -0.5) 
    u.dbl *= u.dbl;     // pow(pow(x,-0.5), 2) = pow(x, -1) = 1.0/x 
    return u.dbl; 
} 

Hmm ....... io feritore se la CPU produce sapeva si potrebbe ottenere il reciproco con un solo moltiplicare , sottrazione e spostamento di bit quando hanno progettato la CPU .... hmm .........

Per quanto riguarda i bench-marking, l'hardware x istruzioni in combinazione con le istruzioni hardware sottrazione sono altrettanto velocemente come hardware 1.0/x istruzioni su moderni computer al giorno (i miei punti di riferimento erano su un i7 di Intel, ma vorrei assumere risultati simili per altri processori). Tuttavia, se questo algoritmo fosse implementato nell'hardware come una nuova istruzione di assemblaggio, allora l'aumento della velocità sarebbe probabilmente abbastanza buono da rendere questa istruzione abbastanza pratica.

Infine, questa implementazione si basa sul meraviglioso "fast" inverse square root algorithm.

Answer 5

Questo dovrebbe farlo con un certo numero di pre-srotolati iterazioni di Newton valutato come un polinomio Horner che usa fuso-moltiplicare accumulare operazioni più moderne CPU giornata di eseguire in un unico ciclo Clk (ogni volta):

float inv_fast(float x) { 
    union { float f; int i; } v; 
    float w, sx; 
    int m; 

    sx = (x < 0) ? -1:1; 
    x = sx * x; 

    v.i = (int)(0x7EF127EA - *(uint32_t *)&x); 
    w = x * v.f; 

    // Efficient Iterative Approximation Improvement in horner polynomial form. 
    v.f = v.f * (2 - w);  // Single iteration, Err = -3.36e-3 * 2^(-flr(log2(x))) 
    // v.f = v.f * (4 + w * (-6 + w * (4 - w))); // Second iteration, Err = -1.13e-5 * 2^(-flr(log2(x))) 
    // v.f = v.f * (8 + w * (-28 + w * (56 + w * (-70 + w *(56 + w * (-28 + w * (8 - w))))))); // Third Iteration, Err = +-6.8e-8 * 2^(-flr(log2(x))) 

    return v.f * sx; 
} 

Fine Print: più vicino a 0, l'approssimazione non è ottimale, quindi il programmatore deve testare le prestazioni o limitare l'ingresso al minimo prima di ricorrere alla divisione hardware. sii responsabile!