math बिट बदलावों का उपयोग करके 10 तक विभाजित करें?




low-level bit (5)

यहां छोटे इंटीग्रल स्थिरांक द्वारा डिवीजन संकलित करते समय माइक्रोसॉफ्ट कंपाइलर करता है। 32-बिट मशीन मानें (कोड तदनुसार समायोजित किया जा सकता है):

int32_t div10(int32_t dividend)
{
    int64_t invDivisor = 0x1999999A;
    return (int32_t) ((invDivisor * dividend) >> 32);
}

यहां क्या हो रहा है कि हम 1/10 * 2 ^ 32 के नज़दीकी अनुमान से गुणा कर रहे हैं और फिर 2 ^ 32 को हटा रहे हैं। इस दृष्टिकोण को विभिन्न divisors और विभिन्न बिट चौड़ाई के लिए अनुकूलित किया जा सकता है।

यह ia32 आर्किटेक्चर के लिए बहुत अच्छा काम करता है, क्योंकि इसके IMUL निर्देश 64-बिट उत्पाद को एडैक्स में डाल देंगे: eax, और edx मान वांछित मान होगा। जैसे (माना जाता है कि लाभांश ईएक्स में पारित किया गया है और ईएक्स में लौटाया गया है)

div10 proc 
    mov    edx,1999999Ah    ; load 1/10 * 2^32
    imul   eax              ; edx:eax = dividend / 10 * 2 ^32
    mov    eax,edx          ; eax = dividend / 10
    ret
    endp

एक धीमी गुणा निर्देश के साथ एक मशीन पर भी, यह एक सॉफ्टवेयर विभाजन से तेज होगा।

शुद्ध बिट बदलाव, जोड़, घटाव और शायद गुणा करके 10 से एक हस्ताक्षरित पूर्णांक को विभाजित करना संभव है? बहुत सीमित संसाधनों और धीमी गति से विभाजित प्रोसेसर का उपयोग करना।


हालांकि अब तक दिए गए उत्तर वास्तविक प्रश्न से मेल खाते हैं, लेकिन वे शीर्षक से मेल नहीं खाते हैं। तो यहां एक समाधान हैकर हैरस की डिलाइट से प्रेरित है जो वास्तव में केवल बिट बदलावों का उपयोग करता है।

unsigned divu10(unsigned n) {
    unsigned q, r;
    q = (n >> 1) + (n >> 2);
    q = q + (q >> 4);
    q = q + (q >> 8);
    q = q + (q >> 16);
    q = q >> 3;
    r = n - (((q << 2) + q) << 1);
    return q + (r > 9);
}

मुझे लगता है कि आर्किटेक्चर के लिए यह सबसे अच्छा समाधान है जिसमें गुणा निर्देश की कमी है।


आर्किटेक्चर पर जो केवल एक ही समय में एक स्थान को स्थानांतरित कर सकता है, 10 से गुणा की कम शक्तियों के खिलाफ स्पष्ट तुलना की श्रृंखला समाधान फॉर्म हैकर की खुशी से बेहतर काम कर सकती है। 16 बिट लाभांश मानते हुए:

uint16_t div10(uint16_t dividend) {
  uint16_t quotient = 0;
  #define div10_step(n) \
    do { if (dividend >= (n*10)) { quotient += n; dividend -= n*10; } } while (0)
  div10_step(0x1000);
  div10_step(0x0800);
  div10_step(0x0400);
  div10_step(0x0200);
  div10_step(0x0100);
  div10_step(0x0080);
  div10_step(0x0040);
  div10_step(0x0020);
  div10_step(0x0010);
  div10_step(0x0008);
  div10_step(0x0004);
  div10_step(0x0002);
  div10_step(0x0001);
  #undef div10_step
  if (dividend >= 5) ++quotient; // round the result (optional)
  return quotient;
}

क्यूबा ओबेर की प्रतिक्रिया को ध्यान में रखते हुए, एक ही नस में एक और है। यह परिणाम के पुनरावृत्ति अनुमान का उपयोग करता है, लेकिन मुझे किसी भी आश्चर्यजनक प्रदर्शन की उम्मीद नहीं होगी।

मान लें कि हमें x खोजना है जहां x = v / 10

हम उलटा ऑपरेशन v = x * 10 उपयोग करेंगे क्योंकि इसमें अच्छी संपत्ति है कि जब x = a + b , तो x * 10 = a * 10 + b * 10

परिणाम का सबसे अच्छा अनुमान लगाने के लिए x को वैरिएबल के रूप में उपयोग करने दें। जब खोज समाप्त होती है, x परिणाम धारण करेगा। हम x प्रत्येक बिट b को सबसे महत्वपूर्ण से कम महत्वपूर्ण, एक-एक करके, अंत तुलना (x + b) * 10 साथ सेट करेंगे। यदि इसका छोटा या बराबर v , तो बिट b x में सेट है। अगली बिट का परीक्षण करने के लिए, हम बस बी को एक स्थिति को दाएं स्थानांतरित करते हैं (दो से विभाजित)।

हम x * 10 और b * 10 को अन्य चरों में रखते हुए गुणा से बच सकते हैं।

यह v द्वारा 10 को विभाजित करने के लिए निम्नलिखित एल्गोरिदम उत्पन्न करता है।

uin16_t x = 0, x10 = 0, b = 0x1000, b10 = 0xA000;
while (b != 0) {
    uint16_t t = x10 + b10;
    if (t <= v) {
        x10 = t;
        x |= b;
    }
    b10 >>= 1;
    b >>= 1;
}
// x = v / 10

संपादित करें: क्यूबा ओबेर के एल्गोरिदम प्राप्त करने के लिए जो चर x10 की आवश्यकता से बचाता है, हम इसके बजाय v और v10 से b10 घटा सकते हैं। इस मामले में x10 की अब आवश्यकता नहीं है। एल्गोरिदम बन जाता है

uin16_t x = 0, b = 0x1000, b10 = 0xA000;
while (b != 0) {
    if (b10 <= v) {
        v -= b10;
        x |= b;
    }
    b10 >>= 1;
    b >>= 1;
}
// x = v / 10

लूप को अनदेखा किया जा सकता है और b और b के विभिन्न मानों को स्थिरांक के रूप में प्रीकंप्यूट किया जा सकता है।


बेशक आप कर सकते हैं अगर आप परिशुद्धता में कुछ नुकसान के साथ रह सकते हैं। यदि आप अपने इनपुट मानों की मान सीमा जानते हैं तो आप थोड़ा बदलाव और एक गुणा के साथ आ सकते हैं जो सटीक है। कुछ उदाहरण हैं कि आप 10, 60, द्वारा विभाजित कैसे कर सकते हैं ... जैसा कि इस ब्लॉग में वर्णित किया गया है ताकि समय को सबसे तेज़ तरीका संभव बनाया जा सके।

temp = (ms * 205) >> 11;  // 205/2048 is nearly the same as /10

आपका, एलोइस क्रॉस





bit