Najbardziej efektywny sposób implementacji funkcji mocy opartej na liczbach całkowitych pow (int, int)

Zauważ, że wykładnictwo przez kwadrat nie jest najbardziej optymalną metodą. Jest to prawdopodobnie najlepsze, co możesz zrobić jako ogólna metoda, która działa dla wszystkich wartości wykładnika, ale dla określonej wartości wykładnika może być lepsza sekwencja, która wymaga mniej mnożenia.

Na przykład, jeśli chcesz obliczyć x^15, metoda wykładnicza przez kwadrat da ci:

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

Jest to łącznie 6 mnożeń.

Okazuje się, że można to zrobić za pomocą "tylko" 5 mnożenie przez dodawanie-wykładnik Łańcuchowy .

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

Nie ma efektywnych algorytmów, aby znaleźć ten optymalny ciąg mnożenia. Z Wikipedii :

Problem znalezienia najkrótszego łańcucha dodawania nie może być rozwiązany przez programowanie dynamiczne, ponieważ nie spełnia on założeń optymalnej podbudowy. Oznacza to, że nie wystarczy rozkładać mocy na mniejsze moce, z których każda jest obliczana minimalnie, ponieważ łańcuchy dodawania dla mniejszych potęg mogą być powiązane (do współdzielenia obliczeń). Na przykład, w najkrótszym łańcuchu dodawania dla a1⁵ powyżej, podproblem dla a⁶ musi być obliczony jako (a3)2, ponieważ a3 jest ponownie używany (w przeciwieństwie do, powiedzmy, a⁶ = A2(a2)2, który również wymaga trzech mnożenia).

Jeśli chcesz podnieść 2 do potęgi. Najszybszy sposób, aby to zrobić, to bit przesunięcie przez moc.

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

Oto metoda w Javie

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

power() funkcja do pracy tylko dla liczb całkowitych

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;

}

Złożoność = O (log (exp))

power() funkcja do pracy dla negative EXP i float base .

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 
    }

} 

Złożoność = O (log (exp))

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

Bardzo wyspecjalizowanym przypadkiem jest, gdy trzeba powiedzieć 2^(- x do Y), gdzie x, jest oczywiście ujemne, a y jest zbyt duże, aby zrobić przesunięcie na int. Możesz jeszcze zrobić 2^x w stałym czasie, wkręcając pływak.

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

Możesz uzyskać więcej mocy 2, używając podwójnego jako typu bazowego. (Wielkie dzięki dla komentatorów za pomoc w uporządkowaniu tego postu).

Istnieje również możliwość, że dowiedzenie się więcej o IEEE floats , innych szczególnych przypadkach wykładnictwa mogą się zaprezentować.

Jeśli chcesz uzyskać wartość liczby całkowitej dla 2 podniesioną do potęgi czegoś, zawsze lepiej jest użyć opcji shift:

pow(2,5) może być zastąpiony przez 1<<5

Jako kontynuacja komentarzy na temat wydajności wykładniczej przez kwadraturę.

Zaletą tego podejścia jest to, że działa w czasie log(n). Na przykład, jeśli zamierzałeś obliczyć coś wielkiego, na przykład x^1048575 (2^20 - 1), Musisz tylko przejść przez pętlę 20 razy, a nie 1 milion+ używając naiwnego podejścia.

Ponadto, jeśli chodzi o złożoność kodu, jest to prostsze niż próba znalezienia najbardziej optymalnego ciągu mnożenia, a la Pramod ' s sugestia.

Edit:

Chyba powinienem wyjaśnić, zanim ktoś oznaczy mnie potencjałem przepełnienia. Takie podejście zakłada, że masz jakąś bibliotekę hugeint.

Spóźnienie na imprezę:

Poniżej znajduje się rozwiązanie, które również radzi sobie z y < 0 najlepiej jak potrafi.

1. używa wyniku intmax_t dla maksymalnego zasięgu. Nie ma przepisu na odpowiedzi, które nie pasują do intmax_t.
2. powjii(0, 0) --> 1 który jest wspólnym wynikiem w tym przypadku.

3. pow(0,negative), kolejny niezdefiniowany wynik, zwraca 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;
   }
   

Ten kod używa pętli forever for(;;), aby uniknąć ostatecznej base *= base wspólnej w innych pętlach rozwiązania. To mnożenie jest 1) niepotrzebne i 2) może być int*int przepełnieniem, które jest UB.

Bardziej ogólne rozwiązanie uwzględniające wykładnik ujemny

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

Jeszcze jedna implementacja (w Javie). Może nie jest najbardziej wydajnym rozwiązaniem, ale # iteracji jest taki sam jak w przypadku rozwiązania wykładniczego.

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

Używam rekurencyjnego, jeśli exp jest parzysty, 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);
   }
}

W przeciwieństwie do tego, że nie jest on w pełni automatyczny, nie jest on w pełni automatyczny i nie jest w pełni automatyczny, nie jest w pełni automatyczny i nie jest w pełni automatyczny.]}

Tutaj jest zmodyfikowana wersja wykładnika przez kwadraturę, która działa również ze znakowanymi typami liczb całkowitych i nie podaje nieprawidłowych wartości:

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

Rozważania dla tej funkcji:

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

Jeśli dojdzie do przepełnienia lub owinięcia, return 0;

Użyłem int64_t, ale Dowolna szerokość (podpisana lub niepodpisana) może być używana z niewielką modyfikacją. Jednakże, jeśli chcesz użyć typu integer o nieokreślonej szerokości, musisz zmienić SQRT_INT64_MAX na (int)sqrt(INT_MAX) (W przypadku użycia int) lub coś podobnego, które powinno być zoptymalizowane, ale jest brzydsze, a nie stałe wyrażenie C. Również rzutowanie wyniku sqrt() na int nie jest zbyt dobre ze względu na precyzję zmiennoprzecinkową w przypadku doskonałego kwadratu, ale ponieważ nie znam żadnej implementacji gdzie INT_MAX - lub maksimum każdego typu-to idealny kwadrat, z którym można żyć.

Zaimplementowałem algorytm, który zapamiętuje wszystkie moce obliczeniowe, a następnie używa ich w razie potrzeby. Na przykład x^13 jest równe (x^2)^2^2 * x^2^2 * x, gdzie x^2^2 zostało wzięte z tabeli zamiast ponownie ją obliczyć. Jest to w zasadzie implementacja @ Pramod answer (ale w C#). Wymagana liczba mnożenia to Ceil (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);
}

Mój przypadek jest trochę inny, próbuję stworzyć maskę z mocy, ale pomyślałem, że i tak podzielę się znalezionym rozwiązaniem.

Oczywiście działa tylko dla potęg 2.

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

Jeśli znasz wykładnik (i jest to liczba całkowita) podczas kompilacji, możesz użyć szablonów do rozwinięcia pętli. Można to uczynić bardziej efektywnym, ale chciałem zademonstrować podstawową zasadę tutaj:

#include <iostream>

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

Przerywamy rekurencję za pomocą szablonu specjalizacji:

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

Wykładnik musi być znany w czasie wykonywania,

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