Szybkie potęgowanie - ilość mnożeń

Hej, mam taki algorytm szybkiego potęgowania, znajoma jest mi już idea jego działania, proszę tylko o pomoc w policzeniu liczby mnożeń.

Mianowicie załóżmy dwa przypadki (x to liczba, n to wykładnik)

• x=2 n=134
• x=2 n=8

Czy w tym algorytmie zakładamy że wiemy ile to jest 2⁶⁷ i 2⁴? Bo jeśli tak to robimy jedno mnożenie podnosząc te liczby do kwadratu i koniec. Jeśli natomiast nie to liczba mnożeń wynosi 67 i 4 aby uzyskać dane liczby, zgadza się? w tradycyjnym algorytmie ilość mnożeń jest równa n-1. Jeśli coś źle myślę to proszę o wyprowadzenie z błędu i pomoc w zrozumieniu liczenia mnożeń jakie wykonuje ten algorytm.

potęga(x,n)
if n=0
   then return 1;
if n!%=0
return x*(potęga(x,(n-1)/2)^2
else return (potęga(x,n/2))^2
 

sory za refresh ale jutro o 8 rano mam egzamin z algorytmów i bardzo proszę o pomoc w zliczeniu tych mnożeń

przykład

załóżmy że chcemy pomnożyć tym algorytmem 2¹⁸⁷. licząc naiwnie wykonujemy 186 mnożeń (bo n-1 gdzie n to wykładnik). wykorzystując jednak algorytm szybkiego potęgowania 2¹⁸⁷ zapisujemy jako 2⁹³ - wykonujemy 92 mnożenia. Teraz 2⁹³ podnosimy do kwadratu uzyskując 2¹⁸⁶ - czyli wykonaliśmy dodatkowe jedno mnożenie, i do tego mnożymy jeszcze 2¹⁸⁶ * 2 żeby uzyskać 2¹⁸⁷ co dodaje nam jeszcze jedno mnożenie.

podsumowując - naiwnie mamy 186 mnożen, a korzystając z algorytmu mamy 94 mnożenia. Dobrze kombinuję ?

Dobrze, ilość operacji mnożenia to n/2 + 1

Edit: maksymalnie n/2 + 1

Ani trochę bo przecież tego 2⁹³ też nie mnozysz naiwnie tylko połówkując...

To znaczy mam połówkować aż do momentu gdy dalej nie będzie się dało tego rozłożyć?

Shalom mozesz to rozpisać jak to zrobić na przykładzie ? :D

No przecież chyba widzisz algorytm napisany w pierwszym poście o_O
Wyliczenie aⁿ wymaga:

• policzenia x = a^(n/2)
• pomnożenia x*x
  A wyliczenie a^(n/2) ? Analogicznie:
• policzenia x = a^(n/4)
• pomnożenia x*x
  i tak dalej...

Czyli np a⁸⁶ = a⁴³ * a⁴³ = (a²¹ * a²¹ * a) ² itd ... i tak aż dostane we wzorze same a²? Bo jeśli tak to jest to bardzo żmudne i rozpisanie np a¹⁸⁷ zajęłoby bardzo dużo czasu, aż za dużo, jak na jeden podpunkt na egzaminie ...

Żeby policzyć ile mnożeń będzie potrzebne nie trzeba tego rozpisywać, wystarczy użyć mózgu ;] Ale rozpisz sobie trochę przykładów i może dojdziesz do jakiejś zależności. Zalecam jednak rozpisywać to na zasadzie
a¹⁸⁷ = a⁴³ * a⁴³ * a -> dwa mnożenia
a⁴³ = a²¹ * a²¹ * a -> dwa mnożenia
a²¹ = a¹⁰ * a¹⁰ * a -> dwa mnożenia
a¹⁰ = a⁵ * a⁵ -> jedno mnożenie
a⁵ = a² * a² * a -> dwa mnożenia
a² = a*a -> jedno mnożenie
w sumie 2+2+2+1+2+1 = 10, chyba trochę lepiej niż twoje 94 mnożenia które proponowałeś wyżej :D
Co więcej zajęło mi to "żmudne rozpisanie" całą minutę...

Shalom napisał(a):

a¹⁸⁷ = a⁴³ * a⁴³ -> jedno mnożenie

@Shalmon popraw

@Shalom jednak mnożen jest więcej.

Zauważ że np

a¹⁸⁷ = a⁴³ * a⁴³ * a -> dwa mnożenia
a⁴³ = a²¹ * a²¹ * a -> ????dwa mnożenia???? --> sugerujesz że na tym etapie są cztery mnożenia, a czy jednak nie ma ich więcej?

czyli a¹⁸⁷ = (a²¹ * a²¹ * a) * (a²¹ * a²¹ * a) * a . -- > 6 mnożeń, a nie 4 .

No jak ktoś jest idiotą i chce dwa razy wyliczać coś co już zna to jasne. Jak policzyłeś sobie raz a⁴³ to PO CO chcesz je liczyć drugi raz? o_O Mijasz się chyba z powołaniem na tej informatyce...

A ty konkretnie w jakim celu robisz te przytyki ? Masz jakiś kłopot ze sobą ? To już nie pierwszy raz, więc może czas wyjść z domu przed komputerka do ludzi, bo niedługo stuknie 18 tysięcy postów, zastanów się nad tym.

A ty konkretnie w jakim celu robisz te przytyki

Bo mam dobre serce i chcę cię uratować przed zmarnowaniem kilku lat na studiowanie czegoś co ci się w życiu nie przyda...

Haha właśnie takiej motywacji potrzebowałem w noc zarywaną przed egzaminem :D Potęgowanie opanowane - temat do zamknięcia.

Zawsze do usług :) Powodzenia na egzaminie. Może jakimś cudem nie pojawi się zadanie w którym trzeba będzie coś wymyślić, bo może być ciężko ;]

Jak udowodnić że szybkie potęgowanie przy dzieleniu wykładnika przez 3 a nie przez 2 będzie wymagało mniejszej liczby mnożeń?

Chodzi mi o to że jak zwieszamy liczbę przez którą dzielimy to maleje liczba potrzebnych iteracji ale rośnie liczba mnożeń na iteracje i chodzi mi o to jak policzyć(analitycznie) dla jakiego dzielnika wyjdzie najlepszą wydajność. Numerycznie sprawdziłem i wychodzi że 4.
To jest ten sam problem jak znalezienie takiej podstawy reprezentacji liczb która zabiera jak najmniej pamięci. Rozwiązaniem tego problemu jest liczba e - najbliższa naturalna to 3. Tylko nie wiem jak to policzyć :C

Przy okzaji @Shalom - zdałem, dokładnie ten algorytm się pojawił i wpadł MAX także dzięki za pomoc jeszcze raz, jednak kto nie pyta ten błądzi.

A co do pytania topik92, jak już wcześniej udowodniłem to geniuszem nie jestem ale czy aby na pewno uzyskasz mniejszą złożoność obliczeniową algorytmu dla większego dzielnika?

Biorąc dla przykładu liczbę a¹⁸⁷ i rozkładając wykładnik poprzez dzielenie go przez 2 - wyszło nam 10 mnożeń. Jeśli będziemy dzielić wykładnik przez 3 to :

a¹⁸⁷= a⁶² * a⁶² * a⁶² * a ->3 mnożenia
a⁶²=a²⁰*a²⁰*a²⁰a² -> 3 mnożenia + a²=aa
i tutaj musimy rozpisać nie tylko a²⁰ ale także a² więc już widać, że ilość mnożeń będzie większa. Chyba właśnie na tym polega sukces dzielenia wykładnika przez 2, że reszta z dzielenia zawsze jest 0 lub 1. Wgl jak wpadłeś na to że dla exponenty jest to wydajniejsze ? Może indukcji matematycznej trzeba spróbować, w końcu to liczby naturalne.

Mogę się mylić. Najpewniej się mylę.

@topik92 dowód może być analityczny i opierać się będzie o takie magiczne pojęcie jak logarytm. Bo właśnie logarytm potrafi powiedzieć ci ile tych mniejszych czynników będziesz miał.
Załóżmy przypadek prosty kiedy wszystko jest potęgą 2, żeby się ładnie liczyło:
a⁶⁴ = a³² * a³²
a³² = a¹⁶ * a¹⁶
a¹⁶ = a⁸ * a⁸
a⁸ = a⁴ * a⁴
a⁴ = a² * a²
a² = a * a

Więc do policzenia mamy: a², a⁴, a⁸, a¹⁶ i a³² czyli 5 wyrazów podczas gdy log2(64) = 6
Nie jest to przypadek ;)
W przypadku ogólnym dla każdego czynnika możemy wykonać 1 lub 2 mnożenia, zależnie od tego czy był podzielny przez 2 nie. Jeśli wszystkie są podzielne to liczba potrzebnych mnożeń wyniesie po prostu log2(exponenta)-1, jeśli mamy przypadek pesymistyczny to na każdym poziomie będą potrzebne 2 mnożenia, czyli w sumie 2*(ceil(log2(exponenta))-1). Czy faktycznie tak jest? Weźmy na przykład a⁶³ i rozpiszmy tak jak poprzednio:

a⁶³ = a³¹ * a³¹ * a
a³¹ = a¹⁵ * a¹⁵ * a
a¹⁵ = a⁷ * a⁷ * a
a⁷ = a³ * a³ * a
a³ = a * a * a

Jak widać mamy tutaj 5*2 = 10 mnożeń, podczas gdy log2(63) = 5.97 i jednocześnie ceil(5.97) = 6 więc 2*(ceil(log2(exponenta))-1) = 2*(6-1) = 10

Średnio dla losowej liczby będziemy potrzebowali w połowie przypadków 2 mnożeń i w połowie 1 mnożenia, więc średnio *1.5 ale jeśli interesuje nas tylko rząd zlożoności to mamy po prostu O(log(exponenta)).

Co się zmieni jeśli zmienimy dzielnik z 2 na 3? Zmieni sie podstawa logarytmu oraz liczba mnożeń potrzebnych w jednej rundzie - tym razem będą potrzebne 2 lub 3 mnożenia. Optymistycznie będzie więc (log3(exponenta)-1)*2 a pesymistycznie (log3(exponenta)-1)*3, a średnio oczywiście *2.5 i jednocześnie rząd złożoności to O(log3(exponenta)).

Pytanie więc czy (dla przypadku średniego) funkcja (log2(n)-1)*1.5 rośnie szybciej czy wolniej od (log3(n)-1)*2.5. Polecam czytelnikowi przeprowadzić analizę obu tych funkcji w celu ustalenia stanu faktycznego, podpowiem jednak że wynikiem powinien być wniosek, że dla odpowiednio dużych n funkcja z 3 rośnie szybciej.

zrobiłem czeski błąd i dla 3 i zamiast rozkładać x⁶² na :
x²⁰ * x²⁰ * x²⁰ * x *x
rozkładałem na x^{20 * x}20 *x *x
pomijając że to jest bez sensu to w takim przypadku dla 3 i 62 wychodzi
log3(62)+log3(62)*średnia_ilość_mnożeń
średnia_ilość_mnożeń - można zastąpić zapiać ze wzoru na sumę szeregu arytmetycznego od 0 do 2 przez ilość elementów - i po skróceniu wychodzi cos takiego
log3(62)+log3(62)* (3-1)/2
jesli podstawimy za 62-n a za dzielnik d dla d > 1;

log_podstawa_d(n)+log-podstawa-d(n)*  (d-1)/2 =>
log_podstawa_d (n) (1 + (d-1)/2) =>
ln(n)/ln(d) * (1 + (d-1)/2)

co już takie trywialne i intuicyjne nie jest,
nie mogłem do tego dojść bo robiłem nie to co trzeba i cały czas się coś nie zgadzało :P.