राउंडिंग पूर्णांक दिनचर्या

Question

ऐसा कुछ है जो मुझे ट्यूटोरियल में पूर्णांक अंकगणितीय के साथ परेशान करता है। सटीक, पूर्णांक विभाजन होना।

प्रतीत होता है पसंदीदा तरीका एक नाव में भाजक कास्टिंग, तो निकटतम पूर्ण संख्या के लिए नाव गोलाई से है, तो डाली कि वापस पूर्णांक में:

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

फिर भी इस के साथ अपने बाएं कान खरोंच की तरह लगता है आपका दाहिना हाथ क्या मैं का उपयोग करें:

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

यह कोई सफलता है, लेकिन तथ्य यह है कि यह मानक नहीं है मुझे आश्चर्य है कि अगर मैं कुछ भी याद आ रही है बनाता है? मेरे (हालांकि सीमित) परीक्षण के बावजूद, मुझे कोई परिदृश्य नहीं मिला जहां दो विधियां मुझे अलग-अलग परिणाम देती हैं। क्या किसी ने किसी प्रकार के परिदृश्य में भाग लिया जहां int-> float-> int कास्टिंग ने अधिक सटीक परिणाम दिए?

Answer 1

मानक समाधान पसंद करते हैं। Cstdlib में घोषित कार्यों के std :: div परिवार का प्रयोग करें।

देखें: http://en.cppreference.com/w/cpp/numeric/math/div

संपादित करें: तो फ्लोट करने के लिए int करने के लिए कुछ आर्किटेक्चर पर बहुत अक्षम हो सकता है कास्टिंग, e.x. माइक्रोकंट्रोलर्स।

Answer 2

यह वास्तव में प्रोसेसर पर निर्भर करेगा, और पूर्णांक जो बेहतर है की सीमा (और double का उपयोग कर सीमा मुद्दों के सबसे हल होगा) x86-64 और एआरएम तरह

आधुनिक "बड़ी" सीपीयू के लिए, पूर्णांक विभाजन और फ़्लोटिंग प्वाइंट डिवीजन मोटे तौर पर एक ही प्रयास है, और एक फ्लोट या इसके विपरीत एक पूर्णांक को परिवर्तित करना "कठिन" कार्य नहीं है (और कम से कम उस रूपांतरण में सही राउंडिंग करता है), इसलिए परिणामस्वरूप ऑपरेशन कर रहे हैं।

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

लगभग चार मशीन निर्देश।

दूसरी ओर, आपका कोड दो विभाजन, एक मॉड्यूलो और एक गुणा का उपयोग करता है, जो इस तरह के प्रोसेसर पर काफी अधिक संभावना है।

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

तो पाँच निर्देश है, और उन में से तीन "विभाजन" हैं (जब तक संकलक काफी चालाक a % b के लिए a/b का पुन: उपयोग करने के लिए है - लेकिन यह अभी भी दो अलग-अलग विभाजित है)।

बेशक, यदि आप अंकों की संख्या के बाहर हैं जो फ्लोट या डबल अंक खोने के बिना पकड़ सकते हैं (फ्लोट के लिए 23 बिट्स, डबल के लिए 53 बिट्स), तो आपकी विधि बेहतर हो सकती है (मान लीजिए कि कोई नहीं है पूर्णांक गणित में अतिप्रवाह)।

उन सभी के शीर्ष पर, क्योंकि पहले फॉर्म का उपयोग "हर किसी" द्वारा किया जाता है, यह वह है जिसे संकलक पहचानता है और अनुकूलित कर सकता है।

जाहिर है, परिणाम दोनों संकलक इस्तेमाल किया जा रहा है और प्रोसेसर पर चलता है यह इस पर निर्भर है, लेकिन इन कोड ऊपर पोस्ट, clang++ (v3.9-रिलीज के माध्यम से संकलित चलने से मेरे परिणाम, सुंदर जारी किया गया के करीब हैं 3.8)।

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

हालांकि, दिलचस्प बात यह है मुझे लगता है कि जब मैं उत्पन्न कोड को देखो:

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 

कि round वास्तव में एक फोन है। जो वास्तव में मुझे आश्चर्यचकित करता है, लेकिन बताता है कि कुछ मशीनों (विशेष रूप से अधिक हालिया x86 प्रोसेसर) पर, यह तेज़ है।

g++-ffast-math साथ बेहतर परिणाम है, जो चारों ओर देता है देता है:

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

(यह 100k मूल्यों की वृद्धि हुई गिनती के साथ है)

Answer 3

अंकगणित समाधान

यदि एक परिभाषित क्या आपके कार्यों लौटना चाहिए , वह इसे f(a, b) के करीब कुछ के रूप में वर्णित करेगी a के विभाजन के निकटतम निकटतमअसली विभाजक अंगूठी में। "

इस प्रकार, प्रश्न को संक्षेप में सारांशित किया जा सकता है, क्या हम केवल पूर्णांक विभाजन का उपयोग करके इस निकटतम पूर्णांक को परिभाषित कर सकते हैं। मुझे लगता है हम कर सकते हैं।

निकटतम पूर्णांक के रूप में वास्तव में दो उम्मीदवारों नहीं है: a/b और (a/b) + 1 (1)। चयन आसान है, अगर a % b0 के करीब है क्योंकि यह b है, तो a/b हमारा परिणाम है। यदि नहीं, (a/b) + 1 है।

एक लिखने, अनदेखी अनुकूलन और अच्छी प्रथाओं के लिए कुछ इसी तरह कर सकते हैं:

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

हालांकि इस परिभाषा की जरूरत है बाहर संतुष्ट करता है, एक यह b द्वारा कंप्यूटिंग उपयोग के साथ दो बार 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; 
} 

समस्या हम पहले किया था हमारे कार्यान्वयन की अच्छी तरह से परिभाषित व्यवहार से हमें भरोसा दिलाते का विश्लेषण।

(1) जांच करने के लिए केवल एक आखिरी बात है: a या b नकारात्मक होने पर यह कैसा व्यवहार करता है? यह पाठक के लिए छोड़ दिया गया है;)।

बेंचमार्क

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

आउटपुट:

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

दो अंकगणित समाधान के प्रदर्शन कर रहे हैं नहीं अलग पहचाना (उनके बेंचमार्क अभिसरण जब आप बेंच आकार पैमाने)।

Answer 4

अभी तक सुझावों के लिए धन्यवाद। कुछ प्रकाश डालने के लिए मैंने प्रदर्शन की तुलना करने के लिए एक परीक्षण सेटअप किया।

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

परिणाम मैं अपने मशीन पर मिल गया (vs2015 साथ i7) इस प्रकार था: सापेक्ष गणित के रूप में तेजी से int-> float-> पूर्णांक कास्टिंग विधि के रूप में के बारे में दो बार किया गया था। पर निर्भर विधि std :: div_t (@YSC और @teroi द्वारा सुझाई गई) तेजी से int-> float-> int, लेकिन मॉड्यूलो अंकगणितीय विधि से धीमी है।

संपादित एक दूसरा परीक्षण कुछ संकलक अनुकूलन @YSC द्वारा बताया बचने के लिए प्रदर्शन किया गया था: # शामिल # शामिल # शामिल # शामिल # शामिल # शामिल नाम स्थान एसटीडी का उपयोग करते हुए;

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

इस दूसरे टेस्ट धीमी में std :: div_t, divide_by_float() द्वारा पीछा किया पर divide_by_quotient() निर्भर था, और सबसे तेजी से फिर से divide_by_modulo() था। हालांकि इस बार प्रदर्शन अंतर बहुत कम था, 20% से कम था।