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
- Rejestracja:ponad 11 lat
- Ostatnio:prawie 6 lat
- Postów:86
0
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
edytowany 11x, ostatnio: Tytanowyy
_13th_Dragon
O jakie liczby chodzi, bo jak o normalne mieszczące się w double to oba sposoby są równoznaczne i oba gorsze niż da się zrobić?
- Rejestracja:ponad 19 lat
- Ostatnio:2 miesiące
- Rejestracja:prawie 11 lat
- Ostatnio:ponad 4 lata
- Postów:140
1
W obu przypadkach wykonasz k+1 mnożeń więc nie ma różnicy. @_13th_Dragon Dlaczego według Ciebie najlepiej a^2k ?
- Rejestracja:prawie 11 lat
- Ostatnio:ponad 4 lata
- Postów:140
0
Przecież potęgowanie to właśnie mnożenie.
To policz 2^(0.5) mnożąc.
No dobrze, ale tu akurat możemy dojść aż do poziomu mnożeń sprzętowych. Jeżeli jest ktoś w stanie powiedzieć mi dlaczego x<sup>2k jest lepsze niż x</sup>k * x^k to słucham.
Zle, ja to tylko tak rozpisałem w komentarzu. Chodzi o to co wyżej, że lepiej najpierw podnieść do połowy potęgi a potem pomnożyć przez siebie.
- Rejestracja:ponad 11 lat
- Ostatnio:prawie 6 lat
- Postów:86
0
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!
edytowany 1x, ostatnio: Tytanowyy
- Rejestracja:prawie 11 lat
- Ostatnio:ponad 4 lata
- Postów:140
0
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.
Jeżeli masz durnie zrealizowane potęgowanie to masz durne wnioski.
Czyli jesteś za głupi żeby wytłumaczyć. Rozumiem, zdarza się. Ktoś inny ?
Nie, to ty jesteś za głupi by zrozumieć że realizacja b^n jako seria n mnożeń to jest najgłupszy algorytm z możliwych
Panowie, panować nad słownictwem! @Lukasz_ - chcesz pożegnać się na jakiś czas z dostępem do forum? @_13th_Dragon - przystopuj trochę;
- Rejestracja:ponad 19 lat
- Ostatnio:2 miesiące
4
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.
edytowany 1x, ostatnio: _13th_Dragon
Tak jest o wiele lepiej, i przynajmniej wartość merytoryczna dużo większa dla wszystkich. Zwracam honor ;)
- Rejestracja:ponad 13 lat
- Ostatnio:prawie 10 lat
- Postów:95
2
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żymyretprzeza^(2^k)obliczone wcześniej.
edytowany 4x, ostatnio: Oak
... gwoli ścisłości, to nie jest mój sposób.
Pomijając szczegóły implementacji robisz dokładnie to co opisałem.
To się zgadza, ale sam sposób był wymyślony raczej przed moim urodzeniem.
W to nie wątpię. Sam kiedyś go wyprowadziłem bez większych problemów. :)
No właśnie to napisałem: - "to
nie jest mój sposób"
Tak, ale na początku zrozumiałem to jako "nie opisałeś mojego sposobu".
- Rejestracja:ponad 19 lat
- Ostatnio:2 miesiące
1
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.