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

Jaki jest najskuteczniejszy sposób podniesienia liczby całkowitej do potęgi innej liczby całkowitej w C?

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

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

Potęgowanie przez kwadrat.

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

    return result;
}

Jest to standardowa metoda wykonywania potęgowania modułowego dla ogromnych liczb w kryptografii asymetrycznej.

Zauważ, że potęgowanie przez kwadrat nie jest najbardziej optymalną metodą. Jest to prawdopodobnie najlepsza metoda, jaką można zrobić jako ogólną metodę, która działa dla wszystkich wartości wykładniczych, ale dla konkretnej wartości wykładniczej może istnieć lepsza sekwencja, która wymaga mniejszej liczby mnożenia.

Na przykład, jeśli chcesz obliczyć x ^ 15, metoda potęgowania przez podniesienie do kwadratu da ci:

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

Jest to w sumie 6 multiplikacji.

Okazuje się, że można tego dokonać za pomocą „tylko” 5 krotności poprzez potęgowanie łańcucha dodatków .

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 wydajnych algorytmów pozwalających znaleźć tę optymalną sekwencję mnożenia. Z Wikipedii :

Problem znalezienia najkrótszego łańcucha dodawania nie może zostać rozwiązany przez programowanie dynamiczne, ponieważ nie spełnia założenia optymalnej podbudowy. Oznacza to, że nie wystarczy rozłożyć mocy na mniejsze moce, z których każda jest obliczana minimalnie, ponieważ łańcuchy dodatków dla mniejszych mocy mogą być powiązane (w celu współdzielenia obliczeń). Na przykład w najkrótszym łańcuchu dodawania dla powyższej a⁵, podproblem dla a⁶ musi zostać obliczony jako (a³) ², ponieważ a³ jest ponownie użyte (w przeciwieństwie do, powiedzmy, a⁶ = a² (a²) ², co również wymaga trzech mnożeń ).

Jeśli musisz podnieść 2 do potęgi. Najszybszym sposobem na to jest przesunięcie bitowe według siły.

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

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

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żna zastąpić 1<<5

Jest to o wiele bardziej wydajne.

power()funkcja działa 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 ujemnego 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))

Niezwykle wyspecjalizowanym przypadkiem jest, gdy trzeba powiedzieć 2 ^ (- x do y), gdzie x jest oczywiście ujemne, a y jest zbyt duże, aby wykonać przesunięcie int. Nadal możesz 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 podstawowego. (Wielkie dzięki dla komentujących za pomoc w poprawieniu tego posta).

Istnieje również możliwość, że jeśli dowiesz się więcej o pływakach IEEE , mogą pojawić się inne specjalne przypadki potęgowania.

Podobnie jak kontynuacja komentarzy na temat wydajności potęgowania przez kwadrat.

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

Również pod względem złożoności kodu jest prostsze niż próba znalezienia najbardziej optymalnej sekwencji multiplikacji, co sugeruje la Pramod.

Edytować:

Chyba powinienem wyjaśnić, zanim ktoś oznaczy mnie tagiem pod kątem możliwości przepełnienia. Podejście to zakłada, że ​​masz jakąś ogromną bibliotekę.

Późno na imprezę:

Poniżej znajduje się rozwiązanie, które radzi sobie y < 0najlepiej, jak to możliwe.

1. Wykorzystuje wynik intmax_tdla maksymalnego zasięgu. Nie ma przepisów dotyczących odpowiedzi, które nie pasują intmax_t.
2. powjii(0, 0) --> 1co jest częstym wynikiem w tym przypadku.

3. pow(0,negative), zwraca kolejny niezdefiniowany wynik 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 for(;;)na zawsze, aby uniknąć ostatecznego base *= basewspólnego w innych zapętlonych rozwiązaniach. To zwielokrotnienie jest 1) niepotrzebne i 2) może być int*intprzepełnieniem, które jest UB.

bardziej ogólne rozwiązanie z uwzględnieniem ujemnego exponenetu

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 być najskuteczniejszym rozwiązaniem, ale liczba iteracji jest taka sama 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);
   }
}

Oprócz odpowiedzi Eliasa, która powoduje niezdefiniowane zachowanie po zaimplementowaniu za pomocą liczb całkowitych ze znakiem, oraz niepoprawne wartości wysokich danych wejściowych po zaimplementowaniu za pomocą liczb całkowitych bez znaku,

tutaj jest zmodyfikowana wersja potęgowania przez kwadrat, która działa również z podpisanymi typami liczb całkowitych i nie podaje niepoprawnych 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;
}

Uwagi dotyczące tej funkcji:

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

Jeśli nastąpi przelew lub owijanie, return 0;

Użyłem int64_t, ale dowolnej szerokości (podpisanej lub niepodpisanej) można używać z niewielką modyfikacją. Jednakże, jeśli chcesz używać bez stałej szerokości typu INTEGER, będzie trzeba zmienić SQRT_INT64_MAXprzez (int)sqrt(INT_MAX)(w przypadku używania int) lub coś podobnego, który powinien zostać zoptymalizowany, ale jest brzydsze, a nie wyrazem C stała. Również rzutowanie wyniku sqrt()na „ intnie” jest bardzo dobre z powodu precyzji zmiennoprzecinkowej w przypadku idealnego kwadratu, ale ponieważ nie znam żadnej implementacji, w której INT_MAX- lub maksimum dowolnego typu - jest idealnym kwadratem, możesz żyć z tym.

Wdrożyłem algorytm, który zapamiętuje wszystkie obliczone moce, a następnie wykorzystuje je w razie potrzeby. Na przykład x ^ 13 jest równe (x ^ 2) ^ 2 ^ 2 * x ^ 2 ^ 2 * x gdzie x ^ 2 ^ 2 wziął z tabeli zamiast go ponownie obliczać. Jest to w zasadzie implementacja odpowiedzi @Pramod (ale w języku 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ę rozwiązaniem, które znalazłem.

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) w czasie kompilacji, możesz użyć szablonów do rozwinięcia pętli. Można to uczynić bardziej wydajnym, ale chciałem tutaj przedstawić podstawową zasadę:

#include <iostream>

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

Kończymy rekurencję za pomocą specjalizacji szablonu:

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