Witam, mam do Was pytanie, którą z operacji lepiej wykonać, mając parzystą potęgę, podnieść liczbę (a2)k czy (ak)2 Dzięki pozdrawiam
już pomijając kwestię formatowania, to i tak nie rozumiem, o co ci chodzi w podnieść liczbę a^2k do (a^2)^k czy też (a^k)^2
Co do czego chcesz podnosić?
Wybacz, korzystam z telefonu w tym momencie. Liczba a to liczba naturalna, którą chcę podnieść do parzystej potęgi 2k. I teraz mam pytanie, czy lepiej jest to zrobić w taki sposób: (a2)k czy (ak)2
Skąd takie pytanie, otóż w książce przeczytałem, że lepiej jest wykorzystać taki sposób niż 30 razy mnożyć liczbę, bo zaoszczędza się trochę pamięci - wydaje mi się to oczywiste, natomiast pytam się, bo może jest jeszcze jakaś róźnica przy mnożeniu potęgi
Zdecydowanie najlepiej a(2*k)
W obu przypadkach wykonasz k+1 mnożeń więc nie ma różnicy. @_13th_Dragon Dlaczego według Ciebie najlepiej a^2k ?
Bo potęgowanie jest bardziej kosztowne od mnożenia.
Przecież potęgowanie to właśnie mnożenie.
Tak, chodzi o liczby mieszczące się w typie double. Pytam się, bo myślałem, że jest jakaś różnica jeszcze przy wykorzystywaniu tego sposobu.
A to ciekawe, bo właśnie w książce mam napisane, że najlepiej jest robić tym, o którym wspomniałem.
Czyli @_13th_Dragon sugerujesz, że najlepiej jest używać sposobu tego, który podałeś, tak?
Pytam tylko tak orientacyjnie, bo skoro w książce piszą o 'zaoszczędzaniu pamięci', to chciałbym wiedzieć, który sposób jest w rzeczywistości lepszy.
Dzięki za odpowiedzi!
Też tak uważam, o ile kompilator nam czegoś nie uprości sam to mnożenie liczb 2k razy jest bardziej kosztowne niż mnożenie k+1. Ze ściśle matematycznego punktu widzenia.
Potęgowanie to można zrealizować za pomocą O(lg(2k)) mnożeń używając prostego algorytmu rekurencyjnych kwadratów. Można go opisać tak:
a^0 = 1
a^(2k) = let t = a^k in t*t
a^(2k+1) = let t = a^k in a*t*t
Jeżeli chodzi o liczby typu double
to istnieje np w C/C++ funkcja double pow(double,double)
która przeważnie jest realizowana jako: double pow(double b,double p) { return exp(p*log(b)); }
w innych językach podobnie. Jak widać podwójne wykorzystanie pow
da gorszy wynik.
Dla potęg które są liczbami całkowitymi ma sens zrobienia tego w następujący sposób:
double pow(double b,unsigned p)
{
double ret;
for(ret=1;p;b*=b,p>>=1) if(p&1) ret*=b;
return ret;
}
wynik dokładnie ten sam.
PS
Tak a propos, jeżeli chodzi o to drugie potęgowanie to najlepszym sposobem będzie:
double x=pow(b*b,k);
ponieważ:
*
double x=pow(b,k);
x*=x;
- nieco gorzej się czyta;
double x=pow(b,2*k);
będzie miał o dwa mnożenia oraz jedno przesunięcie i dwa warunki więcej.
Odnośnie sposobu @_13th_Dragon - warto opisać skąd on się bierze. Biorąc dowolną liczbę a i potęgę naturalną n zamieniamy potęgę n na system dwójkowy. Zatem:n = 1*b[0] + 2*b[1] + 4*b[2] + 8*b[3] + 16*b[4] + ...
gdzie b[k]
przyjmują wartości 0 lub 1 (są kolejnymi bitami liczby n). Chcemy policzyć a^n
, czyli:a^(1*b[0] + 2*b[1] + 4*b[2] + 8*b[3] + ...) = a^(b[0]) * (a^2)^(b[1]) * (a^4)^(b[2]) * (a^8)^(b[3]) * ...
Algorytm jest taki:
- Zaczynamy od
ret = 1
(element neutralny mnożenia). - Liczmy kolejne kwadraty:
a, a^2, a^4, a^8, a^16, ...
- Jeżeli k-ty bit jest zapalony w liczbie n (
(n >> k) & 1 != 0
), to mnożymyret
przeza^(2^k)
obliczone wcześniej.
Mam jeszcze jedno pytanie do Państwa, czy algorytm który wykorzystuje mnożenie do obliczenia potęgi będzie lepszym rozwiązaniem niż użycie rdzennej funkcji do obliczania potęgi? Pozdrawiam
Rdzennej czyli z math ?
To zależy, jak już wspomniał @bogdans nie policzysz 20.5 za pomocą mnożenia.
Wydaje mi się (tak naprawdę trzeba przeprowadzić badanie, a wynik będzie zależał od procesora) że przy k
w granicach do 25 powinno być szybsze poprzez mnożenie.
No rzeczywiście, byłby problem, nawet o tym nie pomyślałem :). Jeszcze raz dzięki za odpowiedz i i pozdrawiam
Zarejestruj się i dołącz do największej społeczności programistów w Polsce.
Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.