Cosa è più veloce di std :: pow?

Question

Il mio programma spende il 90% del tempo della CPU nella funzione std::pow(double,int). L'accuratezza non è una preoccupazione primaria qui, quindi mi chiedevo se ci fossero alternative più veloci. Una cosa che stavo pensando di provare è lanciare su float, eseguire l'operazione e poi tornare a raddoppiare (non l'ho ancora provato); Sono preoccupato che questo non è un modo portabile di migliorare le prestazioni (non la maggior parte delle CPU operano su doppie intrinseca in ogni caso?)

Acclamazioni

Answer 1

Sembra Martin Ankerl ha un paio di articoli su questo, Optimized Approximative pow() in C/C++ è uno e ha due versioni veloci, uno è la seguente:

inline double fastPow(double a, double b) { 
    union { 
    double d; 
    int x[2]; 
    } u = { a }; 
    u.x[1] = (int)(b * (u.x[1] - 1072632447) + 1072632447); 
    u.x[0] = 0; 
    return u.d; 
} 

che si basa su tipo di gioco di parole attraverso un'unione che è un comportamento indefinito in C++, dal progetto di sezione standard 9.5[class.union]:

in un'unione, al massimo uno dei membri dati non statici possono essere ctive in qualsiasi momento, ovvero il valore di la maggior parte dei membri di dati non statici possono essere memorizzati in un sindacato in qualsiasi momento. [...]

ma la maggior parte dei compilatori tra cui gcc support this with well defined behavior:

La pratica di lettura da un membro del sindacato diverso da quello più recente scritto (denominato “tipo-giochi di parole”) è comune. Anche con -fstrict-aliasing, è consentita tipo gioco di parole, purché la memoria si accede attraverso il tipo unione

ma questo non è universale come this article points out e come point out in my answer here usando memcpy dovrebbe generare codice identico e non richiama indefinito comportamento.

Si collega anche a un secondo Optimized pow() approximation for Java, C/C++, and C#.

Il primo articolo collega anche ai suoi microbenchmarks here

Answer 2

A seconda di ciò che devi fare, che opera nel dominio di registro potrebbe funzionare - cioè, sostituisci tutti i tuoi valori con i loro logaritmi; la moltiplicazione diventa addizione, la divisione diventa sottrazione e l'esponenziazione diventa moltiplicazione. Ma ora addizione e sottrazione diventano operazioni costose e in qualche modo soggette a errori.

Answer 3

Quanto sono grandi i tuoi numeri interi? Sono conosciuti al momento della compilazione? È molto meglio calcolare x^2 come x*x rispetto a pow(x,2). Nota: quasi tutte le applicazioni da pow() a una potenza intera comportano l'innalzamento di un numero alla seconda o terza potenza (o l'inversione moltiplicativa nel caso di esponenti negativi). L'utilizzo di pow() è eccessivo in questi casi. Usa un modello per questi piccoli poteri interi, o usa semplicemente x*x.

Se gli interi sono piccoli, ma non noti al momento della compilazione, diciamo tra -12 e +12, la moltiplicazione continuerà a battere pow() e non perderà la precisione. Non hai bisogno di undici moltiplicazioni per calcolare x^12. Quattro lo faranno. Usa il fatto che x^(2n) = (x^n)^2 e x^(2n + 1) = x * ((x^n)^2). Ad esempio, x^12 è ((x * x * x)^2)^2.Due moltiplicazioni per calcolare x^3 (x * x * x), un'altra per calcolare x^6 e una finale per calcolare x^12.