rounding interi di routine

Question

C'è qualcosa che mi confonde con l'aritmetica dei numeri interi nei tutorial. Per essere precisi, divisione intera.

Il metodo apparentemente preferito è gettando il divisore in un galleggiante, poi arrotondare il galleggiante al numero intero più vicino, quindi cast che di nuovo in numero intero:

#include <cmath> 
int round_divide_by_float_casting(int a, int b){ 
    return (int) std::roundf(a/(float) b); 
} 

Eppure questo sembra come grattarsi l'orecchio sinistro con la tua mano destra. Quello che uso è:

int round_divide (int a, int b){ 
    return a/b + a % b * 2/b; 
} 

Non è un passo avanti, ma il fatto che non è standard mi domando se mi manca qualcosa? Nonostante il mio (anche se limitato) test, non sono riuscito a trovare nessuno scenario in cui i due metodi mi danno risultati diversi. Qualcuno si è imbattuto in una sorta di scenario in cui il casting int-> float-> int ha prodotto risultati più accurati?

Answer 1

Preferire la soluzione standard. Utilizzare la famiglia di funzioni std :: div dichiarata in cstdlib.

See: http://en.cppreference.com/w/cpp/numeric/math/div

edit: fusione a stare a galla poi a int può essere molto inefficiente su alcune architetture, e.x. microcontrollori.

Answer 2

sarebbe davvero dipende dal processore, e la gamma di numero intero che è meglio (e usando double risolverebbe gran parte dei problemi di range)

per le moderne CPU "grandi" come x86-64 e ARM, la divisione intera e la divisione in virgola mobile sono grosso modo lo stesso, e la conversione di un intero in un float o viceversa non è un'attività "difficile" (e fa l'arrotondamento corretto direttamente in quella conversione, almeno), quindi molto probabilmente le operazioni risultanti siamo.

atmp = (float) a; 
btmp = (float) b; 
resfloat = divide atmp/btmp; 
return = to_int_with_rounding(resfloat) 

Informazioni su quattro istruzioni della macchina.

D'altra parte, il codice utilizza due divisioni, un modulo e un multiplo, che è molto probabilmente più lungo su tale processore.

tmp = a/b; 
tmp1 = a % b; 
tmp2 = tmp1 * 2; 
tmp3 = tmp2/b; 
tmp4 = tmp + tmp3; 

Così cinque istruzioni, e tre di questi sono "dividere" (a meno che il compilatore è abbastanza intelligente da riutilizzare a/b per a % b - ma è ancora due divisioni distinte).

Ovviamente, se si è al di fuori dell'intervallo di numero di cifre che un float o un double può contenere senza perdere cifre (23 bit per float, 53 bit per doppio), allora il metodo potrebbe essere migliore (supponendo che non ci sia overflow nella matematica intera).

Inoltre, poiché il primo modulo è utilizzato da "tutti", è quello che il compilatore riconosce e può ottimizzare.

Ovviamente, i risultati dipendono sia dal compilatore in uso sia dal processore su cui viene eseguito, ma questi sono i miei risultati dall'esecuzione del codice pubblicato sopra, compilato tramite clang++ (v3.9-pre-release, abbastanza vicino a rilasciato 3.8).

round_divide_by_float_casting(): 32.5 ns 
      round_divide_by_modulo(): 113 ns 
    divide_by_quotient_comparison(): 80.4 ns 

Tuttavia, la cosa interessante che ho trovato quando guardo il codice generato:

xorps %xmm0, %xmm0 
cvtsi2ssl 8016(%rsp,%rbp), %xmm0 
xorps %xmm1, %xmm1 
cvtsi2ssl 4016(%rsp,%rbp), %xmm1 
divss %xmm1, %xmm0 
callq roundf 
cvttss2si %xmm0, %eax 
movl %eax, 16(%rsp,%rbp) 
addq $4, %rbp 
cmpq $4000, %rbp    # imm = 0xFA0 
jne .LBB0_7 

è che il round è in realtà una chiamata. Il che mi sorprende, ma spiega perché su alcune macchine (in particolare i processori x86 più recenti), è più veloce.

g++ dà risultati migliori con -ffast-math, che dà giro:

round_divide_by_float_casting(): 17.6 ns 
      round_divide_by_modulo(): 43.1 ns 
    divide_by_quotient_comparison(): 18.5 ns 

(questo è con una maggiore conteggio a 100k valori)

Answer 3

soluzione aritmetica

Se uno definite quali sono le vostre funzioni dovrebbero tornare , lo descriveva come qualcosa di simile a "f(a, b) restituisce il numero intero più vicino del risultato della divisione di a entro il b nel vero anello divisorio. "

Così, la domanda può essere riassunta come, possiamo definire questo numero intero più vicino usando solo la divisione intera. Penso che possiamo

C'è esattamente due candidati come la più vicino intero: a/b e (a/b) + 1 (1). La selezione è semplice, se a % b è più vicino a 0 come a b, quindi il nostro risultato è a/b. In caso contrario, è (a/b) + 1.

Si potrebbe l'qualcosa di scrittura simile a, ignorando l'ottimizzazione e le buone pratiche:

int divide(int a, int b) 
{ 
    const int quot = a/b; 
    const int rem = a % b; 
    int result; 

    if (rem < b - rem) { 
     result = quot; 
    } else { 
     result = quot + 1; 
    } 
    return result; 
} 

Mentre questa definizione soddisfa le esigenze, si potrebbe ottimizzarlo da non calcolando due volte la divisione di a dal b con l'uso di std::div():

int divide(int a, int b) 
{ 
    const std::div_t dv = std::div(a, b); 
    int result = dv.quot; 

    if (dv.rem >= b - dv.rem) { 
     ++result; 
    } 
    return result; 
} 

l'analisi del problema che abbiamo fatto in precedenza ci assicura del comportamento ben definito della nostra implementazione.

(1) C'è solo un'ultima cosa da controllare: come si comporta quando a o è negativo? Questo è lasciato al lettore;).

Benchmark

#include <iostream> 
#include <iomanip> 
#include <string> 

// solutions 
#include <cmath> 
#include <cstdlib> 

// benchmak 
#include <limits> 
#include <random> 
#include <chrono> 
#include <algorithm> 
#include <functional> 

// 
// Solutions 
// 
namespace 
{ 
    int round_divide_by_float_casting(int a, int b) { 
     return (int)roundf(a/(float)b); 
    } 

    int round_divide_by_modulo(int a, int b) { 
     return a/b + a % b * 2/b; 
    } 

    int divide_by_quotient_comparison(int a, int b) 
    { 
     const std::div_t dv = std::div(a, b); 
     int result = dv.quot; 

     if (dv.rem >= b - dv.rem) 
     { 
      ++result; 
     } 
     return result; 
    } 
} 

// 
// benchmark 
// 
class Randomizer 
{ 
    std::mt19937 _rng_engine; 
    std::uniform_int_distribution<int> _distri; 

public: 
    Randomizer() : _rng_engine(std::time(0)), _distri(std::numeric_limits<int>::min(), std::numeric_limits<int>::max()) 
    { 
    } 

    template<class ForwardIt> 
    void operator()(ForwardIt begin, ForwardIt end) 
    { 
     std::generate(begin, end, std::bind(_distri, _rng_engine)); 
    } 
}; 

class Clock 
{ 
    std::chrono::time_point<std::chrono::steady_clock> _start; 

public: 
    static inline std::chrono::time_point<std::chrono::steady_clock> now() { return std::chrono::steady_clock::now(); } 

    Clock() : _start(now()) 
    { 
    } 

    template<class DurationUnit> 
    std::size_t end() 
    { 
     return std::chrono::duration_cast<DurationUnit>(now() - _start).count(); 
    } 
}; 

// 
// Entry point 
// 
int main() 
{ 
    Randomizer randomizer; 
    std::array<int, 1000> dividends; // SCALE THIS UP (1'000'000 would be great) 
    std::array<int, dividends.size()> divisors; 
    std::array<int, dividends.size()> results; 
    randomizer(std::begin(dividends), std::end(dividends)); 
    randomizer(std::begin(divisors), std::end(divisors)); 

    { 
     Clock clock; 
     auto dividend = std::begin(dividends); 
     auto divisor = std::begin(divisors); 
     auto result = std::begin(results); 
     for (; dividend != std::end(dividends) ; ++dividend, ++divisor, ++result) 
     { 
      *result = round_divide_by_float_casting(*dividend, *divisor); 
     } 
     const float unit_time = clock.end<std::chrono::nanoseconds>()/static_cast<float>(results.size()); 
     std::cout << std::setw(40) << "round_divide_by_float_casting(): " << std::setprecision(3) << unit_time << " ns\n"; 
    } 
    { 
     Clock clock; 
     auto dividend = std::begin(dividends); 
     auto divisor = std::begin(divisors); 
     auto result = std::begin(results); 
     for (; dividend != std::end(dividends) ; ++dividend, ++divisor, ++result) 
     { 
      *result = round_divide_by_modulo(*dividend, *divisor); 
     } 
     const float unit_time = clock.end<std::chrono::nanoseconds>()/static_cast<float>(results.size()); 
     std::cout << std::setw(40) << "round_divide_by_modulo(): " << std::setprecision(3) << unit_time << " ns\n"; 
    } 
    { 
     Clock clock; 
     auto dividend = std::begin(dividends); 
     auto divisor = std::begin(divisors); 
     auto result = std::begin(results); 
     for (; dividend != std::end(dividends) ; ++dividend, ++divisor, ++result) 
     { 
      *result = divide_by_quotient_comparison(*dividend, *divisor); 
     } 
     const float unit_time = clock.end<std::chrono::nanoseconds>()/static_cast<float>(results.size()); 
     std::cout << std::setw(40) << "divide_by_quotient_comparison(): " << std::setprecision(3) << unit_time << " ns\n"; 
    } 
} 

Uscite:

g++ -std=c++11 -O2 -Wall -Wextra -Werror main.cpp && ./a.out 
     round_divide_by_float_casting(): 54.7 ns 
       round_divide_by_modulo(): 24 ns 
     divide_by_quotient_comparison(): 25.5 ns 

Demo

prestazioni delle due soluzioni aritmetiche non sono distinguibili (il loro punto di riferimento converge quando si scala la dimensione panca up).

Answer 4

Grazie per i suggerimenti finora. per far luce ho fatto un setup di test per confrontare le prestazioni.

#include <iostream> 
#include <string> 
#include <cmath> 
#include <cstdlib> 
#include <chrono> 

using namespace std; 

int round_divide_by_float_casting(int a, int b) { 
    return (int)roundf(a/(float)b); 
} 

int round_divide_by_modulo(int a, int b) { 
    return a/b + a % b * 2/b; 
} 

int divide_by_quotient_comparison(int a, int b) 
{ 
    const std::div_t dv = std::div(a, b); 
    int result = dv.quot; 

    if (dv.rem <= b - dv.rem) { 
     ++result; 
    } 
    return result; 
} 

int main() 
{ 
    int itr = 1000; 

    //while (true) { 
     auto begin = chrono::steady_clock::now(); 
     for (int i = 0; i < itr; i++) { 
      for (int j = 10; j < itr + 1; j++) { 
       divide_by_quotient_comparison(i, j); 
      } 
     } 
     auto end = std::chrono::steady_clock::now(); 
     cout << "divide_by_quotient_comparison(,) function took : " << chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() << endl; 

     begin = chrono::steady_clock::now(); 
     for (int i = 0; i < itr; i++) { 
      for (int j = 10; j < itr + 1; j++) { 
       round_divide_by_float_casting(i, j); 
      } 
     } 
     end = std::chrono::steady_clock::now(); 
     cout << "round_divide_by_float_casting(,) function took : " << chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() << endl; 

     begin = chrono::steady_clock::now(); 
     for (int i = 0; i < itr; i++) { 
      for (int j = 10; j < itr + 1; j++) { 
       round_divide_by_modulo(i, j); 
      } 
     } 
     end = std::chrono::steady_clock::now(); 
     cout << "round_divide_by_modulo(,) function took : " << chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() << endl; 

    //} 

    return 0; 
} 

I risultati che ho ottenuto sulla mia macchina (i7 con vs2015) era la seguente: l'aritmetica modulo era di circa due volte più veloce l'INT> flottante> int metodo fusione . il metodo basato su std :: div_t (suggerito da @YSC e @teroi) era più veloce del int-> float-> int, ma più lento del metodo aritmetico modulo.

EDIT Un secondo test è stato eseguito per evitare certe ottimizzazioni di compilazione evidenziate dalla @YSC: #include #include #include #include #include #include using namespace std;

int round_divide_by_float_casting(int a, int b) { 
    return (int)roundf(a/(float)b); 
} 

int round_divide_by_modulo(int a, int b) { 
    return a/b + a % b * 2/b; 
} 

int divide_by_quotient_comparison(int a, int b) 
{ 
    const std::div_t dv = std::div(a, b); 
    int result = dv.quot; 

    if (dv.rem <= b - dv.rem) { 
     ++result; 
    } 
    return result; 
} 

int main() 
{ 
    int itr = 100; 
    vector <int> randi, randj; 
    for (int i = 0; i < itr; i++) { 
     randi.push_back(rand()); 
     int rj = rand(); 
     if (rj == 0) rj++; 
     randj.push_back(rj); 
    } 
    vector<int> f, m, q; 

    while (true) { 
     auto begin = chrono::steady_clock::now(); 
     for (int i = 0; i < itr; i++) { 
      for (int j = 0; j < itr; j++) { 
       q.push_back(divide_by_quotient_comparison(randi[i] , randj[j])); 
      } 
     } 
     auto end = std::chrono::steady_clock::now(); 
     cout << "divide_by_quotient_comparison(,) function took : " << chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() << endl; 

     begin = chrono::steady_clock::now(); 
     for (int i = 0; i < itr; i++) { 
      for (int j = 0; j < itr; j++) { 
       f.push_back(round_divide_by_float_casting(randi[i], randj[j])); 
      } 
     } 
     end = std::chrono::steady_clock::now(); 
     cout << "round_divide_by_float_casting(,) function took : " << chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() << endl; 

     begin = chrono::steady_clock::now(); 
     for (int i = 0; i < itr; i++) { 
      for (int j = 0; j < itr; j++) { 
       m.push_back(round_divide_by_modulo(randi[i], randj[j])); 
      } 
     } 
     end = std::chrono::steady_clock::now(); 
     cout << "round_divide_by_modulo(,) function took : " << chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() << endl; 
     cout << endl; 

     f.clear(); m.clear(); q.clear(); 
    } 

    return 0; 
} 

In questo secondo test il più lento è stato il divide_by_quotient() affidamento su std :: div_t, seguita da divide_by_float(), e ancora una volta il più veloce è stato il divide_by_modulo(). tuttavia questa volta la differenza di prestazioni era molto, molto più bassa, meno del 20%.