Strona główna » Algorytmy » Artykuły » Mnożenie Etiopskie
 

Mnożenie Etiopskie

Cel

Mnożenie Etiopskie jest to metoda mnożenia dwóch dodatnich liczb całkowitych przy pomocy operacji podwajania, połowienia oraz dodawania. Interesujący jest fakt, że ma to związek z kodowaniem binarnym.

Opis metody

W celu pomnożenia dwóch liczb a i b przez siebie należy zapisać dwie kolumny liczb. Pierwsza z nich ma na początku wartość a. W każdym kolejnym wierszu znajduje się liczba całkowita dwa razy mniejsza niż w poprzednim, aż do uzyskania wartości 1. Części dziesiętne są ucinane. W drugiej kolumnie na początku należy zapisać liczbę b, a w każdym kolejnym wierszu liczbę dwa razy większą niż w poprzednim. Wynik mnożenia to suma liczb w drugiej kolumnie jeśli w tym samym wierszu w pierwszej kolumnie jest liczba parzysta.

Przykłady

Przykład 1

Obliczenie iloczynu liczb a = 13 i b = 7 wymaga najpierw utworzenia tabelki.

137
614
328
156

Teraz należy wybrać wiersze do zsumowania. Jeden ze sposobów polega na wykreśleniu z drugiej kolumny liczb nie do zsumowania jeśli w danym wierszu w pierwszej kolumnie jest liczba nieparzysta.

137
614
328
156

Po podliczeniu okazuje się, że 13·7 = 7 + 28 + 56 = 91.

Przykład 1

Metoda sprawdza się również podczas mnożenia większych liczb takich jak 181 i 78.

18178
90156
45312
22624
111248
52496
24992
19984

Sumując nie skreślone wartości z drugiej kolumny zostaje otrzymany wynik 181·78 = 78 + 312 + 1248 + 2496 + 9984 = 14118.

Jak to działa?

W celu zrozumienia całego procesu należy przyjrzeć się dokładnie procesowi wyliczania pierwszej kolumny. Wszystkie liczby parzyste wykreślają dany wiersz. W rzeczywistości dany wynik można zastąpić poprzez resztę wynikłą z dzielenia. Z kolei w drugiej kolumnie w i-tym liczba jest mnożona przez 2i. Wracając do pierwszego przykładu otrzymujemy:

1317 = 7·20
6014 = 7·21
3128 = 7·22
1156 = 7·23

Teraz można zapisać obliczenia następująco 1·7·20 + 0·7·21 + 1·7·22 + 1·7·23 = 7(1·20 + 0·21 + 1·22 + 1·23). Tu warto zauważyć, że tak naprawdę reszty z dzielenie to cyfry z kodu binarnego liczby 13 = 11012. Tego typu metodę mnożenia można zaprogramować używając przesunięć bitowych.

Implementacja

Oto przykładowa implmentacja funkcji Iloczyn(), która korzysta z obliczeń arytmetycznych w celu obliczenia wyniku mnożenia podanych argumentów a i b.

C++
C#
  1.   int suma = 0;

(2.) Początkowo suma wartości to 0. Następnie (4. - 5.) sprawdzamy czy mamy zwiększyć sumę i przed następną pętlą (6. - 7.) odpowiednio zmieniamy wartości. (8.) Warunkiem zakończenia pętli jest wartość zmiennej a wynosząca 0 (ostatnia wartość kiedy dodajemy to 1, a więc po podzieleniu będzie 0). Na koniec (9.) zwrócona zostaje obliczona suma.

Testowanie funkcji

Poniższy kod testuje działanie funkcji Iloczyn() poprzez wczytanie liczb a i b od użytkownika, a następnie wypisanie wyniku.

C++
C#
  1.   int suma = 0;

Zadania

Zadanie 1

Napisz implementację metody Mnożenia Etiopskiego wykorzystując do tego operacje bitowe. Nie wolno wykorzystywać żadnej operacji arytmetycznej (mnożenia, dzielenia, modulo) prócz dodawania. Przetestuj działanie napisanego kodu.