Dotaz: c++ mocnina na n

[marek33]

Ahoj mám takový dotaz, v c++ jsem zkoušel vytvořit mocninu na n-tou, nevíte někdo jak na to ??

---

---

Odpovědi

[chrono]

V <cmath> je funkcia std::pow

[marek33]

myslel jsem pomocí funkce if

[Šangala]

Vyšel bych z: IF „hlad“ GOTO „lednice“

[Jary]

if není funkce. A když už bys to rád dělal nějak divně složitě, proč to neuděláš pomocí operátorů & | ^?

[chrono]

Dalo by sa použiť aj if, ale rozumnejšie by mohlo byť for (a if pre n=0 alebo 1)

[l4m4]

Chceš kód obsaující if? Chceš efektivní algoritmus pro celočíselné mocniny? Všechno lze zařídit!

double mocnina(double x, int i)
{
    double r = 1.0;
    if (!i)
        return 1.0;
    bool negative = false;
    if (i < 0) {
        negative = true;
        i = -i;
    }
    for ( ; ; ) {
        if (i & 1)
            r *= x;
        if (!(i >>= 1))
            break;
        x *= x;
    }
    return negative ? 1.0/r : r;
}

Jen nevím, jak budeš vysvětlovat, jak to funguje...

[Radovan]

Pěkné, ale říká se "co je malé, to je hezké"

double mocnina(double x,int y)
       {
       return x*(y>1?mocnina(x,--y):1);
       }

[l4m4]

Tam ovšem není žádný if. Cílem bylo mít tam nějaké ify ;)

[Radovan]

If tam je, jenomže maskovaný

double mocnina(double x,int y)
       {
       if (y>1)
          return x*mocnina(x,--y);
       else
          return 1;
       }

Ale jinak je to blbost dobrá akorát na hraní.

[libco]

Je tam chyba.

Má tam byť:

else

return x;

[Vtipnéř]

Spíš

if (y>0)

Jirka

[Michal Kubeček]

"Hezké" možná, ale máte podstatně horší časovou složitost vůči exponentu a ještě budete muset spoléhat na inteligenci překladače, abyste se nedostal do problémů s přetečením zásobníku.

[l4m4]

Jo, a samozřejmě tohle počítá mocnina(x, 1000000) pomocí 999999 násobení, kdežto mnou uvedený kód pomocí 27 násobení ;)

[lertimir]

Takhle to dopadne, když programátor kašle na výpočetní složitost algoritmů.

[l4m4]

Popravdě řečeno, takle by ten algoritmus byl vhodný pro GMP (kde samozřejmě mocnina nějak podobně implementována je), protože tam je cena nějakých bitových operací a dokonce i podmínek zanedbatelná vůči ceně násobení dvou čísel, a především pro jiné typy než double, které zvládne __builtin_powi()...

Jelikož jsou nejčastěji zapotřebí nízké mocniny, bylo by vhodné pro ně konkrétní výpočty zadrátovat -- a navíc to celé hodit do makra s __builtin_constant_p(), aby se to pro nízké předem známé mocniny optimálně inlinovalo.

A když se bavíme o C++, tak lze ostatně téhož dosáhnout šablonou, kde je ta mocnina coby parametr, a specializací pro nízké mocniny. Akorát nevím, zda by tam pak byly nějaké ify ;)

[Sten]

Když jde o C++, použil bych šablony, ať to počítá rovnou překladač

template <int base,
          int pow>
struct mocnina
{
    enum {
        value = base * mocnina<base, pow - 1>::value
    };
};

template <int base>
struct mocnina<base, 0>
{
    enum {
        value = 1
    };
};

[l4m4]

error: template instantiation depth exceeds maximum of 900

[Ivan]

Na MSVC je max hloubka rekurze sablon 2500. Na g++ je konfigurovatelna (je na to nejaky parameter).

[potato]

Na druhé straně potřebuje-li kód úroveň vnoření šablon větší než 900, někde je cosi podezřelého...

[rastos]

jsem zkoušel vytvořit

Ano? A ako ďaleko si sa dostal?

[pavlix]

A já myslel, že domácí úkoly se řeší samostatně.

[Xóža Hňabaj]

int mocnina(int x,y) {
  if (y == 2) return x*x;
  if (y == 3) return x*x*x;
  if (y == 4) return x*x*x*x;
  if (y == 5) return x*x*x*x*x;
  if (y == 6) return x*x*x*x*x*x;
  if (y == 7) return x*x*x*x*x*x*x;
  if (y == 8) return x*x*x*x*x*x*x*x;
  if (y == 9) return x*x*x*x*x*x*x*x*x;
  if (y == 10) return x*x*x*x*x*x*x*x*x*x;
  if (y == 11) return x*x*x*x*x*x*x*x*x*x*x;
  if (y == 12) return x*x*x*x*x*x*x*x*x*x*x*x;
  if (y == 13) return x*x*x*x*x*x*x*x*x*x*x*x*x;
  if (y == 14) return x*x*x*x*x*x*x*x*x*x*x*x*x*x;
  if (y == 15) return x*x*x*x*x*x*x*x*x*x*x*x*x*x*x;
  if (y == 16) return x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x;
  if (y == 17) return x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x;
  if (y == 18) return x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x;
  if (y == 19) return x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x;
  return x;
}

Je to najlepsia verzia lebo obsahuje najviac ifov. Pre profesionalnu verziu si na zaciatok mozes doplnit assert(y<20);

[chrono]

Prípadne sa tam môže pridať ešte jedno if a rekurzia. :)

[Pavel Kocman]

Dělávali jsme to pomocí for ciklu, tím mohla být mocnina doopravdy libovolná, ale už si nevzpomínám. Taky to potřebuju.

[libco]

double mocnina_x(double cislo, int umocni_na)

{

     int i, vysledok = 1;

     for (i = 1; i <= umocni_na; i++)

     vysledok *= cislo;

     return vysledok;

}

[Bill Gates]

Mozna by se to dalo jeste zoptimalizovat z pohledu delky kodu programu ... Treba na arduinu, kde obcas setrime kazdy bajt by byla lepsi verze ponekud modifikovana (viz nize), dle testovaci kompilace to vychazi pro arduino Mega o 228 bytu lip :) a 228 bajtu na arduinu = misto na plno dalsich funkci. Tedy za predpokladu ze potrebujeme nezbytne nutne pouzit ify :D

void setup() {
int x=10;
int y=10;
int q=mocnina(x,y);
Serial.println(q);
}

int mocnina(int x,int y) {
  if (y == 2) return x*x;
  if (y == 3) return x*x*x;
  if (y == 4) return x*x*x*x;
  if (y == 5) return x*x*x*x*x;
  if (y == 6) return x*x*x*x*x*x;
  if (y == 7) return x*x*x*x*x*x*x;
  if (y == 8) return x*x*x*x*x*x*x*x;
  if (y == 9) return x*x*x*x*x*x*x*x*x;
  if (y == 10) return x*x*x*x*x*x*x*x*x*x;
  if (y == 11) return x*x*x*x*x*x*x*x*x*x*x;
  if (y == 12) return x*x*x*x*x*x*x*x*x*x*x*x;
  if (y == 13) return x*x*x*x*x*x*x*x*x*x*x*x*x;
  if (y == 14) return x*x*x*x*x*x*x*x*x*x*x*x*x*x;
  if (y == 15) return x*x*x*x*x*x*x*x*x*x*x*x*x*x*x;
  if (y == 16) return x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x;
  if (y == 17) return x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x;
  if (y == 18) return x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x;
  if (y == 19) return x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x;
  return x;
}

void loop() { }

Binary sketch size: 4,084 bytes

void setup() {
int x=10;
int y=10;
int q=mocnina(x,y);
Serial.println(q);
}

int mocnina(int c,int y) {
  int x=c;
  if (y >= 2) x*=c;
  if (y >= 3) x*=c;
  if (y >= 4) x*=c;
  if (y >= 5) x*=c;
  if (y >= 6) x*=c;
  if (y >= 7) x*=c;
  if (y >= 8) x*=c;
  if (y >= 9) x*=c;
  if (y >= 10) x*=c;
  if (y >= 11) x*=c;
  if (y >= 12) x*=c;
  if (y >= 13) x*=c;
  if (y >= 14) x*=c;
  if (y >= 15) x*=c;
  if (y >= 16) x*=c;
  if (y >= 17) x*=c;
  if (y >= 18) x*=c;
  if (y >= 19) x*=c;
  return x;
}

void loop() { }

Binary sketch size: 3,856 bytes

[Kit]

Zkus to ještě porovnat s tím, co napsal libco. 3,856 B mi připadá strašně moc.

[Bill Gates]

void setup() {
int x=10;
int y=10;
int q=mocnina(x,y);
Serial.println(q);
}


double mocnina(double cislo, int umocni_na)
{
int i, vysledok = 1;
for (i = 1; i <= umocni_na; i++)
vysledok *= cislo;
return vysledok;
}

void loop() { }

Binary sketch size: 4,068 bytes

void setup() {
int x=10;
int y=10;
int q=mocnina(x,y);
Serial.println(q);
}


int mocnina(int cislo, int umocni_na)
{
int i, vysledok = 1;
for (i = 1; i <= umocni_na; i++)
vysledok *= cislo;
return vysledok;
}

void loop() { }

Binary sketch size: 3,454 bytes

[Bill Gates]

void setup() {
int x=10;
int y=10;
int q=mocnina(x,y);
Serial.println(q);
}


double mocnina(double x,int y) {
return x*(y>1?mocnina(x,--y):1);
}
       
void loop() { }

Binary sketch size: 3,950 bytes

void setup() {
int x=10;
int y=10;
int q=mocnina(x,y);
Serial.println(q);
}


int mocnina(int x,int y) {
return x*(y>1?mocnina(x,--y):1);
}
       
void loop() { }

Binary sketch size: 3,474 bytes

[Ivan]

A to co stenovo reseni? Vysledek vypocita kompilator behem kompilace a do zdrojaku dosadi primo konstantu:

0000000000400578 <main>:
  400578:       48 83 ec 08             sub    $0x8,%rsp
  40057c:       48 be 00 e4 0b 54 02    mov    $0x2540be400,%rsi
  400583:       00 00 00
  400586:       bf 98 06 40 00          mov    $0x400698,%edi
  40058b:       31 c0                   xor    %eax,%eax
  40058d:       e8 d6 fe ff ff          callq  400468 <printf@plt>
  400592:       5a                      pop    %rdx
  400593:       31 c0                   xor    %eax,%eax
  400595:       c3                      retq

0x2540be400 = 10^10