Szybkie potęgowanie od lewej do prawej

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
PowerMan
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 21 lis 2010, o 15:29
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz

Szybkie potęgowanie od lewej do prawej

Post autor: PowerMan »

Witajcie, moim zadaniem jest obliczenie potęg (*) przy wykorzystaniu algorytmu szybkiego potęgowania od lewej do prawej strony, oraz określenie ilości wykonanych mnożeń potrzebnych do wyznaczenia (**) również przy pomocy alg. szybkiego potęgowania OD LEWEJ DO PRAWEJ.
\(\displaystyle{ (*):
a) 2^{22}
b) 2^{15}

(**):
a)x ^{7}
b)x ^{48}
c)x ^{79}}\)


no to lecimy:
\(\displaystyle{ a) 22= _{2}10110}\)
więc
\(\displaystyle{ x ^{10110}=x ^{(((1 \cdot 2+0) \cdot 2+1) \cdot 2+1) \cdot 2+0)} = (((x ^{2} \cdot x^{0})^{2} \cdot x)^{2} \cdot x)^{2} =(((x ^{2})^{2} \cdot x)^{2} \cdot x)^{2}= (((2 ^{2})^{2} \cdot 2)^{2} \cdot 2)^{2} = ((4^{2} \cdot 2)^{2} \cdot 2)^{2}=((32)^{2} \cdot 2)^{2}=(1024 \cdot 2)^{2}=2048^{2}=4194304}\)
czyli wynik poprawny.

b) \(\displaystyle{ 15=_{2} 1111}\)
więc
\(\displaystyle{ x^{1111}=x^{((1 \cdot 2+1) \cdot 2+1) \cdot 2+1)}=x ^{((2+1) \cdot 2+1) \cdot 2+1}=((x^{2} \cdot x)^{2} \cdot x)^{2} \cdot x=((4 \cdot 2)^{2} \cdot 2)^{2} \cdot 2=(64 \cdot 2)^{2} \cdot 2=16384 \cdot 2=32768}\)
czyli wynik poprawny.


(**):
a)
\(\displaystyle{ x^{7}=_{2}x^{111}=x^{(1 \cdot 2+1) \cdot 2+1}=((x^{2} \cdot x)^{2} \cdot x =>}\) mamy 2 mnożenia
b)
\(\displaystyle{ x^{48}=_{2}x^{110000}=x^{((((1 \cdot 2+1) \cdot 2+0) \cdot 2+0) \cdot 2+0) \cdot 2+0}=x^{(((2+1) \cdot 2) \cdot 2) \cdot 2) \cdot 2}=((((x^{2} \cdot x)^{2})^{2})^{2})^{2} =>}\) mamy 1 mnożenie
c)
\(\displaystyle{ x^{79}=_{2}x^{1001111}=x^{((((((1 \cdot 2+0) \cdot 2+0) \cdot 2+1) \cdot 2+1) \cdot 2+1) \cdot 2+1}=x^{((((((2) \cdot 2) \cdot 2+x) \cdot 2+x) \cdot 2+x) \cdot 2 \cdot x}=x^{2})^{2})^{2} \cdot x)^{2} \cdot x)^{2} \cdot x)^{2} \cdot x =>}\) mamy 4 mnożenia

Proszę Was o sprawdzenie poprawności tego co napisałem ze szczególnym uwzględnieniem tego iż ma być to tylko algorytm szybkiego potęgowania od lewej do prawej.
Gdyby coś się nie zgadzało, dajcie znać.


Właściwie to już sam nie wiem czy użyłem algorytmu od lewej do prawej czy od prawej do lewej. Co źródło w sieci to inna wersja, jeśli ktoś jest pewien proszę o odpowiedź, jaka to jest wersja algorytmu.
ta druga jest chyba ładniejsza bo np
\(\displaystyle{ x^{22}=x^{10110}=x^{1 \cdot 2^{4}+0 \cdot 2^{3}+1 \cdot 2^{2}+1 \cdot 2^{1}+1 \cdot 2^{0}}\)
Ostatnio zmieniony 6 mar 2012, o 20:07 przez Jan Kraszewski, łącznie zmieniany 2 razy.
Powód: Nowa linia w LaTeXu to \\. Symbol mnożenia to \cdot.
ODPOWIEDZ