c - हरण - सबसे छोटा पूर्णांक




एक पूर्णांक आधारित पावर फ़ंक्शन पावर(int, int) को लागू करने का सबसे प्रभावी तरीका (12)

सी में एक और पूर्णांक की शक्ति को पूर्णांक बढ़ाने के लिए सबसे प्रभावी तरीका क्या है?

// 2^3
pow(2,3) == 8

// 5^5
pow(5,5) == 3125

2 शक्ति के लिए उठाए गए विशेष मामले को अनदेखा करते हुए, सबसे प्रभावी तरीका सरल पुनरावृत्ति होने जा रहा है।

int pow(int base, int pow) {
  int res = 1;
  for(int i=pow; i<pow; i++)
    res *= base;

  return res;
}

संपादित करें: जैसा कि बताया गया है कि यह सबसे प्रभावी तरीका नहीं है ... जब तक आप दक्षता को सीपीयू चक्र के रूप में परिभाषित करते हैं जो मुझे लगता है कि काफी उचित है।


एक और कार्यान्वयन (जावा में)। सबसे कुशल समाधान नहीं हो सकता है लेकिन पुनरावृत्तियों का # घातीय समाधान के समान है।

public static long pow(long base, long exp){        
    if(exp ==0){
        return 1;
    }
    if(exp ==1){
        return base;
    }

    if(exp % 2 == 0){
        long half = pow(base, exp/2);
        return half * half;
    }else{
        long half = pow(base, (exp -1)/2);
        return base * half * half;
    }       
}

जावा में विधि यहां दी गई है

private int ipow(int base, int exp)
{
    int result = 1;
    while (exp != 0)
    {
        if ((exp & 1) == 1)
            result *= base;
        exp >>= 1;
        base *= base;
    }

    return result;
}

ध्यान दें कि स्क्वायरिंग द्वारा एक्सपोनेंटिएशन सबसे इष्टतम तरीका नहीं है। यह शायद सबसे अच्छा है जो आप एक सामान्य विधि के रूप में कर सकते हैं जो सभी घातीय मूल्यों के लिए काम करता है, लेकिन एक विशिष्ट एक्सपोनेंट वैल्यू के लिए एक बेहतर अनुक्रम हो सकता है जिसके लिए कम गुणा की आवश्यकता होती है।

उदाहरण के लिए, यदि आप x ^ 15 की गणना करना चाहते हैं, तो स्क्वायरिंग द्वारा एक्सपोनेंटिएशन की विधि आपको प्रदान करेगी:

x^15 = (x^7)*(x^7)*x 
x^7 = (x^3)*(x^3)*x 
x^3 = x*x*x

यह कुल 6 गुणा है।

यह पता चला है कि यह अतिरिक्त-श्रृंखला एक्सपोनेंटिएशन के माध्यम से "बस" 5 गुणाओं का उपयोग करके किया जा सकता है।

n*n = n^2
n^2*n = n^3
n^3*n^3 = n^6
n^6*n^6 = n^12
n^12*n^3 = n^15

गुणाओं के इस इष्टतम अनुक्रम को खोजने के लिए कोई कुशल एल्गोरिदम नहीं हैं। विकिपीडिया से :

सबसे छोटी अतिरिक्त श्रृंखला को खोजने की समस्या को गतिशील प्रोग्रामिंग द्वारा हल नहीं किया जा सकता है, क्योंकि यह इष्टतम संरचना की धारणा को पूरा नहीं करता है। यही है, शक्ति को छोटी शक्तियों में विघटित करने के लिए पर्याप्त नहीं है, जिनमें से प्रत्येक को न्यूनतम रूप से गणना की जाती है, क्योंकि छोटी शक्तियों के लिए अतिरिक्त श्रृंखलाएं संबंधित हो सकती हैं (गणना को साझा करने के लिए)। उदाहरण के लिए, उपरोक्त ए for के लिए सबसे छोटी अतिरिक्त श्रृंखला में, ए⁶ के लिए उपप्रोबल को ए (ए) ² के रूप में गणना की जानी चाहिए क्योंकि ए³ का पुन: उपयोग किया जाता है (जैसा कि कहते हैं, a⁶ = a² (a²) ², जिसके लिए तीन गुणा भी आवश्यक है )।


पार्टी के लिए देर हो चुकी है:

नीचे एक समाधान है जो y < 0 साथ सबसे अच्छा व्यवहार करता है।

  1. यह अधिकतम सीमा के लिए intmax_t परिणाम का उपयोग करता है। ऐसे उत्तरों के लिए कोई प्रावधान नहीं है जो intmax_t में फिट न intmax_t
  2. powjii(0, 0) --> 1 जो इस मामले के लिए एक आम परिणाम है
  3. pow(0,negative) , एक और अपरिभाषित परिणाम, INTMAX_MAX देता है

    intmax_t powjii(int x, int y) {
      if (y < 0) {
        switch (x) {
          case 0:
            return INTMAX_MAX;
          case 1:
            return 1;
          case -1:
            return y % 2 ? -1 : 1;
        }
        return 0;
      }
      intmax_t z = 1;
      intmax_t base = x;
      for (;;) {
        if (y % 2) {
          z *= base;
        }
        y /= 2;
        if (y == 0) {
          break; 
        }
        base *= base;
      }
      return z;
    }
    

यह कोड अन्य लूप समाधानों में अंतिम base *= base सामान्य से बचने के for(;;) हमेशा के लिए लूप का उपयोग करता है। वह गुणा 1 है) आवश्यक नहीं है और 2) int*int अतिप्रवाह हो सकता है जो यूबी है।


मेरा मामला थोड़ा अलग है, मैं एक शक्ति से मास्क बनाने की कोशिश कर रहा हूं, लेकिन मैंने सोचा कि मैं वैसे भी मिला जो समाधान मिला हूं।

जाहिर है, यह केवल 2 की शक्तियों के लिए काम करता है।

Mask1 = 1 << (Exponent - 1);
Mask2 = Mask1 - 1;
return Mask1 + Mask2;

मैंने एल्गोरिदम लागू किया है जो सभी गणना शक्तियों को याद करता है और फिर आवश्यकता होने पर उनका उपयोग करता है। तो उदाहरण के लिए x ^ 13 बराबर (x ^ 2) ^ 2 ^ 2 * x ^ 2 ^ 2 * x है जहां x ^ 2 ^ 2 इसे एक बार फिर से कंप्यूटिंग करने के बजाय तालिका से लिया गया है। आवश्यक गुणा की संख्या सील (लॉग एन) है

public static int Power(int base, int exp)
{
    int tab[] = new int[exp + 1];
    tab[0] = 1;
    tab[1] = base;
    return Power(base, exp, tab);
}

public static int Power(int base, int exp, int tab[])
    {
         if(exp == 0) return 1;
         if(exp == 1) return base;
         int i = 1;
         while(i < exp/2)
         {  
            if(tab[2 * i] <= 0)
                tab[2 * i] = tab[i] * tab[i];
            i = i << 1;
          }
    if(exp <=  i)
        return tab[i];
     else return tab[i] * Power(base, exp - i, tab);
}

यदि आप किसी चीज की शक्ति में उठाए गए 2 के लिए पूर्णांक का मान प्राप्त करना चाहते हैं तो शिफ्ट विकल्प का उपयोग करना हमेशा बेहतर होता है:

pow(2,5) 1<<5 द्वारा प्रतिस्थापित किया जा सकता है

यह बहुत अधिक कुशल है।


यदि आपको 2 शक्तियों को बढ़ाने की आवश्यकता है। ऐसा करने का सबसे तेज़ तरीका शक्ति द्वारा थोड़ा बदलाव करना है।

2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)

स्क्वायरिंग द्वारा एक्सपोनिएशन की दक्षता पर टिप्पणियों का पालन करने के लिए।

उस दृष्टिकोण का लाभ यह है कि यह लॉग (एन) समय में चलता है। उदाहरण के लिए, यदि आप x ^ 1048575 (2 ^ 20 - 1) जैसे कुछ विशाल गणना करने जा रहे थे, तो आपको मूर्खतापूर्ण दृष्टिकोण का उपयोग करके केवल 20 बार लूप के माध्यम से जाना होगा, 1 मिलियन + नहीं।

इसके अलावा, कोड जटिलता के मामले में, यह ला प्रमोद के सुझाव, गुणों के सबसे इष्टतम अनुक्रम को खोजने का प्रयास करने से आसान है।

संपादित करें:

मुझे लगता है कि किसी ने मुझे ओवरफ्लो की संभावना के लिए टैग करने से पहले स्पष्टीकरण देना चाहिए। यह दृष्टिकोण मानता है कि आपके पास कुछ प्रकार की विशाल पुस्तकालय है।


केवल इंटीजर के लिए काम करने के लिए power() फ़ंक्शन

int power(int base, unsigned int exp){

    if (exp == 0)
        return 1;
    int temp = power(base, exp/2);
    if (exp%2 == 0)
        return temp*temp;
    else
        return base*temp*temp;

}

जटिलता = ओ (लॉग (एक्सपी))

नकारात्मक एक्सप और फ्लोट बेस के लिए काम करने के लिए power() फ़ंक्शन।

float power(float base, int exp) {

    if( exp == 0)
       return 1;
    float temp = power(base, exp/2);       
    if (exp%2 == 0)
        return temp*temp;
    else {
        if(exp > 0)
            return base*temp*temp;
        else
            return (temp*temp)/base; //negative exponent computation 
    }

} 

जटिलता = ओ (लॉग (एक्सपी))


int pow( int base, int exponent)

{   // Does not work for negative exponents. (But that would be leaving the range of int) 
    if (exponent == 0) return 1;  // base case;
    int temp = pow(base, exponent/2);
    if (exponent % 2 == 0)
        return temp * temp; 
    else
        return (base * temp * temp);
}






exponentiation