8

का उपयोग कर पूर्णांक विभाजन निष्पादित करें एक कंपाइलर द्वारा उत्पादित x86 असेंबली को देखते हुए, मैंने देखा कि (हस्ताक्षरित) पूर्णांक डिवीजन कभी-कभी पूर्णांक गुणों के रूप में कार्यान्वित किए जाते हैं। इन अनुकूलन प्रपत्रगुणा

value/n => (value * ((0xFFFFFFFF/n) + 1))/0x100000000 

उदाहरण के लिए पालन करने के लिए, 9 से एक प्रभाग प्रदर्शन लगते हैं:

12345678/9 = (12345678 * 0x1C71C71D)/0x100000000 

3 से एक प्रभाग इतने पर 0x55555555 + 1 साथ गुणा का प्रयोग करेंगे, और।

इस तथ्य का पता लगाना कि mul निर्देश edx रजिस्टर में परिणाम के उच्च भाग को संग्रहीत करता है, विभाजन का अंतिम परिणाम जादू मूल्य के साथ एक गुणा का उपयोग करके प्राप्त किया जा सकता है। (हालांकि इस ऑप्टिमाइज़ेशन को कभी-कभी अंत में बिट-वार शिफ्ट के संयोजन के साथ प्रयोग किया जाता है।)

मुझे कुछ अंतर्दृष्टि चाहिए कि यह वास्तव में कैसे काम करता है। यह दृष्टिकोण कब वैध है? हमारे "जादू संख्या" में 1 क्यों जोड़ा जाना चाहिए?

+2

निरंतर जो आप गुणा करते हैं वह पारस्परिक का अनुमान है। यहां यादृच्छिक +/- 1 है और यह सुनिश्चित करना है कि यह हमेशा "गोल" हो। यह साबित करना कि एक विशेष विधि सही है या तो गणितीय रूप से या सभी संख्याओं के ब्रूट-बल परीक्षण द्वारा किया जा सकता है। (32-बिट के लिए, यह पूरी तरह से व्यवहार्य है।) – Mysticial

+0

@ मिस्टिकियल: यह मेरे उत्तर की तरह दिखता है। –

+0

@ScottHunter शायद बाद में जब मैं काम से बाहर हूं। मेरे पास व्यापक उत्तर देने के लिए यहां बहुत सारे टूल नहीं हैं। – Mysticial

उत्तर

10

उस विधि को "इनविरिएंट गुणा द्वारा डिवीजन" कहा जाता है।

जो स्थिरांक आप देख रहे हैं वे वास्तव में पारस्परिक रूप से अनुमानित हैं।

तो बजाय कंप्यूटिंग से:

N/D = Q 

आप इस बजाय कुछ ऐसा कार्य करें:

N * (1/D) = Q 

जहां 1/D एक पारस्परिक कि precomputed जा सकता है।

मूल रूप से, पारस्परिक रूप से अपरिवर्तनीय हैं जब तक कि D एक शक्ति-दो है। तो कुछ गोल-बंद त्रुटि शामिल होगी। +1 जो आप देखते हैं वह राउंड-ऑफ़ त्रुटि के लिए सही है।


सबसे आम उदाहरण 3 से विभाजन है:

N/3 = (N * 0xaaaaaaab) >> 33 

कहाँ 0xaaaaaaab = 2^33/3 + 1

यह दृष्टिकोण अन्य divisors को सामान्यीकृत करेगा।

+1

कैननिकल संदर्भ है: टी। ग्रैनलंड और पीएल मोंटगोमेरी," गुणा का उपयोग करके परिवर्तनीय पूर्णांक द्वारा डिवीजन ", * प्रोग्रामिंग भाषा डिजाइन पर सिग्प्लान '94 सम्मेलन की कार्यवाही में और कार्यान्वयन *, 1 99 4, पीपी 61-72। – njuffa

+1

अतिरिक्त, अधिक हालिया संदर्भ: एन मोलर और टी। ग्रैनलंड, "इनवेरिएंट इंटीग्रेट्स द्वारा बेहतर विभाजन," * कंप्यूटर पर आईईईई लेनदेन *, वॉल्यूम। 60, नहीं। 2, पीपी 165 -175, फरवरी 2011. – njuffa

+0

आपका सामान्यीकरण और सबूत गलत है। विभाजन के लिए 0x55555556 भी 3 द्वारा हस्ताक्षरित रेंज के लिए काम करता है, यानी। 2^31 तक। – Jester

संबंधित मुद्दे