Strona główna » Algorytmy » Artykuły » Algorytm Steina
 

Algorytm Steina

https://mattomatti.com/a0031

Wstęp

Tak samo jak w przypadku algorytmu Euklidesa algorytm Steina służy do wyliczania NWD (największego wspólnego dzielnika) dla dwóch liczb naturalnych. Jednak proces przyśpieszenia obliczeń pociąga za sobą szereg warunków co czyni algorytm trudny do zapamiętania.

Algorytm

W celu obliczenia NWD algorytmem Steina przyjmuje się, że:

  1. NWD(0, 0) = 0
  2. NWD(a, 0) = a i analogicznie NWD(0, b) = b
  3. Jeśli a i b są liczbami parzystymi to NWD(a, b) = 2·NWD(a/2, b/2)
  4. Jeśli a parzyste i b nieparzyste to NWD(a, b) = NWD(a/2, b) i analogicznie jeśli b parzyste i a nieparzyste
  5. Jeśli a i b są nieparzyste to NWD(a, b) = NWD(|a - b|/2, b)

Kroki od (3.) do (5.) należy wykonywać w pętli, aż a = b lub a = 0. Jeśli po wykonaniu któreś operacji liczba a < b to liczby należy zamienić miejscami. W każdym przypadku znaleziona wartość to 2k·b. Oznacza to, że w podanym algorytmie wszystkie dwójki z rozkładu na czynniki pierwsze są zawsze znajdowane i usuwane z liczb.

Uzasadnienie

Punkt (1.) jest kwestią umowną i wygodną podczas obliczeń. Punkt (2.) wynika z faktu, że 0 dzieli każda liczba. Następny podpunkt (3.) to szybkie wyszukiwanie 2 z rozkładu na czynniki pierwsze z obu liczb. W ten sposób liczby bardzo szybko maleją. Na podobnej zasadzie działa punkt (4.), który z kolei usuwa zbędne wartości 2 z rozkładu na czynniki pierwsze liczby parzystej. Warto tu zauważyć, że jeśli jedna liczba jest parzysta, a druga nie to nigdy obie nie będą podzielne przez 2. W ostatnim podpunkcie (5.) ważny jest fakt, że różnica dwóćh liczb nieparzystych a i b jest parzysta, więc po podzieleniu przez dwa nie mają prawa pojawić się liczby z częścią ułamkową.

Przykład

Spróbujmy obliczyć podanym algorytmem NWD(34, 99).

abKomentarz
3699b > a, zamiana liczb miejscami
9936a nieparzyste, b parzyste, więc NWD(99, 36) = NWD(99, 36/2)
9918a nieparzyste, b parzyste, więc NWD(99, 18) = NWD(99, 18/2)
999a i b nieparzyste, więc NWD(99, 9) = NWD(|99 - 9|/2, 9)
459a i b nieparzyste, więc NWD(45, 9) = NWD(|45 - 9|/2, 9)
369a parzyste, b nieparzyste, więc NWD(36, 9) = NWD(36/2, 9)
189a parzyste, b nieparzyste, więc NWD(18, 9) = NWD(18/2, 9)
99a = b, więc NWD(99, 36) = 9

Implementacja

Podany algorytm można napisać w wersji arytmetycznej oraz przy pomocy operacji binarnych. Ze względu na to, że algorytm będzie wykonywał program to w toerii zdecydowanie lepszy pomysłem jest zastosowanie operacji binarnych. Jednak warto poznać oba rozwiązania.

Wersja arytmetyczna

Przestawiony poniżej kod realizuje metodę Steina w wersji iteracyjnej. Oznacza to, że kroki (3. - 5.) listy kroków są wykonywane w pętli, aż do uzyskania wyniku. Na początku (2. - 4.) sprawdzane są warunki początkowe po których jest zapewnione, że a i b są różne od 0.

  1. int NWD(int a, int b) {
  2.   if (a == b) return a;
  3.   if (a == 0) return b;
  4.   if (b == 0) return a;
  5.   int wynik = 1;
  6.   while (a != b) {
  7.     if (b > a)
  8.       swap(b, a);
  9.     if (a % 2 == 0 && b % 2 == 0) {
  10.       wynik *= 2;
  11.       a /= 2;
  12.       b /= 2;
  13.     } else if (a % 2 == 0 && b % 2 != 0) {
  14.       a /= 2;
  15.     } else if (a % 2 != 0 && b % 2 == 0) {
  16.       b /= 2;
  17.     } else if (a % 2 != 0 && b % 2 != 0) {
  18.       a = abs(a - b) / 2;
  19.     }
  20.   }
  21.   return wynik * a;
  22. }

(5.) Deklarowana zmienna wynik będzie zbierać wartości 2 z rozkładu, które są zabierane z liczb w przypadku, gdy obie są parzyste. (6.) W pętli dopóki nie jest spełniony warunek początkowy to: (7. - 8.) program upewnia się, że a jest większe, równe b. Następnie w zależności od wartości a i b (9. - 19.) wykonywana jest odpowiednia operacja. Na koniec (21.) należy pamiętać, że rozwiązaniem jest a lub b (mają te same wartości) pomnożone przez wartość zmiennej wynik.

Operacje binarne

Podczas działania algorytmu wykonywane są jedynie operacje sprawdzania czy liczba jest parzysta oraz operacje dzielenia / mnożenia przez 2. Wszystkie te operacje arytmetyczne można zastąpić przesunięciami bitowymi - odpowiednio o 1 w lewo lub prawo.

Pozostaje jeszcze kwestia sprawdzania parzystości liczb. W najgorszym przypadku parzystość każdej z liczb jest sprawdzana dokładnie cztery razy. Proces ten można udoskonalić sprawdzając tylko raz. Przypuśćmy, że 0 oznacza parzysta, a 1 nieparzysta. Znając parzystości liczb tworzymy dwucyfrową liczbę binarną i na jej podstawie wybieramy z jakim przypadkiem mamy do czynienia czyli np. 10 oznaczałaby a nieparzyste i b parzyste.

Po tych zmianach kod ma podobną strukturę, ale nie używa już żadnych operacji arytmetycznych:

  1. int NWD(int a, int b) {
  2.   if (a == b) return a;
  3.   if (a == 0) return b;
  4.   if (b == 0) return a;
  5.   int wynik = 1;
  6.   while (a != b) {
  7.     if (b > a)
  8.       swap(b, a);
  9.     switch (((a & 1) << 1) | (b & 1)) {
  10.       case 0:
  11.         wynik <<= 1;
  12.         a >>= 1;
  13.         b >>= 1;
  14.       break;
  15.       case 1:
  16.         a >>= 1;
  17.         break;
  18.       case 2:
  19.         b >>= 1;
  20.         break;
  21.       case 3:
  22.         a = (abs(a - b) >> 1);
  23.         break;
  24.     }
  25.   }
  26.   return wynik * a;
  27. }

Testowanie funkcji

W celu przetestowania napisaną funkcję NWD() można skorzystać z poniższej funkcji main():

  1. int main() {
  2.   int a, b;
  3.   cout << "Podaj dwie liczby\na = ";
  4.   cin >> a;
  5.   cout << "b = ";
  6.   cin >> b;
  7.   cout << "NWD(" << a << ", " << b << ") = " << NWD(a, b);
  8.   system("pause");
  9.   return 0;
  10. }

Zadania

Zadanie 1

Napisz rekurencyjną wersję algorytmu Steina wykorzystują do tego:

  1. operacje arytmetyczne
  2. operacje binarne

Sprawdź poprawnosć napisanych funkcji.