मैं 2^एन + 1 द्वारा विभाजन को कैसे कम कर सकता हूं?

Question

मुझे अपने कोड के गर्म पथ में कुछ पूर्णांक डिवीजन करने की आवश्यकता है। मैंने पहले ही प्रोफाइलिंग और चक्र गिनती के माध्यम से निर्धारित किया है कि पूर्णांक डिवीजनों की लागत मुझे है। मुझे आशा है कि कुछ ऐसा है जो मैं कुछ सस्ता में विभाजन को कम करने के लिए कर सकता हूं।

इस पथ में, मैं 2^एन + 1 से विभाजित हूं, जहां एन परिवर्तनीय है। अनिवार्य रूप से मैं विभाजन ऑपरेटर निकालने के लिए इस समारोह को अनुकूलित करना चाहते:

unsigned long compute(unsigned long a, unsigned int n) 
{ 
    return a/((1 << n) + 1); 
} 

अगर मैं द्वारा 2^n विभाजित किया गया है, मैं सिर्फ एक पारी-सही n द्वारा साथ div की जगह लेंगे। अगर मैं स्थिरता से विभाजित हो रहा था, तो मैं संकलक शक्ति को उस विशिष्ट विभाजन को कम करने देता हूं, संभवतः इसे एक गुणा और कुछ बदलावों में बदल देता हूं।

क्या कोई समान अनुकूलन है जो 2^एन + 1 पर लागू होता है?

संपादित करें: यहां एक मनमाना 64-बिट पूर्णांक हो सकता है। n 10 के बीच केवल कुछ मान लेता है और कहता है, 25. मैं निश्चित रूप से प्रत्येक एन के लिए कुछ मानों का प्रीकंप्यूट कर सकता हूं, लेकिन इसके लिए नहीं।

Answer 1

के बाद से आप केवल एक int बहुत सारे स्थान बदल सकते हैं, तो आप उन सभी मामलों कई डिवीजनों में से एक का एक विकल्प में एक निरंतर द्वारा रख सकते हैं:

unsigned long compute(unsigned long a, unsigned int n) 
{ 
    // assuming a 32-bit architecture (making this work for 64-bits 
    // is left as an exercise for the reader): 
    switch (n) { 
     case 0: return a/((1 << 0) + 1); 
     case 1: return a/((1 << 1) + 1); 
     case 2: return a/((1 << 2) + 1); 

      // cases 3 through 30... 

     case 31: return a/((1 << 31) + 1); 
    } 
} 

तो अब प्रत्येक प्रभाग एक स्थिर, के द्वारा होता है जो कंपाइलर्स आमतौर पर गुणा/शिफ्ट/जोड़ निर्देशों की एक श्रृंखला को कम कर देंगे (जैसा कि प्रश्न का उल्लेख किया गया है)। Deatils के लिए Does a c/c++ compiler optimize constant divisions by power-of-two value into shifts? देखें।

Answer 2

आप एक जादू संख्या और एक शिफ्ट के साथ गुणा (मॉड्यूलो शब्दकोष) द्वारा निरंतर एक पूर्णांक विभाजन को प्रतिस्थापित कर सकते हैं।

ज्ञात स्थिरांक के लिए जादू संख्याओं की पूर्व गणना की जा सकती है।

चूंकि एन कई मान नहीं ले सकता है उदा। 0..31 यह सभी एन के लिए इन जादू संख्याओं की पूर्व-गणना करने के लिए "आसान" है और इसे 32 तत्वों वाले तालिका में संग्रहीत करना है।

Javascript Page for calculating the magic numbers

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

जादू संख्याओं की गणना के लिए कोड के साथ विस्तृत विवरण एक साथ फंड हो सकता है हेनरी एस वॉरेन, जूनियर द्वारा 0 "हैकर्स डिलाइट" बुक करें (अत्यधिक अनुशंसित पुस्तक होना चाहिए!) पीपी 180 एफ। प्रासंगिक अध्याय लिए Google पुस्तकें पर

लिंक:

Chapter 10-9 Unsigned Division by Divisors >= 1