it-swarm-eu.dev

Nejúčinnější způsob implementace celočíselné výkonové funkce pow (int, int)

Jaký je nejúčinnější způsob, jak zvýšit celé číslo na sílu dalšího čísla v C?

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

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

Umocnění squaringem.

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

    return result;
}

Toto je standardní metoda pro modulární umocnění pro obrovská čísla v asymetrické kryptografii.

362
Elias Yarrkov

Všimněte si, že umocnění squaringem není nejoptimálnější metodou. Je to asi nejlepší, co můžete udělat jako obecná metoda, která funguje pro všechny hodnoty exponentu, ale pro konkrétní hodnotu exponentu může být lepší sekvence, která vyžaduje méně násobení.

Například, pokud chcete vypočítat x ^ 15, způsob umocnění pomocí squaringu vám dá:

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

To je celkem 6 násobení.

Ukazuje se, že to lze provést pomocí "jen" 5 násobení přes umocnění přídavného řetězce .

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

Neexistují žádné efektivní algoritmy pro nalezení této optimální sekvence násobení. Z Wikipedie :

Problém nalezení nejkratšího adičního řetězce nelze vyřešit dynamickým programováním, protože nesplňuje předpoklad optimální substruktury. To znamená, že není dostačující rozložit moc na menší síly, z nichž každá je počítána minimálně, protože adiční řetězce pro menší mocnosti mohou být vztaženy (ke sdílení výpočtů). Například, v nejkratším sčítání řetězec pro¹⁵ nahoře, subproblem pro a⁶ muset být počítán jak (a³)? Protože protože? Je re-použitý (jak protichůdný k, říkat, a⁶ = a? (??)?), Který také vyžaduje tři násobky\t ).

59
Pramod

Pokud potřebujete zvýšit 2 na výkon. Nejrychlejší způsob, jak toho dosáhnout, je posunutí o sílu.

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

Zde je metoda v jazyce 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;
}
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

Extrémně specializovaný případ je, když potřebujete říci 2 ^ (- x k y), kde x je samozřejmě záporné a y je příliš velké na to, aby se posunovalo na int. Stále můžete 2 × x v konstantním čase přišroubovat plovákem.

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

Můžete získat více pravomocí 2 pomocí dvojité jako základní typ. (Díky moc komentátorům za pomoc při hraní tohoto příspěvku pryč).

Existuje také možnost, že se dozvíte více o IEEE se vznáší , další speciální případy umocnění se mohou projevit.

6
Doug T.

Chcete-li získat hodnotu celého čísla pro 2, zvýšíte sílu něčeho, co je vždy lepší použít volbu posunu:

pow(2,5) může být nahrazeno 1<<5

To je mnohem efektivnější.

6
aditya

Stejně jako navázání na komentáře o efektivitě umocňování.

Výhodou tohoto přístupu je, že běží v log (n) době. Například, pokud jste chtěli spočítat něco obrovského, například x ^ 1048575 (2 ^ 20 - 1), musíte pouze projít smyčkou 20 krát, ne 1 milion + pomocí naivního přístupu.

Také z hlediska složitosti kódu je jednodušší, než snažit se najít nejoptimálnější posloupnost násobení, la Pramodův návrh.

Upravit:

Myslím, že bych si měl ujasnit, než mě někdo označí za potenciál přetečení. Tento přístup předpokládá, že máte nějakou obrovskou knihovnu.

4
Jason Z

power() funkce pro Pouze celá čísla  

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;

}

Složitost = O(log(exp))

power() funkce pro práci s negativní exp a 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 
    }

} 

Složitost = O(log(exp))

4
roottraveller

Pozdní strana: 

Níže je řešení, které se také zabývá y < 0 co nejlépe. 

  1. Používá výsledek intmax_t pro maximální rozsah. Neexistuje žádné ustanovení pro odpovědi, které se nevejdou do intmax_t
  2. powjii(0, 0) --> 1 což je společný výsledek pro tento případ.
  3. pow(0,negative), další nedefinovaný výsledek, vrátí 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;
    }
    

Tento kód používá navždy smyčku for(;;), aby se zabránilo poslednímu base *= base společnému v jiných řešeních smyček. Toto násobení je 1) nepotřebné a 2) by mohlo být přetečení int*int, což je UB.

2
chux

Ještě jedna implementace (v Javě). Nesmí být nejefektivnějším řešením, ale počet iterací je stejný jako u exponenciálního řešení.

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

obecnější řešení s ohledem na negativní exponent

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

Implementoval jsem algoritmus, který zapamatuje všechny vypočítané síly a pak je použije v případě potřeby. Tak například x ^ 13 se rovná (x ^ 2) ^ 2 ^ 2 * x ^ 2 ^ 2 * x, kde x ^ 2 ^ 2 je převzato z tabulky namísto opětovného výpočtu. Počet potřebných násobení je 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);
}
1
rank1

V případě, že víte, že exponent (a je to celé číslo) při kompilaci, můžete použít k vytvoření smyčky šablony. To může být efektivnější, ale chtěl jsem zde ukázat základní princip:

#include <iostream>

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

Rekurzi ukončíme pomocí specializace šablony:

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

Exponent musí být znám za běhu,

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

Můj případ je trochu jiný, snažím se vytvořit sílu z moci, ale myslel jsem, že bych se podělil o řešení, které jsem našel.

Je zřejmé, že funguje pouze pro síly 2.

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

Používám rekurzivní, pokud exp je sudý, 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

Kromě odpovědi Elias, která způsobuje nedefinované chování při implementaci s celými čísly podepsanými, a nesprávné hodnoty pro vysoký vstup při implementaci s celými čísly bez znaménka,

zde je upravená verze umocnění ze strany Squaring, která také pracuje s typem celých čísel a nedává nesprávné hodnoty:

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

Úvahy o této funkci:

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

Pokud dojde k přetečení nebo zabalení, return 0;

Použil jsem int64_t, ale libovolnou šířku (podepsanou nebo nepodepsanou) lze použít s malou úpravou. Pokud však potřebujete použít celé číslo bez pevné šířky, budete muset změnit SQRT_INT64_MAX podle (int)sqrt(INT_MAX) (v případě použití int) nebo něco podobného, ​​které by mělo být optimalizováno, ale je to ošklivější a ne C konstantní výraz. Také odlévání výsledku sqrt() do int není příliš dobré, protože v případě dokonalého čtverce je to přesnost s plovoucí desetinnou čárkou, ale protože nevím o žádné implementaci, kde INT_MAX -nebo maximum jakéhokoli typu- je dokonalý čtverec s tím můžete žít.

0
Cacahuete Frito