Mnożenie rosyjskich chłopów

Wstęp

Mnożenie rosyjskich chłopów pozwala na pomnożenie dwóch liczb naturalnych w niewielkiej ilości kroków. Jest to jeden z algorytmów, które komputery mogą wykonywać tylko przy użyciu operacji binarnych. Podobny system mnożenia został opracowany również w Egipcie. Nazwa jednak pochodzi od rosyjskich chłopów, którzy w XIX w. bardzo często posługiwali się tą metodą.

Algorytm

Przyjmijmy za a = 4 i za b = 8, wtedy:

1. Ustal wynik na 0
2. Jeśli liczba b jest nieparzysta to dodaj a do wyniku
3. Pomnóż a przez 2, a b podziel przez dwa. Tutaj należy wykonać dzielenie całkowitoliczbowe
4. Jeśli b jest większe od 0 to wróć do punktu 2
5. Zwróć wynik

Przykład 1

Przypuśćmy, że mamy dwie liczby naturalne a i b.

Iloczyn 4·8 = 32.

Przykład 2

Przyjmijmy za a = 20 i za b = 11, wtedy:

Iloczyn 20·11 = 220.

Implementacja

Wersja arytmetyczna

Wersja arytmetyczna w celu obliczenia wyniku korzysta z operacji mnożenia i dzielenia. Jest najdokładniejszym odzwierciedleniem przedstawionej na początku listy kroków do wykonania. Funkcja przyjmuje dwie nieujemne liczby a i b.

1. unsigned int russianPeasantArithmetic(unsigned int a, unsigned int b) {
2.   unsigned int wynik = 0;
3.   while (b > 0) {
4.     if (b % 2 == 1)
5.       wynik += a;
6.     a *= 2;
7.     b /= 2;
8.   }
9.   return wynik;
10. }

(2.) Zadeklaruj zmienną wynik i ustaw jej wartość 0. (3.) Dopóki b > 0 to (3.) sprawdź parzystość b jeśli reszta wynosi 1 to (4.) dodaj do wyniku a. Następnie odpowiednio (5.) pomnóż a przez 2 i (6.) podziel b przez 2. Na koniec (8.) zwróć wynik.

Wersja z operatorami binarnymi

W tej wersji kodu operacje arytmetyczne zostaną zastąpione przez operacje binarne. Kolejno dotyczy to (4.) sprawdzania parzystości liczby. W tym celu wystarczy sprawdzić bit na najmniej znaczącym miejscu. W przypadku 1 będzie to liczba nieparzysta i zostanie to potraktowane jako prawda.

Operacje (5.) mnożenie i (6.) dzielenia przez 2 można zastąpić poprzez przesunięcia bitów. W celu pomnożenia wystarczy przesunąć bity w lewo, a przesunięcie w prawo podzieli liczbę przez 2.

1. unsigned int russianPeasantBinary(unsigned int a, unsigned int b) {
2.   unsigned int wynik = 0;
3.   while (b > 0) {
4.     if (b & 1)
5.       wynik += a;
6.     a <<= 1;
7.     b >>= 1;
8.   }
9.   return wynik;
10. }

Testowanie funkcji

W celu przetestowania obu funkcji można skorzystać z poniższego fragmentu kodu.

1. int main () {
2.   cout << russianPeasantArithmetic(3, 1) << endl;
3.   cout << russianPeasantBinary(5, 3) << endl;
4.   system("pause");
5.   return 0;
6. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz algorytm realizujący zadanie Mnożenie rosyjskich chłopów wykorzystując do tego rekurencje.

• Kod źródłowy Zadanie 1