Il modo più efficace per implementare un numero intero a base di potere funzione pow(int, int)

Question

Che cosa è il modo più efficiente dato a sollevare un intero al potere di un altro numero intero in C?

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

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

Answer 1

Elevamento a potenza elevando al quadrato.

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

    return result;
}

Questo è il metodo standard per fare esponenziazione modulare per grandi numeri di crittografia asimmetrica.

Answer 2

Nota che elevamento a potenza da squadratura non è più ottimale.È probabilmente il migliore che si può fare come un metodo generale che funziona per tutti i valori dell'esponente, ma per uno specifico valore di esponente ci potrebbe essere una migliore sequenza che ha bisogno di un minor numero di moltiplicazioni.

Per esempio, se si desidera calcolare x^15, il metodo di elevamento a potenza dalla quadratura vi darà:

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

Questo è un totale di 6 moltiplicazioni.

Si scopre che questo può essere fatto utilizzando "solo" 5 moltiplicazioni via oltre a catena di elevamento a potenza.

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

Non esiste un algoritmo efficiente per trovare questa sequenza ottimale di moltiplicazioni.Da Wikipedia:

Il problema di trovare il più breve, oltre la catena non può essere risolto con la programmazione dinamica, perché non soddisfare l'assunzione ottimale di sottostruttura.Che è, non è sufficiente per decomporre l'alimentazione in piccoli poteri, ciascuno dei quali è calcolato minimamente, dal momento che l'aggiunta di catene per potenze più piccole possono essere correlati (per condividere i calcoli).Per esempio, nel più breve aggiunta a catena per a1⁵ sopra, il subproblem per a⁶ deve essere calcolato come (a3)2 poiché la a3 è ri-utilizzato (piuttosto che, per dire, a⁶ = a2(a2)2, che richiede anche tre moltiplica).

Answer 3

Se avete bisogno di aumentare da 2 a potenza.Il modo più veloce per farlo è quello di spostamento bit per il potere.

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

Answer 4

Qui è il metodo in Java

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

Se si desidera ottenere il valore di un numero intero per 2 elevato alla potenza di qualcosa è sempre meglio utilizzare il tasto maiusc opzione:

pow(2,5) può essere sostituito da 1<<5

Questo è molto più efficiente.

Answer 7

Estremamente specializzata caso, quando hai bisogno di dire 2^(-x, y), dove x è negativo e y è troppo grande per fare la cambiata su un int.Si può ancora fare 2^x in un tempo costante, avvitando con un galleggiante.

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

È possibile ottenere maggiori potenze di 2, utilizzando un doppio come il tipo di base.(Grazie un sacco di commentatori per aiutare a piazza questo post di distanza).

C'è anche la possibilità che l'apprendimento di più su IEEE carri, altri casi particolari di elevamento a potenza potrebbe presentarsi.

Answer 8

Proprio come un follow-up per i commenti sull'efficienza di elevamento a potenza elevando al quadrato.

Il vantaggio di questo approccio è che esso viene eseguito nel log(n).Per esempio, se si dovesse andare a calcolare qualcosa di enorme, come x^1048575 (2^20 - 1), devi solo passare attraverso il ciclo di 20 volte, non 1 milioni+ utilizzando l'approccio ingenuo.

Inoltre, in termini di complessità di codice, è più semplice che cercare di trovare la migliore sequenza di moltiplicazioni, la Pramod suggerimento.

Edit:

Credo che dovrebbe chiarire prima che qualcuno tag di me per il potenziale di overflow.Questo approccio presuppone che si dispone di una sorta di hugeint biblioteca.

Answer 9

power() funzione per Solo Numeri Interi

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;

}

Complessità = O(log(exp))

power() funzione per negativo exp e 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 
    }

} 

Complessità = O(log(exp))

Answer 10

Tardi per il partito:

Qui di seguito è una soluzione che si occupa anche di y < 0 come meglio può.

1. Esso utilizza un risultato di intmax_t per la massima gamma.Non vi è alcuna disposizione per le risposte che non si adattano intmax_t.
2. powjii(0, 0) --> 1 che è un risultato comune per questo caso.

3. pow(0,negative), un altro risultato indefinito, restituisce 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;
   }
   

Questo codice utilizza un loop per sempre for(;;) per evitare di finale base *= base comune in altri loop soluzioni.Che la moltiplicazione è 1) non è necessaria e 2) possono essere int*int overflow che è UB.

Answer 11

soluzione più generica considerando negativo 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

Uno in più di attuazione (in Java).Potrebbe non essere la soluzione più efficiente, ma # di iterazioni è uguale a quella Esponenziale soluzione.

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

Io uso ricorsivo, se l'exp è anche,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

In aggiunta alla risposta di Elias, che provoca Comportamenti Indefiniti se implementato con gli interi con segno, e valori non corretti per l'input ad alta quando attuata con numeri interi senza segno

qui è una versione modificata dell'elevamento a potenza da Squadratura che funziona anche con il sottoscritto tipi interi, e non dare valori errati:

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

Considerazioni per questa funzione:

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

Se l'overflow o wrapping è andando a prendere posto, return 0;

Ho usato int64_t, ma qualsiasi larghezza (con o senza segno) può essere utilizzato con piccole modifiche.Tuttavia, se è necessario utilizzare un non-larghezza fissa di tipo intero, è necessario cambiare SQRT_INT64_MAX da (int)sqrt(INT_MAX) (nel caso di utilizzo di int) o qualcosa di simile, che dovrebbe essere ottimizzato, ma è più brutto, e non C espressione costante.Anche il risultato della fusione sqrt() per un int non è molto buona a causa della virgola mobile precission nel caso di un quadrato perfetto, ma non so di qualsiasi applicazione dove INT_MAX -o il massimo di ogni tipo - è un quadrato perfetto, si può vivere con.

Answer 15

Ho implementato un algoritmo che memorizza tutte calcolate poteri e poi li usa quando necessario.Così, per esempio, x^13 è uguale a (x^2)^2^2 * x^2^2 * x, dove x^2^2 presi dalla tabella invece di calcolo, ancora una volta.Questo è fondamentalmente l'attuazione di @Pramod risposta, ma in C#).Il numero di moltiplicazione necessario è 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);
}

Answer 16

Il mio caso è un po ' diverso, sto cercando di creare una maschera da un potere, ma ho pensato di condividere la soluzione che ho trovato comunque.

Ovviamente, funziona solo per potenze di 2.

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

Answer 17

Nel caso In cui si conosce l'esponente (e non è un numero intero) al momento della compilazione, è possibile utilizzare i modelli di srotolare il ciclo.Questo può essere reso più efficiente, ma ho voluto dimostrare il principio di base qui:

#include <iostream>

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

Abbiamo terminare la ricorsione utilizzando un modello di specializzazione:

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

L'esponente deve essere conosciuta in fase di esecuzione,

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

Answer 18

Ignorando il caso speciale di 2 elevato a potenza, il modo più efficace sarà semplice iterazione.

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

  return res;
}

EDIT:Come è stato sottolineato che questo non è il modo più efficace...così a lungo come si definisce efficienza come i cicli di cpu che credo sia abbastanza giusto.