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.
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.
Obliczenie iloczynu liczb a = 13 i b = 7 wymaga najpierw utworzenia tabelki.
| 13 | 7 |
| 6 | 14 |
| 3 | 28 |
| 1 | 56 |
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.
| 13 | 7 |
| 6 | |
| 3 | 28 |
| 1 | 56 |
Po podliczeniu okazuje się, że 13·7 = 7 + 28 + 56 = 91.
Metoda sprawdza się również podczas mnożenia większych liczb takich jak 181 i 78.
| 181 | 78 |
| 90 | |
| 45 | 312 |
| 22 | |
| 11 | 1248 |
| 5 | 2496 |
| 2 | |
| 1 | 9984 |
Sumując nie skreślone wartości z drugiej kolumny zostaje otrzymany wynik 181·78 = 78 + 312 + 1248 + 2496 + 9984 = 14118.
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:
| 13 | 1 | 7 = 7·20 |
| 6 | 0 | 14 = 7·21 |
| 3 | 1 | 28 = 7·22 |
| 1 | 1 | 56 = 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.
Oto przykładowa implmentacja funkcji Iloczyn(), która korzysta z obliczeń arytmetycznych w celu obliczenia wyniku mnożenia podanych argumentów a i b.
(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.
Poniższy kod testuje działanie funkcji Iloczyn() poprzez wczytanie liczb a i b od użytkownika, a następnie wypisanie wyniku.
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.