Algorytmy

Potęgowanie

Podnoszenie liczby do potęgi można zrealizowac na kilka sposobów. Pierwszy z nich to zwykła pętla:
public long power1(int a, int b) {
        long wynik = 1;
        for (int i = b; i > 0; i--) {
                wynik *= a;
        }
        return wynik;
}

jest to najbardziej nieefektywny sposób. Szczególnie jest to widoczne przy dużych wykładnikach. Cały algorytm ma złożoność liniową względem parametru b. Oznacz to że im wyższa potęga tym dłużej jest on wykonywany. Dla b równego N należy wykonać N-1 mnożeń. Za dużo.
Inną metodą jest zapisanie potęgi jako sumy liczb np. 51 = 25 + 12 + 6 + 3 + 3 + 1 oraz zauważenie iż ab = a z * ax gdzie b = z + x. Ok teraz jak dojść do tego jakie liczby należy zsumować? Wystarczy w każdym kroku podnosić do kwadratu wartość z kroku poprzedniego (otrzymujemy a1, a2, a4 itd. ) i mnożyć przez pamiętany wynik jeżeli w rozwinięciu binarnym wykładnika pojawia się jedynka. Po co? Każdą liczbę można zapisać jako sumę potęg dwójki jednak nieparzysta wymaga dodania jeszcze jedynki. W naszym przypadku oznacza to, że dodajemy do siebie kolejne potęgi dwójki z rozwinięcia wykładnika (inaczej mnożymy podstawy podniesione do potęg które są kolejnymi potęgami dwójki) co pewien czas mnożąc trzymany w pamięci wynik przez ten uzyskane w pętli:
public long power2(int a, int b) {
        long wynik = 1;
        long v = a;
        for (int i = b; i > 0; i /= 2) {
                if (i % 2 == 1) {
                        wynik = wynik * v;
                }
                v = v * v;
        }
        return wynik;
}

Złożoność jest jak logN. Czyli można powiedzieć że szybciej już się nie da.

8 komentarzy

goransol 2011-10-09 13:33

Jeden błąd

double Potega(double Podstawa, double Wykladnik)
{
       if (Podstawa < 0 )
            Podstawa *= -1;

        return (exp(log(Podstawa)*Wykladnik));
}

Koziołek 2007-06-28 20:45

Dobra... Dopisywać inne metody panowie. Bo się zrobi mówiąc nieładnie burdel jak będziemy to wsztko w komentarzach wrzucać·

Szczawik 2007-06-28 16:20

Przy implementacjach dużych liczb też nie stosuje się powyższej metody, bo mimo wszystko jest zbyt wolna - istnieje algorytm jakiegoś tam kolesia (nazwiska nie pamiętam, ale algorytm był opisany na Wikipedii).

Dopisane: Rozwiązania te zaliczają się do grupy obliczania funkcji eksponencjalnej metodą kwadratów (powyższa jest na niej oparta; złożoność Θ(log n) ) lub <url=http://cr.yp.to/papers/pippenger.pdf>metodą łańcuchów sumacyjnych Pippenger'a</url> lub krzywych eliptycznych Koblitz'a.

@Koziołek - co do funkcji exp() kliknij na nią w kodzie a zobaczysz jej opis.

Pawel200x.5 2007-06-28 15:10

Szczawik: Robi, robi, np. przy implementacji Bardzo Dużych Liczb. :P
Koziołek: metoda Szczawika jest nowocześniejsza i dużo wydajniejsza (na pewno jeśli chodzi o potęgowanie liczb przecinkowych), bo wykorzystuje koprocesor...

Koziołek 2007-06-28 14:02

@Szczawik, a jak działa exp() w twoim przykładzie? Chodziło o podanie "bebechów" a nie wykorzystanie gotowej funkcji.
Jest jeszcze jedna metoda, która działa w C/C++ i to pod warunkiem że wiemy do której potęgi i co podnosimy. Wystarczy napisać skrypt prekompilatora, który wyliczy odpowiednią stałą i ją podstawi. Meta programowanie fajna rzecz :)

Szczawik 2007-06-28 13:06

Nikt nie robi przecież potęgowania/pierwiastkowania w oparciu o pętle!

double Potega(double Podstawa, double Wykladnik)
{
    return (exp(log(Podstawa)*Wykladnik));
}

Spykaj 2007-06-28 10:26

Hmmm :P krótko, zwięźle, prosto i na temat. Podoba mi się ;D

Xitami 2007-07-29 18:46

----------------------------------------------------------------------------------------------------------------------
Sposobu lepszego niż power2 chyba niema.
A jeśli chodzi o wielkie liczby, to chodzi o to, że mnożenie można zrealizować na wiele sposobów, a najwolniejszym (dla odpowiednio wielkich liczb) jest sposób opart na metodzie której uczono nas w szkole podstawowej.
Ważne nazwiska które powinny się tu jeszcze znaleźć to Karatsuba, Toom i Fourier (FFT).
--------------------------------------------------------------------------------------------------------[ Xitami ]---