Strona główna » Algorytmy » Artykuły » Mnożenie rosyjskich chłopów

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

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

  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

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

abwynikOperacja
480pomijamy krok (3.)
840pomijamy krok (3.)
1620pomijamy krok (3.)
3210b nieparzyste, więc dodajemy a do wyniku
64032b jest mniejsze od 1, więc zwracamy wynik

Iloczyn 4·8 = 32.

Przykład 2

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

abwynikOperacja
20110b nieparzyste, więc dodajemy a do wyniku
40520b nieparzyste, więc dodajemy a do wyniku
80260pomijamy krok (3.)
160160b nieparzyste, więc dodajemy a do wyniku
3200220b jest mniejsze od 1, więc zwracamy wynik

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ższej funkcji main().

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

Zadania

Zadanie 1

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