الطريقة الأكثر فعالية لتنفيذ عدد صحيح على أساس السلطة الدالة pow(int, int)

Question

ما هي الطريقة الأكثر فعالية نظرا لزيادة عدد صحيح إلى قوة أخرى صحيح في C ؟

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

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

Answer 1

الأسي التوفيق.

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

    return result;
}

هذا هو المعيار طريقة لعمل وحدات الأسي على أعداد هائلة في التشفير غير المتناظر.

Answer 2

علما بأن الأسي التوفيق ليست أفضل طريقة.وربما هو أفضل ما يمكن القيام به كوسيلة العام أن يعمل لجميع الأس القيم ، ولكن لمدة محددة الأس القيمة قد يكون هناك تسلسل أفضل من أن يحتاج إلى عدد أقل من الضرب.

فعلى سبيل المثال ، إذا كنت ترغب في حساب 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

لا توجد خوارزميات فعالة لإيجاد الأمثل هذا التسلسل من الضرب.من ويكيبيديا:

مشكلة إيجاد أقصر بالإضافة إلى سلسلة لا يمكن حلها عن طريق البرمجة الديناميكية, لأنه لا يرضي افتراض الأمثل التحتية.أي أنه لا يكفي أن تتحلل السلطة إلى أصغر صلاحيات كل من هو محسوب الحد الأدنى ، منذ ذلك سلاسل أصغر القوى قد تكون ذات صلة (أن حصة العمليات الحسابية).على سبيل المثال ، في أقصر بالإضافة إلى سلسلة a1⁵ أعلاه ، subproblem على a⁶ يجب أن يحسب (a3)2 منذ a3 إعادة استخدامها (بدلا من, قول, a⁶ = a2(a2)2 ، الأمر الذي يتطلب أيضا ثلاثة يضاعف).

Answer 3

إذا كنت بحاجة إلى رفع 2 إلى السلطة.أسرع طريقة للقيام بذلك هو الشيء تحول من قبل السلطة.

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

Answer 4

هنا هو طريقة في جافا

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

Answer 5

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

Answer 6

إذا كنت ترغب في الحصول على قيمة عدد صحيح 2 مرفوعة إلى القوة من شيء فمن الأفضل دائما أن استخدام التحول الخيار:

pow(2,5) يمكن الاستعاضة عن 1<<5

هذا هو أكثر كفاءة بكثير.

Answer 7

غاية المتخصصة القضية ، عندما كنت في حاجة يقول 2^(x-y) حيث x هو بالطبع هو سلبي و y كبيرة جدا للقيام التحول على الباحث.يمكنك لا تزال تفعل 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 باستخدام مزدوج كقاعدة نوع.(بفضل الكثير من المعلقين للمساعدة في ساحة هذا المنصب بعيدا).

هناك أيضا إمكانية أن تعلم المزيد عن IEEE يطفو, وغيرها حالات خاصة من الأسي قد تقدم نفسها.

Answer 8

فقط متابعة التعليقات على كفاءة الأسي التوفيق.

وميزة هذا النهج هو أنه يعمل في log(n) مرة.على سبيل المثال, إذا كنت تريد حساب شيء ضخم مثل x^1048575 (2^20 - 1), لديك فقط للذهاب من خلال حلقة 20 مرة ، 1 مليون+ باستخدام النهج السذاجة.

أيضا ، من حيث التعقيد رمز ، بل هو أبسط مما تحاول العثور على معظم الأمثل سلسلة من الضرب ، a la برامود اقتراح.

تحرير:

أعتقد أنني يجب أن توضح قبل شخص العلامات لي إمكانية تجاوز.هذا النهج يفترض أن لديك نوعا من hugeint المكتبة.

Answer 9

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;

}

تعقيد = O(log(exp))

power() وظيفة للعمل السلبية exp و تطفو قاعدة.

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 
    }

} 

تعقيد = O(log(exp))

Answer 10

في وقت متأخر إلى الحزب:

أدناه هو الحل الذي يتناول أيضا y < 0 بأفضل ما يمكن.

1. ويستخدم نتيجة 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;
   }
   

يستخدم هذا الرمز حلقة إلى الأبد for(;;) لتجنب النهائي base *= base شيوعا في آخر يحلق الحلول.أن الضرب هو 1) لا حاجة و 2) يمكن أن يكون int*int تجاوز وهو UB.

Answer 11

المزيد من generic الحل النظر السلبية exponenet

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

Answer 12

أحد أكثر التنفيذ (Java).قد لا يكون الحل الأكثر فعالية ولكن # من التكرار هو نفسه كما ان من الأسي الحل.

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

Answer 13

يمكنني استخدام العودية ، إذا كان exp هو حتى 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);
   }
}

Answer 14

بالإضافة إلى الإجابة عن الياس الذي يسبب Undefined السلوك عند تنفيذ وقعت صحيحة و غير صحيحة قيم مدخلات عالية عند تنفيذه مع غير صحيحة ،

هنا هو نسخة معدلة من الأسي التوفيق الذي يعمل أيضا مع صحيح وقعت أنواع, و لا يعطي قيم غير صحيحة:

#include <stdint.h>

#define SQRT_INT64_MAX (INT64_C(0xB504F333))

int64_t alx_pow_s64 (int64_t base, uint8_t exp)
{
    int_fast64_t    base_;
    int_fast64_t    result;

    base_   = base;

    if (base_ == 1)
        return  1;
    if (!exp)
        return  1;
    if (!base_)
        return  0;

    result  = 1;
    if (exp & 1)
        result *= base_;
    exp >>= 1;
    while (exp) {
        if (base_ > SQRT_INT64_MAX)
            return  0;
        base_ *= base_;
        if (exp & 1)
            result *= base_;
        exp >>= 1;
    }

    return  result;
}

اعتبارات لهذه الوظيفة:

(1 ** N) == 1
(N ** 0) == 1
(0 ** 0) == 1
(0 ** N) == 0

إن أي تجاوز أو التفاف سوف تأخذ مكان ، return 0;

اعتدت int64_t, لكن أي عرض (موقعة أو غير موقعة) يمكن استخدامها مع القليل من التعديل.ومع ذلك ، إذا كنت بحاجة إلى استخدام غير ثابت-عرض نوع عدد صحيح, سوف تحتاج إلى تغيير SQRT_INT64_MAX قبل (int)sqrt(INT_MAX) (في حالة استخدام int) أو شيئا من هذا القبيل ، والتي ينبغي أن يكون الأمثل ، بل هو أقبح ، وليس ج ثابت التعبير.أيضا الصب نتيجة sqrt() إلى int ليست جيدة جدا بسبب النقطة العائمة الدقه صفه جديره في حالة من الكمال مربع ، ولكن لا أعلم من أي مكان INT_MAX -أو الحد من أي نوع - هو الكمال مربع ، هل يمكن أن يعيش مع هذا.

Answer 15

لقد نفذت خوارزمية أن يحفظ جميع القوى المحسوبة ثم يستخدمها عند الحاجة.لذلك على سبيل المثال x^13 يساوي (x^2)^2^2 * x^2^2 * x حيث x^2^2 مأخوذة من الجدول بدلا من الحوسبة ذلك مرة أخرى.هذا هو الأساس في تنفيذ @برامود الجواب (ولكن في C#).عدد الضرب المطلوب هو سقف(Log n)

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

Answer 16

حالتي هي مختلفة قليلا ، أحاول إنشاء قناع من القوة, ولكن اعتقدت حصة الحل وجدت على أي حال.

ومن الواضح أنها لا تعمل إلا على صلاحيات 2.

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

Answer 17

في حال كنت تعرف الأس (وهو صحيح) في وقت التحويل البرمجي ، يمكنك استخدام قوالب انبسط الحلقة.هذا يمكن أن تكون أكثر كفاءة ، ولكن أردت أن تثبت المبدأ الأساسي هنا:

#include <iostream>

template<unsigned long N>
unsigned long inline exp_unroll(unsigned base) {
    return base * exp_unroll<N-1>(base);
}

ونحن إنهاء العودية باستخدام قالب التخصص:

template<>
unsigned long inline exp_unroll<1>(unsigned base) {
    return base;
}

الأس يحتاج إلى أن يعرف في وقت التشغيل ،

int main(int argc, char * argv[]) {
    std::cout << argv[1] <<"**5= " << exp_unroll<5>(atoi(argv[1])) << ;std::endl;
}

Answer 18

وتجاهل حالة خاصة من 2 إلى السلطة, الطريقة الأكثر فعالية سوف تكون بسيطة التكرار.

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

  return res;
}

تحرير:كما أوضحت هذه ليست الطريقة الأكثر فعالية...طالما يمكنك تحديد الكفاءة دورات وحدة المعالجة المركزية التي أعتقد هو عادلة بما فيه الكفاية.