Potęgowanie liczby - zaoszczędzenie pamięci

0

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

1

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ć?

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

1

Zdecydowanie najlepiej a(2*k)

1

W obu przypadkach wykonasz k+1 mnożeń więc nie ma różnicy. @_13th_Dragon Dlaczego według Ciebie najlepiej a^2k ?

0

Bo potęgowanie jest bardziej kosztowne od mnożenia.

0

Przecież potęgowanie to właśnie mnożenie.

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!

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.

2

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

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:

  1. Zaczynamy od ret = 1 (element neutralny mnożenia).
  2. Liczmy kolejne kwadraty: a, a^2, a^4, a^8, a^16, ...
  3. Jeżeli k-ty bit jest zapalony w liczbie n ((n >> k) & 1 != 0), to mnożymy ret przez a^(2^k) obliczone wcześniej.
0

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

0

Rdzennej czyli z math ?

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.

0

No rzeczywiście, byłby problem, nawet o tym nie pomyślałem :). Jeszcze raz dzięki za odpowiedz i i pozdrawiam

1 użytkowników online, w tym zalogowanych: 0, gości: 1