Następujący rekurencyjny algorytm mnożenia dwóch liczb całkowitych dodatnich x, y jest realizowany z użyciem operacji arytmetycznych dodawania i dzielenia całkowitego przez 2.

iloczyn(x, y):

   jeżeli y = 1:

      wynikiem jest x

   w przeciwnym razie:

      k = y div 2

      z = iloczyn(x, k)

      jeżeli y mod 2 = 0:

         wynikiem jest z + z

      w przeciwnym razie:

         wynikiem jest x + z + z

Poniżej zapisano iteracyjny algorytm realizujący funkcję iloczyn(x, y). Uzupełnij trzy luki w algorytmie, tak aby był zgodny z poniższą specyfikacją.

UWAGA: spośród operacji arytmetycznych możesz użyć tylko: dodawania, odejmowania, dzielenia całkowitego i reszty z dzielenia. Nie możesz użyć zwłaszcza operacji mnożenia.

Specyfikacja:
Dane:
x, y – liczby całkowite dodatnie
Wynik:
z – wartość iloczynu x*y

Algorytm:

z = ____________

dopóki ______________ wykonuj:

   jeżeli y mod 2 = 1

      z = z + x

   x = x + x

   y = _____________