Problem z algorytmem potęgowania

Mógłby ktoś napisać jak się potęguje metodą dziel i zwyciężaj?

Może po prostu rozłożysz potęgę na wiele części, np.

Masz: 2^10
Rozkładasz potęgę na czynniki pierwsze: 2^{5 + 2}5

int liczbaresztlokalna;
int liczbareszt = 0;
int liczbadzielen = 0;
int wynik;
int potega;
int liczba;

while (potega>=2)
{
 liczbaresztlokalna=potega%2;
 liczbareszt=liczbaresztlokalna+liczbareszt;
 potega=potega/2;
 liczbadzielen=liczbadzielen+1;
}
while (liczbadzielen>=1)
{
 wynik=wynik*wynik;
 liczbadzielen=liczbadzielen-1;
}
while (liczbareszt>0)
{
 wynik=wynik*liczba;
 liczbareszt=liczbareszt-1;
}

@mgx8: przecież 2^{10 to 2}5*2^5 a nie suma

#include <iostream>

int pow2(int liczba, unsigned int potega) {
  if(!potega || liczba == 1) return 1;
  return potega == 1 ? liczba :  pow2(liczba, potega/2) * pow2(liczba, potega/2) * (potega%2 ? liczba : 1);
}

int main() {
  int a, b;
  std::cin >> a >> b;
  std::cout << pow2(a, b);
}

Trochę nie na temat, ale przy okazji chciałbym pokazać, jak to zrobić efektywnie za pomocą algorytmu szybkiego potęgowania (pisałem bez kompilatora, więc mogą być drobne błędy).

int pow(int liczba, unsigned int potega) {
  int wyn = 1;
  int mnoznik = liczba;
  while (potega){
     if (potega & 1) {
         wyn *= mnoznik;
      }
      mnoznik *=  mnoznik;
      potega >>= 1;
  }
   return wyn;
}

__krzysiek85 napisał(a)

Trochę nie na temat, ale przy okazji chciałbym pokazać, jak to zrobić efektywnie za pomocą algorytmu szybkiego potęgowania (pisałem bez kompilatora, więc mogą być drobne błędy).

int pow(int liczba, unsigned int potega) {
  int wyn = 1;
  int mnoznik = liczba;
  while (potega){
     if (potega & 1) {
         wyn *= mnoznik;
      }
      mnoznik *=  mnoznik;
      potega >>= 1;
  }
   return wyn;
}

"&1" i ">>=" to nie są żadne optymalizacje (bo nic nie przyśpieszają - to mity), tylko zły styl. Kod pisany w ten sposób czyta się TRAGICZNIE. Powinno być "potega%2" i "potega /= 2".
A algorytm jest dokładnie ten sam, tylko zapisany iteracyjnie.
(oprócz przypadku liczba = 1)

Inaczej, kiedyś przyspieszało, gdy optymalizatory nie potrafiły wychwycić takich rzeczy. Teraz to już nie ma różnicy bo, przynajmniej większość nowych, powinna to wychwycić i poprawić.

Kiedyś, znaczy w latach siedemdziesiątych ubiegłego wieku. Obecnie takie idiotyzmy tylko utrudniają kompilatorowi optymalizację - program bez takich tricków będzie najpewniej wydajniejszy od ręcznie 'optymalizowanego'. Obecne kompilatory wspierają profilowanie do kompilacji - sporo programów dostaje ogromnego kopa po przekompilowaniu z użyciem danych z profilowania. Poza tym aby takie optymalizacje robić należy znać dokładnie właściwości docelowego procesora, bez tego prędzej spowolnisz kod niż przyspieszysz - obecne procesory różnią się znacząco od 386.

To kolejny mit w społeczności 'programistów', który przynosi wyłącznie straty - utrudnia innym pracę z tak 'zoptymalizowanym' kodem. Jeżeli coś trzeba faktycznie zoptymalizować bardzo niskopoziomowo to wynajmuje się kodera żeby to faktycznie w assemblerze napisał, jednak od lat takich przypadków nie spotykałem.