it-swarm-tr.com

Tamsayı esaslı bir güç fonksiyonu kullanmanın en etkili yolu pow (int, int)

Bir tamsayıyı C'deki başka bir tamsayıya yükseltmek için verilen en etkili yol nedir?

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

// 5^5
pow(5,5) == 3125
220
Doug T.

Karelenerek üstelleştirme.

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

    return result;
}

Asimetrik kriptografide büyük sayılar için modüler üstelleştirme yapmak için standart yöntem budur.

362
Elias Yarrkov

Karelemeyle üstelleştirme 'nin en uygun yöntem olmadığını unutmayın. Muhtemelen tüm üs değerleri için çalışan genel bir yöntem olarak yapabileceğiniz en iyisidir, ancak belirli bir üs değeri için daha az çarpma gerektiren daha iyi bir sıra olabilir.

Örneğin, x ^ 15 değerini hesaplamak istiyorsanız, kare alma yöntemiyle üs üs yöntemi size:

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

Bu toplam 6 çarpımdır.

Bunun, "sadece" 5 {çarpım toplama-zincir üstelleştirmesi ile çarpımı kullanılarak yapılabileceği ortaya çıktı.

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

Bu optimal çarpım sırasını bulmak için etkili bir algoritma yoktur. Wikipedia konumundan:

En kısa ekleme zincirini bulma sorunu, dinamik programlama ile çözülemez, çünkü optimum altyapı varsayımını karşılamıyordur. Diğer bir deyişle, gücü her biri en az hesaplanan daha küçük güçlere ayırmak yeterli değildir, çünkü daha küçük güçler için ekleme zincirleri (hesaplamaları paylaşmak için) ilişkili olabilir. Örneğin, a¹⁵ için en kısa ekleme zincirinde, a⁶ için alt problem (a³) ² olarak hesaplanmalıdır çünkü a³ tekrar kullanılır (bunun yerine, üç çarpı gerektiren ).

59
Pramod

2'yi bir güce yükseltmeniz gerekiyorsa. Bunu yapmanın en hızlı yolu, gücün biraz değişmesidir.

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

İşte Java'da yöntem

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;
}
15
user1067920
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);
}
7
Chris Cudmore

Oldukça özel bir durum, 2 ^ (- y'ye x) demeniz gerektiğinde, burada x, elbette negatif ve y, bir int üzerinde kaydırmak için çok büyük. Hala bir şamandıra ile vidalayarak 2 ^ x sabit zaman yapabilirsiniz.

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

Temel tür olarak bir çift kullanarak daha fazla güç elde edebilirsiniz . (Bu gönderiyi kareye ayırmaya yardımcı olduğunuz için çok teşekkürler).

Ayrıca, IEEE yüzmeleri hakkında daha fazla şey öğrenmenin, başka özel üstelleşme örneklerinin kendilerini sunma olasılığı da vardır.

6
Doug T.

Eğer bir şeyin gücüne bağlı olarak 2 için bir tamsayı değerini elde etmek istiyorsanız, shift seçeneğini kullanmak her zaman daha iyidir:

pow(2,5), 1<<5 ile değiştirilebilir

Bu çok daha verimli.

6
aditya

Üstelik üstelik üstelik üstelik üstelik kareyi alarak yorumluyorsunuz.

Bu yaklaşımın avantajı log (n) zamanında çalışmasıdır. Örneğin, x ^ 1048575 (2 ^ 20 - 1) gibi çok büyük bir şey hesaplayacaksanız, naif yaklaşımı kullanarak 1 milyon + değil yalnızca döngüden 20 kez geçmeniz gerekir.

Ayrıca, kod karmaşıklığı açısından, en uygun çarpma sırasını, la Pramod'un önerisini bulmaya çalışmaktan daha basittir.

Düzenle:

Sanırım biri beni taşma potansiyeli için etiketlemeden önce netleştirmeliyim. Bu yaklaşım, bir çeşit bigint kütüphanesine sahip olduğunuzu varsayar.

4
Jason Z

çalışmak için power() işlevi Yalnızca Tamsayılar  

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;

}

Karmaşıklık = O(log(exp))

power() işlevi negatif exp ve float tabanı için çalışır.

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 
    }

} 

Karmaşıklık = O(log(exp))

4
roottraveller

Partiye geç: 

Aşağıda y < 0 ile mümkün olan en iyi şekilde ilgilenen bir çözüm bulunmaktadır. 

  1. Maksimum aralık için intmax_t sonucunu kullanır. intmax_t 'a uymayan cevaplar için bir hüküm yoktur. 
  2. powjii(0, 0) --> 1 olan ortak bir sonuç bu durumda.
  3. Başka bir tanımlanmamış sonuç olan pow(0,negative), INTMAX_MAX değerini döndürür.

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

Bu kod, diğer döngülü çözümlerde ortak olan son base *= base 'dan kaçınmak için bir sonsuza kadar döngü for(;;) kullanır. Bu çarpma 1) gerekli değildir ve 2) UB olan int*int taşması olabilir.

2
chux

Bir uygulama daha (Java'da). En verimli çözüm olmayabilir, ancak yineleme sayısı Üstel çözümünkiyle aynıdır.

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;
    }       
}
1
Vaibhav Fouzdar

negatif üs dikkate alınarak daha genel bir çözüm

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);
}
1
Abhijit Gaikwad

Tüm hesaplanan güçleri ezberleyen ve gerektiğinde bunları kullanan bir algoritma kullandım. Örneğin, x ^ 13 eşittir (x ^ 2) ^ 2 ^ 2 * x ^ 2 ^ 2 * x, burada x ^ 2 ^ 2, bir kez daha hesaplamak yerine tablodan alınır. Gerekli çarpma sayısı Ceil'dir (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);
}
1
rank1

Derleme zamanında üssü (ve bir tamsayıdır) biliyorsanız, döngüyü açmak için şablonları kullanabilirsiniz. Bu daha verimli yapılabilir, ancak temel prensibi burada göstermek istedim:

#include <iostream>

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

Şablon uzmanlığını kullanarak özyinelemeyi sonlandırıyoruz:

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

Üsünün çalışma zamanında bilinmesi gerekiyor,

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

Benim durumum biraz farklı, bir güçten maske oluşturmaya çalışıyorum, ama yine de bulduğum çözümü paylaşacağımı düşündüm.

Açıkçası, sadece 2 güç için çalışıyor.

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

Exp bile olsa, özyinelemeyi kullanırım, 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);
   }
}
0
kyorilys

İmzalı tamsayılarla uygulandığında Tanımsız Davranışa ve işaretsiz tamsayılarla uygulandığında yüksek girdi için yanlış değerlere neden olan Elias'ın cevabına ek olarak,

burada, üstelik işaretlenmiş tamsayı tipleriyle de çalışan ve yanlış değerler vermeyen, üstelik Squaring tarafından değiştirilmiş bir versiyonudur:

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

Bu fonksiyon için dikkat edilmesi gerekenler:

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

Herhangi bir taşma veya sarma gerçekleşecekse, return 0;

int64_t kullandım, ancak herhangi bir genişlik (imzalı veya imzasız) küçük değişikliklerle kullanılabilir. Bununla birlikte, sabit genişlikte olmayan bir tamsayı türü kullanmanız gerekirse, SQRT_INT64_MAX ile (int)sqrt(INT_MAX) (int kullanıldığında) veya benzer bir şey değiştirmeniz gerekecektir, optimize edilmesi gerekir, ancak çirkindir, C sabit ifade Ayrıca, sqrt() sonucunun bir int öğesine atılması, mükemmel bir kare olması durumunda kayan nokta önceliği nedeniyle çok iyi değildir, ancak INT_MAX-veya herhangi bir türün maksimumunun-mükemmel bir kare olduğu hiçbir uygulama bilmediğim için, bununla yaşayabilirsin.

0
Cacahuete Frito