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




सबसे छोटा पूर्णांक (14)

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

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

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

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

उदाहरण के लिए, यदि आप 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²) ², जिसके लिए तीन गुणा भी आवश्यक है )।


केवल इंटीजर के लिए काम करने के लिए 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 
    }

} 

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


मैंने एल्गोरिदम लागू किया है जो सभी गणना शक्तियों को याद करता है और फिर आवश्यकता होने पर उनका उपयोग करता है। तो उदाहरण के लिए 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);
}

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);
}

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

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

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


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

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;
}

एक बेहद विशिष्ट मामला है, जब आपको 2 ^ (- x से y) की आवश्यकता होती है, जहां x, निश्चित रूप से नकारात्मक है और y int पर स्थानांतरण करने के लिए बहुत बड़ा है। आप अभी भी एक फ्लोट के साथ पेंच करके स्थिर समय में 2 ^ x कर सकते हैं।

struct IeeeFloat
{

    unsigned int base : 23;
    unsigned int exponent : 8;
    unsigned int signBit : 1;
};


union IeeeFloatUnion
{
    IeeeFloat brokenOut;
    float f;
};

inline float twoToThe(char exponent)
{
    // notice how the range checking is already done on the exponent var 
    static IeeeFloatUnion u;
    u.f = 2.0;
    // Change the exponent part of the float
    u.brokenOut.exponent += (exponent - 1);
    return (u.f);
}

आप बेस प्रकार के रूप में डबल का उपयोग करके 2 की अधिक शक्तियां प्राप्त कर सकते हैं। (इस पोस्ट को स्क्वायर करने में मदद के लिए टिप्पणी करने वालों के लिए बहुत बहुत धन्यवाद)।

आईईईई फ्लोट्स के बारे में अधिक सीखने की संभावना भी है , एक्सपोनेंटिएशन के अन्य विशेष मामले खुद को पेश कर सकते हैं।


स्क्वायरिंग द्वारा एक्सपोनेंटिएशन।

int ipow(int base, int exp)
{
    int result = 1;
    for (;;)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        if (!exp)
            break;
        base *= base;
    }

    return result;
}

असममित क्रिप्टोग्राफी में बड़ी संख्या के लिए मॉड्यूलर एक्सपोनेंटिएशन करने के लिए यह मानक तरीका है।


मैं रिकर्सिव का उपयोग करता हूं, अगर एक्सप भी है, 5 ^ 10 = 25 ^ 5।

int pow(float base,float exp){
   if (exp==0)return 1;
   else if(exp>0&&exp%2==0){
      return pow(base*base,exp/2);
   }else if (exp>0&&exp%2!=0){
      return base*pow(base,exp-1);
   }
}

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

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

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

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

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

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

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


नकारात्मक एक्सपोननेट पर विचार करने के लिए अधिक सामान्य समाधान

private static int pow(int base, int exponent) {

    int result = 1;
    if (exponent == 0)
        return result; // base case;

    if (exponent < 0)
        return 1 / pow(base, -exponent);
    int temp = pow(base, exponent / 2);
    if (exponent % 2 == 0)
        return temp * temp;
    else
        return (base * temp * temp);
}

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

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

  return res;
}

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





exponentiation