बिट बदलावों का उपयोग कर मॉड्यूलो को फिर से कार्यान्वित करें?

Question

मैं एक बहुत सीमित सिस्टम के लिए कुछ कोड लिख रहा हूं जहां मॉड ऑपरेटर बहुत धीमा है। मेरे कोड में एक मॉड्यूलो प्रति सेकेंड 180 बार इस्तेमाल किया जाना चाहिए और मुझे लगा कि जितना संभव हो सके इसे हटाने से मेरे कोड की गति में काफी वृद्धि होगी, क्योंकि अब मेरे मेनलोप का एक चक्र 1/60 में नहीं चलता है दूसरा यह चाहिए। मैं सोच रहा था कि गुणा और विभाजन के साथ संभवतः थोड़ा बदलावों का उपयोग करके मॉड्यूलो को फिर से कार्यान्वित करना संभव था। तो सी ++ में अब तक मेरा कोड है (यदि मैं असेंबली का उपयोग करके मॉड्यूलो कर सकता हूं तो यह बेहतर होगा)। विभाजन या गुणा का उपयोग किए बिना मैं मॉड्यूल को कैसे हटा सकता हूं?

while(input > 0) 
{ 
    out = (out << 3) + (out << 1); 
    out += input % 10; 

    input = (input >> 8) + (input >> 1); 
} 

संपादित करें: असल में मैंने महसूस किया कि मैं इसे प्रति सेकंड रास्ता 180 से अधिक बार की ज़रूरत है। इनपुट के मूल्य के रूप में देखकर 40 अंकों तक बहुत बड़ी संख्या हो सकती है।

Answer 1

सरल बिटवाई ऑपरेशंस के साथ आप क्या कर सकते हैं मूल्य (लाभांश) की शक्ति-दो-मॉड्यूलो (divisor) को divisor-1 के साथ ले जा रहा है। कुछ उदाहरण:

unsigned int val = 123; // initial value 
unsigned int rem; 

rem = val & 0x3; // remainder after value is divided by 4. 
       // Equivalent to 'val % 4' 
rem = val % 5; // remainder after value is divided by 5. 
       // Because 5 isn't power of two, we can't simply AND it with 5-1(=4). 

यह क्यों काम करता है? मान 123 के लिए थोड़ा पैटर्न मानें जो 1111011 है और फिर divisor 4, जिसमें 00000100 का बिट पैटर्न है। जैसा कि हम अब तक जानते हैं, विभाजक को शक्ति-दो-दो होना चाहिए (जैसा कि 4 है) और हमें इसे एक से कम करने की आवश्यकता है (दशमलव में 4 से 3 तक) जो हमें थोड़ा पैटर्न 00000011 उत्पन्न करता है। हम bitwise के बाद- और मूल 123 और 3 दोनों, परिणामी बिट पैटर्न 00000011 होगा। यह दशमलव में 3 हो जाता है। हमें दो शक्तियों की शक्ति की आवश्यकता है कि एक बार जब हम उन्हें एक बार घटाते हैं, तो हमें 1 पर सेट की जाने वाली सभी कम महत्वपूर्ण बिट्स मिलती हैं और बाकी 0 हैं। एक बार जब हम थोड़ा सा करते हैं- और, यह मूल मूल्य से अधिक महत्वपूर्ण बिट्स को 'रद्द करता है', और हमें विभाजक द्वारा विभाजित मूल मूल्य के बाकी हिस्सों के साथ छोड़ देता है।

हालांकि, मनमाने ढंग से विभाजक के लिए इस तरह के कुछ विशिष्ट को लागू करने के लिए काम नहीं किया जा रहा है जब तक कि आप पहले से ही अपने divisors (संकलन समय पर, और फिर divisor- विशिष्ट codepaths की आवश्यकता है) - यह हल करने के लिए रन-टाइम व्यवहार्य नहीं है, विशेष रूप से आपके मामले में जहां प्रदर्शन मायने रखता है।

इसके अलावा a previous question related to the subject है जो शायद इस बिंदु पर विभिन्न बिंदुओं से दिलचस्प जानकारी है।

Answer 2

बिट बदलावों के साथ मॉड्यूलो 10 करना मुश्किल और बदसूरत होने वाला है, क्योंकि बिट बदलाव मूल रूप से बाइनरी हैं (किसी भी मशीन पर जो आप आज चल रहे हैं)। यदि आप इसके बारे में सोचते हैं, तो बिट बदलाव आसानी से गुणा या विभाजित होते हैं 2.

लेकिन एक स्पष्ट स्पेस-टाइम व्यापार है जो आप यहां कर सकते हैं: out और out % 10 के लिए मानों की एक तालिका सेट करें और इसे देखें। फिर लाइन

out += tab[out] 

और किसी भी किस्मत के साथ, यह एक 16-बिट एड और स्टोर ऑपरेशन बन जाएगा।

Answer 3

यदि आप मॉड्यूल 10 और बदलाव करना चाहते हैं, तो आप अपनी आवश्यकताओं के लिए double dabble algorithm अनुकूलित कर सकते हैं?

यह एल्गोरिदम का उपयोग मॉड्यूल या विभाजन का उपयोग किए बिना बाइनरी संख्याओं को दशमलव में बदलने के लिए किया जाता है।

Answer 4

6 में 16 की प्रत्येक शक्ति 6 ​​में समाप्त होती है।यदि आप 16 की शक्तियों के योग के रूप में संख्या का प्रतिनिधित्व करते हैं (यानी इसे nybbles में तोड़ दें), तो प्रत्येक शब्द किसी के स्थान को छोड़कर, उसी अंक में अंतिम अंक में योगदान देता है।

0x481A % 10 = (0x4 * 6 + 0x8 * 6 + 0x1 * 6 + 0xA) % 10 

ध्यान दें कि 6 = 5 + 1, और 5 की रद्द हो जाएगी यदि उनमें से कोई भी संख्या है। तो बस nybbles (आखिरी एक को छोड़कर) योग करें और अगर परिणाम अजीब है तो 5 जोड़ें।

0x481A % 10 = (0x4 + 0x8 + 0x1 /* sum = 13 */ 
       + 5 /* so add 5 */ + 0xA /* and the one's place */) % 10 
      = 28 % 10 

यह सबसे 0xF * 4 + 5 = 65 पर एक नंबर करने के 16-बिट, 4-nybble सापेक्ष कम कर देता है। बाइनरी में, यह अभी भी परेशान है 3 nybbles तो आपको एल्गोरिदम दोहराना होगा (हालांकि उनमें से एक वास्तव में गिनती नहीं है)।

लेकिन 286 में उचित कुशल बीसीडी अतिरिक्त होना चाहिए जिसका उपयोग आप योग करने के लिए कर सकते हैं और परिणाम को एक पास में प्राप्त कर सकते हैं। (इसके लिए प्रत्येक एनबबल को मैन्युअल रूप से बीसीडी में परिवर्तित करने की आवश्यकता है; मुझे प्लेटफ़ॉर्म के बारे में पर्याप्त जानकारी नहीं है कि यह कैसे अनुकूलित किया जाए या यह समस्याग्रस्त हो।)

Answer 5

वास्तव में स्थिरांक द्वारा विभाजन संकलक के लिए एक प्रसिद्ध अनुकूलन है और वास्तव में, जीसीसी पहले से ही कर रहा है।

यह सरल कोड का टुकड़ा:

int mod(int val) { 
    return val % 10; 
} 

-O3 के साथ मेरी नहीं बल्कि पुराने जीसीसी का निम्न कोड उत्पन्न करता है:

_mod: 
     push ebp 
     mov  edx, 1717986919 
     mov  ebp, esp 
     mov  ecx, DWORD PTR [ebp+8] 
     pop  ebp 
     mov  eax, ecx 
     imul edx 
     mov  eax, ecx 
     sar  eax, 31 
     sar  edx, 2 
     sub  edx, eax 
     lea  eax, [edx+edx*4] 
     mov  edx, ecx 
     add  eax, eax 
     sub  edx, eax 
     mov  eax, edx 
     ret 

आप समारोह उपसंहार/प्रस्तावना दो muls उपेक्षा, मूल रूप से (यदि वास्तव में x86 पर हम भाग्यशाली हैं और एक के लिए ली का उपयोग कर सकते हैं) और कुछ बदलाव और जोड़/subs। मुझे पता है कि मैंने पहले ही इस अनुकूलन के पीछे सिद्धांत को समझाया है, इसलिए मैं देखूंगा कि मैं इसे फिर से समझाए जाने से पहले उस पोस्ट को पा सकता हूं या नहीं।

अब आधुनिक सीपीयू पर जो स्मृति तक पहुंचने से निश्चित रूप से तेज़ है (भले ही आप कैश हिट करते हैं), लेकिन क्या यह स्पष्ट रूप से थोड़ा अधिक प्राचीन CPU के लिए तेज़ है, यह एक सवाल है जिसे केवल बेंचमार्किंग के साथ उत्तर दिया जा सकता है (और यह सुनिश्चित भी कर सकता है आपका कंपाइलर अनुकूलन कर रहा है, अन्यथा आप हमेशा जीसीसी संस्करण को "चोरी" कर सकते हैं;))। विशेष रूप से यह मानते हुए कि यह कुशल होने के लिए एक कुशल मुल्श (यानी गुणा निर्देश के उच्च बिट) पर निर्भर करता है। ध्यान दें कि यह कोड आकार स्वतंत्र नहीं है - जादू संख्या में परिवर्तन सटीक होने के लिए (और शायद ऐड/शिफ्ट के कुछ हिस्सों) भी हो सकता है, लेकिन इसे अनुकूलित किया जा सकता है।

Answer 6

जॉन बेंटले के "लेखन कुशल कार्यक्रम" की एक प्रति प्राप्त करें (दुर्भाग्य से प्रिंट से बाहर, सारांश उनके "Programming Pearls" में है)। यह चर्चा करता है कि कैसे (और कब!) कार्यक्रमों के प्रदर्शन की आखिरी बूंद को निचोड़ने के लिए। यहां पर चर्चा की गई सरल परिवर्तनों को वर्तमान कंपेलरों द्वारा निश्चित रूप से एक मामले के रूप में बनाया गया है, वैकल्पिक स्रोतों के असेंबलर कोड की जांच करें और जो कुछ भी स्पष्ट है उसे रखें।