C / C ++ arrotondamento decimali con una certa precisione, efficienza

Question

Sto cercando di ottimizzare quanto segue. Il soffietto di codice fa questo:

Se a = 0.775 e ho bisogno di precisione 2 dp, allora a => 0.78

In sostanza, se l'ultima cifra è 5, si arrotonda verso l'alto la cifra successiva, altrimenti non.

Il mio problema era che doesnt 0,45 rotonda a 0,5 con 1 decimalpoint, come il valore viene salvato come ,44999999343 .... e setprecision arrotonda a 0,4.

Ecco perché setprecision è costretto ad essere più alto setprecision(p+10) e poi se finisce davvero in un 5, aggiungere la piccola quantità al fine di completare correttamente.

Una volta fatto, si confronta una stringa con B e restituisce il risultato. Il problema è, questa funzione viene chiamata un paio di miliardi di volte, rendendo il Craw programma. Tutte le idee migliori su come riscrivere / ottimizzare questo e quali funzioni nel codice sono così pesanti sulla macchina?

bool match(double a,string b,int p) { //p = precision no greater than 7dp

    double t[] = {0.2, 0.02, 0.002, 0.0002, 0.00002, 0.000002, 0.0000002, 0.00000002};

    stringstream buff;
    string temp;

    buff << setprecision(p+10) << setiosflags(ios_base::fixed) << a; // 10 decimal precision
    buff >> temp;

    if(temp[temp.size()-10] == '5')  a += t[p]; // help to round upwards

    ostringstream test;
    test << setprecision(p) << setiosflags(ios_base::fixed) << a;
    temp = test.str();

    if(b.compare(temp) == 0) return true;

    return false;
}

Answer 1

ho scritto una subroutine radice quadrata intero con niente di più di una ventina di righe di ASM, senza chiamate API di sorta - e ancora poteva fare solo circa 50 milioni di SqRoots / secondo (questo è stato circa cinque anni fa ...) .

Il punto che sto facendo è che se si sta andando per miliardi di chiamate, la tecnologia ancora di oggi sta per soffocare.

Ma se si vuole veramente fare uno sforzo per accelerarlo, rimuovere il maggior numero usi API come umanamente possibile. Questo può richiedere di eseguire operazioni API manualmente, invece di lasciare che le librerie di farlo per voi. Specificamente, rimuovere qualsiasi tipo di operazione stream. Quelli sono più lento di sporco in questo contesto. Si può davvero improvvisare lì.

L'unica cosa che resta da fare dopo che è quello di sostituire le tante linee di C ++, come si può con ASM su misura - ma dovrete essere un perfezionista su di esso. Assicurarsi che si sta assumendo il massimo vantaggio di ogni ciclo della CPU e della registrazione - così come ogni byte di cache della CPU e spazio di stack.

Si può considerare l'utilizzo valori interi, invece di floating-punti, in quanto questi sono di gran lunga più ASM-friendly e molto più efficiente. Avresti per moltiplicare il numero per 10 ^ 7 (o 10 ^ p, a seconda di come si decide di formare la logica) per spostare il decimale tutta la strada verso destra. Poi si potrebbe tranquillamente convertire la virgola mobile in un intero di base.

Dovrete fare affidamento su hardware del computer per fare il resto.

<--Microsoft Specific-->
Devo dire anche aggiungere che C ++ identificatori (compresi quelli statici, come detto Donnie DeBoer) sono direttamente accessibili dai blocchi ASM annidati nel codice C ++. Questo rende inline un gioco da ragazzi.
<--End Microsoft Specific-->

Answer 2

A seconda di cosa si desidera che i numeri per, si potrebbe desiderare di utilizzare numeri in virgola fissa, invece di virgola mobile. Una rapida ricerca salta fuori questo .

Answer 3

Credo che si può semplicemente aggiungere 0.005 per la precisione di centesimi, 0,0005 per migliaia, ecc snprintf il risultato con qualcosa come "% 1.2f" (centesimi, millesimi 1.3f, etc.) e confrontare le stringhe. Si dovrebbe essere in grado di tavolo-izzare o parametrizzare questa logica.

Answer 4

Si potrebbe risparmiare alcuni cicli principali nel codice inviato da solo facendo che la doppia t [] statico, in modo che non è allocare più e più volte.

Answer 5

Prova a modificare:

#include <cmath>

double setprecision(double x, int prec) {
    return 
        ceil( x * pow(10,(double)prec) - .4999999999999)
        / pow(10,(double)prec);
}

E 'probabilmente più veloce. Forse provare inlining esso pure, ma che potrebbe far male se non aiuta.

Esempio di come funziona:

2.345* 100 (10 to the 2nd power) = 234.5
234.5 - .4999999999999 = 234.0000000000001
ceil( 234.0000000000001 ) = 235
235 / 100 (10 to the 2nd power) = 2.35

Il ,4999999999999 è stato scelto a causa della precisione di un c ++ doppia su un sistema a 32 bit. Se siete su una piattaforma a 64 bit sarà probabilmente bisogno di più nove. Se si aumentano le nove ulteriormente su un sistema a 32 bit che trabocca e arrotonda per difetto anziché verso l'alto, i. e. 234,00000000000001 ottiene troncati a 234 in un doppio a (mia) ambiente a 32 bit.

Answer 6

Utilizzando virgola mobile (una rappresentazione inesatta) significa che hai perso alcune informazioni circa il numero reale. Non si può semplicemente "fissare" il valore memorizzato nel doppio con l'aggiunta di un valore fondente. Questo potrebbe risolvere alcuni casi (come .45), ma si romperà gli altri casi. Vi ritroverete arrotondamento numeri che avrebbero dovuto essere arrotondato per difetto.

Ecco un articolo correlato: http://www.theregister.co.uk/2006/08/12 / floating_point_approximation /

Answer 7

sto prendendo a indovinare ciò che si intende fare. Ho il sospetto che si sta cercando di vedere se una stringa contiene una rappresentazione decimale di un doppio a una certa precisione. Forse si tratta di un programma di quiz aritmetica e si sta cercando di vedere se la risposta dell'utente è "abbastanza vicino" per la vera risposta. Se questo è il caso, allora può essere più semplice per convertire la stringa in un doppio e vedere se il valore assoluto della differenza tra i due doppie è a una certa tolleranza.

double string_to_double(const std::string &s)
{
    std::stringstream buffer(s);
    double d = 0.0;
    buffer >> d;
    return d;
}

bool match(const std::string &guess, double answer, int precision)
{
    const static double thresh[] = { 0.5, 0.05, 0.005, 0.0005, /* etc. */ };
    const double g = string_to_double(guess);
    const double delta = g - answer;
    return -thresh[precision] < delta && delta <= thresh[precision];
}

Un'altra possibilità è di arrotondare la risposta prima (mentre è ancora numerico) prima di convertirlo in una stringa.

bool match2(const std::string &guess, double answer, int precision)
{
    const static double thresh[] = {0.5, 0.05, 0.005, 0.0005, /* etc. */ };
    const double rounded = answer + thresh[precision];
    std::stringstream buffer;
    buffer << std::setprecision(precision) << rounded;
    return guess == buffer.str();
}

Entrambe queste soluzioni dovrebbero essere più veloce del tuo codice di esempio, ma non sono sicuro se lo fanno ciò che si vuole veramente.

Answer 8

Per quanto vedo si sta verificando se un arrotondata sui punti P è uguale b.

invece di cambiare una stringa, fare altra stringa strada e il cambiamento di raddoppiare - (solo moltiplicazioni e addion o solo additoins utilizzando tavolino) - poi sottrarre i due numeri e verificare se sottrazione sia in perfette gamma (se p == 1 => abs (p-a) <0,05)

Answer 9

Gli sviluppatori tempo vecchio trucco da secoli bui di sterline, Shilling e pence nel paese vecchio.

Il trucco era quello di memorizzare il valore come un numero intero fo mezze pennys. (O qualunque sia la vostra più piccola unità è). Poi tutta la vostra successiva arithmatic è semplice intero arithimatic e arrotondamento ecc si prenderà cura di se stessa.

Quindi nel tuo caso si memorizzano i dati in unità di 200ths di ciò che si sta contando, fare semplici calcoli interi su tali valori e dividere per 200 in un varaible galleggiante quando si desidera visualizzare il risultato.

I beleive Boost fa una biblioteca "BigDecimal" in questi giorni, ma, il vostro requisito per la velocità fase di esecuzione sarebbe probabilmente escludere questa altrimenti eccellente soluzione.

Answer 10

Sembra che quello che stai cercando di fare non è un vero e proprio di arrotondamento. 0.45 è infatti 0.45 in notazione binaria, e ,44999999343 non è la stessa cosa.

Può essere che si deve fare l'arrotondamento multipla -. Primo a dire 3 posti decimali, poi a due, poi a uno

La domanda è, che cosa stai cercando di realizzare? Se il vostro criterio di corrispondenza essere

abs(a-b) < 10 ** -p

, invece?