làm tròn số nguyên thường lệ

Question

Có điều gì đó khiến tôi bị sai số học số nguyên trong hướng dẫn. Để được chính xác, phân chia số nguyên.

Phương pháp dường như ưa thích là bởi đúc số chia thành một phao, sau đó làm tròn các phao đến số nguyên gần nhất, sau đó đúc mà lại vào số nguyên:

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

Tuy nhiên điều này có vẻ như gãi tai trái của bạn với tay phải của bạn. Những gì tôi sử dụng là:

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

Nó không phải là bước đột phá, nhưng thực tế là nó không phải là tiêu chuẩn làm cho tôi tự hỏi nếu tôi thiếu bất cứ điều gì? Mặc dù thử nghiệm của tôi (mặc dù có giới hạn), tôi không thể tìm thấy bất kỳ kịch bản nào trong đó hai phương pháp cho tôi kết quả khác nhau. Đã có ai đó chạy vào một số loại kịch bản mà int-> float-> int đúc sản xuất kết quả chính xác hơn?

Answer 1

Ưu tiên giải pháp tiêu chuẩn. Sử dụng std :: div family của các hàm được khai báo trong cstdlib.

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

chỉnh sửa: đúc nổi sau đó đến int có thể rất hiệu quả trên một số kiến ​​trúc, e.x. vi điều khiển.

Answer 2

Nó sẽ thực sự phụ thuộc vào bộ vi xử lý, và phạm vi của các số nguyên mà là tốt hơn (và sử dụng double sẽ giải quyết hầu hết các vấn đề range)

Đối với CPU "lớn" hiện đại như x86-64 và ARM, phân chia số nguyên và phân chia dấu phẩy động là nỗ lực tương tự, và chuyển đổi một số nguyên thành phao hoặc ngược lại không phải là một nhiệm vụ "cứng" (và làm tròn chính xác trực tiếp trong chuyển đổi đó). là.

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

Giới thiệu về bốn hướng dẫn máy.

Mặt khác, mã của bạn sử dụng hai lần chia, một modulo và một số nhân, có khả năng dài hơn trên bộ xử lý như vậy.

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

Vì vậy lăm hướng dẫn, và ba trong số đó là những "chia" (trừ khi trình biên dịch là đủ thông minh để tái sử dụng a/b cho a % b - nhưng nó vẫn còn hai phân chia riêng biệt).

Tất nhiên, nếu bạn ở ngoài phạm vi số chữ số mà phao hoặc kép có thể giữ mà không làm mất chữ số (23 bit cho float, 53 bit cho double), thì phương pháp của bạn CÓ THỂ tốt hơn (giả sử không có tràn trong toán số nguyên).

Trên tất cả, vì biểu mẫu đầu tiên được sử dụng bởi "mọi người", đó là biểu mẫu mà trình biên dịch nhận ra và có thể tối ưu hóa. Rõ ràng, các kết quả phụ thuộc vào cả trình biên dịch đang được sử dụng và bộ xử lý nó chạy, nhưng đây là kết quả của tôi từ việc chạy mã được đăng ở trên, được biên dịch qua clang++ (v3.9-trước khi phát hành, khá gần để phát hành 3.8).

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

Tuy nhiên, điều thú vị tôi thấy khi tôi nhìn vào mã được tạo:

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 

là round thực sự là một cuộc gọi. Điều thực sự làm tôi ngạc nhiên, nhưng giải thích tại sao trên một số máy (đặc biệt là các bộ vi xử lý x86 gần đây), nó nhanh hơn.

g++ cho kết quả tốt hơn với -ffast-math, mang đến cho xung quanh:

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

(Đây là với tăng đếm đến 100k giá trị)

Answer 3

giải pháp số học

Nếu một định nghĩa những gì chức năng của bạn nên quay trở lại , cô ấy sẽ mô tả nó như một cái gì đó gần như "f(a, b) trả về số nguyên gần nhất của kết quả của sự phân chia của a bởi b trong vòng chia số thực. "

Do đó, câu hỏi có thể được tóm tắt là, chúng ta có thể định nghĩa số nguyên gần nhất này bằng cách sử dụng chỉ phân chia số nguyên. Tôi nghĩ rằng chúng ta có thể.

Có chính xác hai ứng cử viên là số nguyên gần nhất: a/b và (a/b) + 1 (1). Việc lựa chọn rất dễ dàng, nếu a % b gần hơn với 0 vì nó là b, thì a/b là kết quả của chúng tôi. Nếu không, (a/b) + 1 là.

Người ta có thể write một cái gì đó tương tự, bỏ qua tối ưu hóa và thông lệ tốt:

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; 
} 

Trong khi định nghĩa này đáp ứng ra nhu cầu, người ta có thể tối ưu hóa nó bằng cách không tính hai lần so với bộ phận của a bởi b với việc sử dụng của 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; 
} 

Phân tích sự cố chúng tôi đã đảm bảo với chúng tôi về hành vi được xác định rõ.

(1) Chỉ có một điều cuối cùng cần kiểm tra: nó hoạt động như thế nào khi a hoặc b là số âm? Điều này được để lại cho người đọc;).

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"; 
    } 
} 

Đầu ra:

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

màn trình diễn Hai giải pháp số học không rõ rệt (benchmark của họ hội tụ khi bạn mở rộng kích thước băng ghế dự bị lên).

Answer 4

Cảm ơn bạn đã đề xuất cho đến thời điểm này. để làm sáng tỏ một số thiết lập thử nghiệm để so sánh hiệu suất.

#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; 
} 

Kết quả tôi đã nhận trên máy tính của tôi (i7 với vs2015) là như sau: số học modulo là khoảng gấp đôi nhanh như int-> mảng bè> int phương pháp đúc. phương pháp dựa trên std :: div_t (được đề xuất bởi @YSC và @teroi) nhanh hơn là int-> float-> int, nhưng chậm hơn so với phương pháp số học modulo.

EDIT Một thử nghiệm thứ hai được thực hiện để tránh một số tối ưu hóa trình biên dịch chỉ ra bởi @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; 
} 

Trong thử nghiệm thứ hai này, chậm nhất là divide_by_quotient() phụ thuộc vào std :: div_t, tiếp theo là divide_by_float(), và nhanh nhất lại là divide_by_modulo(). tuy nhiên lần này sự khác biệt về hiệu suất là rất nhiều, thấp hơn nhiều, dưới 20%.