Algorytm mnożenia, zlożoność w przypadku pesymistycznym.

hacz · Post autor: **hacz** » 13 lis 2009, o 10:05

Prosze o pomoc z rozwiązaniem poniższego zadania.

\(\displaystyle{ Mnoz(y, z) & & \\
x \gets 0; & & \\
while \ z > 0; & & \\
do \ if \ z \ mod \ 2 = 1 \ then \ x\getsx + y; & & \\
y\gets2 * y; & & \\
z\gets\lfloor z/2\rfloor; & & \\
return \ x;}\)

Należy określić ile razy zostanie wykonane dodawanie (instrukcja w wierszu 4) w przypadku pesymistycznym.

smiechowiec · Post autor: **smiechowiec** » 13 lis 2009, o 12:58

Tyle razy ile bitów o wartości 1 ma liczba z czyli maksymalnie długość liczby z lub logarytm przy podstawie 2 z liczby z.

hacz · Post autor: **hacz** » 13 lis 2009, o 13:32

A czy
\(\displaystyle{ if \ z \ mod \ 2=1}\)
nie wplynie jakos na liczbe wykonań operacji dodawania, np zmniejszy ją o połowe?

smiechowiec · Post autor: **smiechowiec** » 13 lis 2009, o 16:56

Operacja if zawsze spowalnia działania programu bo jej wynik nie jest dla procesora znany przed jej wykonaniem co utrudnia keszowanie ciągu instrukcji.
z mod 2 testuje właśnie najmłodszy bit liczby z w danej chwili (jest to równoważne instrukcji z & 1)
Natomiast z = z/2 to przesunięcie bitów liczby w prawo o jeden czyli (z >>= 1)
Czyli dodawanie jest wtedy wykonywane gdy kolejny bit liczby z (licząc od prawej) wynosi 1.
Więc w najgorszym przypadku, gdy liczba z składa się z samych jedynek, dodawań wykonamy tyle ile cyfr ma liczba z.