Potęgowanie

Koziołek

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

Jeden błąd

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

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

}

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

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 metodą łańcuchów sumacyjnych Pippenger'a lub krzywych eliptycznych Koblitz'a.

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

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...

@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 :)

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

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

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


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 ]---