NWD - algorytm Euklidesa


Tematy pokrewne   Podrozdziały
Przedziały liczbowe i liczby
Liczby parzyste i nieparzyste
Liczby podzielne lub niepodzielne przez zadane podzielniki
Ciągi arytmetyczne
NWD – algorytm Euklidesa
Liczby względnie pierwsze
Najmniejsza wspólna wielokrotność
Odwrotność modulo – rozszerzony algorytm Euklidesa
Liczby pierwsze – generacja przez sprawdzanie podzielności
Liczby pierwsze – generacja sitem Eratostenesa
Liczby pierwsze – generacja sitem liniowym
Liczby pierwsze – generacja sitem Atkina-Bernsteina
Czynniki pierwsze – metoda próbnych dzieleń
Czynniki pierwsze – metoda Fermata
Pierwszość liczby naturalnej – algorytmy naiwne
Pierwszość liczby naturalnej – Chiński Test Pierwszości
Pierwszość liczby naturalnej – Małe Twierdzenie Fermata
Pierwszość liczby naturalnej – test Millera-Rabina
Liniowe generatory liczb pseudolosowych
Generator pseudolosowy Park-Miller
Generator pseudolosowy Mersenne Twister
Wbudowane generatory liczb pseudolosowych
Generowanie liczb pseudolosowych
Liczby Fibonacciego
System liczbowy Fibonacciego
Całkowity pierwiastek kwadratowy
  Rozwiązanie 1
Rozwiązanie 2
Rozwiązanie 3

 

Problem

Dla danych dwóch liczb naturalnych a i b znaleźć największą liczbę naturalną c, która dzieli bez reszty liczbę a i dzieli bez reszty liczbę b.

 

 

Liczba c o powyższej własności nosi nazwę NWD największego wspólnego dzielnika a i b (ang. GCD – greatest common divisor). NWD znajdujemy za pomocą znanego algorytmu Euklidesa, będącego jednym z najstarszych algorytmów, ponieważ pojawił się on w dziele Elementy napisanym przez Euklidesa około 300 p.n.e. Właściwie Euklides nie podał algorytmu dla liczb, lecz dla dwóch odcinków. Chodziło w nim o znalezienie wspólnej miary (czyli odcinka jednostkowego), która mogłaby posłużyć do zmierzenia obu danych odcinków – wspólna miara odkłada się w każdym z odcinków całkowitą liczbę razy.

 

 

Rozwiązanie 1

Euklides wykorzystał prosty fakt, iż NWD liczb a i b dzieli również ich różnicę. Zatem od większej liczby odejmujemy w pętli mniejszą dotąd, aż obie liczby się zrównają. Wynik to NWD dwóch wyjściowych liczb.

 

Algorytm Euklidesa

Wejście

a, b  liczby naturalne, których NWD poszukujemy, a, b N

Wyjście:

NWD liczb a i b

Lista kroków:
K01: Dopóki ab wykonuj krok K02  
K02:     Jeśli a < b, to bb - a
    inaczej          aa - b
; od większej liczby odejmujemy mniejszą aż się zrównają
K03: Pisz a ; wtedy dowolna z nich jest NWD
K04: Zakończ  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje z pierwszego wiersza dwie liczby a i b, a następnie wypisuje w następnym wierszu ich NWD. Żadna z liczb a i b nie może wynosić 0 – wtedy różnica nie zmienia większej z nich i program działa w nieskończoność. Niedogodność tę da się prosto zlikwidować – proponuję to jako ćwiczenie dla czytelników.

 

Lazarus
// NWD - wersja z odejmowaniem
// Data   : 12.03.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

program prg;

var a,b : longword;

begin
  readln(a,b);
  while a <> b do
    if a < b then b := b - a
    else          a := a - b;
  writeln(a);
end.
Code::Blocks
// NWD - wersja z odejmowaniem
// Data   : 12.03.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>

using namespace std;

int main()
{
  unsigned int a,b;

  cin >> a >> b;
  while(a != b)
    if(a < b) b -= a; else a -= b;
  cout << a << endl;
  return 0;
}
Free Basic
' NWD - wersja z odejmowaniem
' Data   : 12.03.2008
' (C)2012 mgr Jerzy Wałaszek
'----------------------------

Dim As Uinteger a,b

Input a,b
While a <> b
  If a < b Then b -= a: Else: a -= b
Wend
Print a
End
Wynik
18 24
6
 

Algorytm Euklidesa
(C)2012 mgr Jerzy Wałaszek

a = , b =


...

 

Rozwiązanie 2

Pierwsze rozwiązanie problemu znajdowania NWD jest złe z punktu widzenia efektywności. Wyobraźmy sobie, iż a jest równe 4 miliardy, a b jest równe 2. Pętla odejmująca będzie wykonywana dotąd, aż zmienna a zrówna się ze zmienną b, czyli w tym przypadku 2 miliardy razy – trochę dużo. Tymczasem można wykorzystać operację reszty z dzielenia. Mniejszą liczbę można odjąć od większej liczby tyle razy, ile wynosi iloraz całkowity tych liczb. Po odejmowaniu pozostaje reszta z dzielenia – a Euklides właśnie zauważył, iż NWD dzieli również różnicę danych liczb, czyli:

 

NWD(a,b) = NWD(a mod b,b)

 

Ponieważ reszta zawsze jest mniejsza od dzielnika, wymieniamy a z b, a b z a mod b. Jeśli otrzymamy wynik b = 0, to w a jest ostatni dzielnik dzielący bez reszty różnicę.

 

Algorytm Euklidesa

Wejście

a, b  liczby naturalne, których NWD poszukujemy, a, b N

Wyjście:

NWD liczb a i b

Zmienne pomocnicze

t – tymczasowo przechowuje dzielnik,  t N

Lista kroków:
K01: Dopóki b ≠ 0 wykonuj kroki K02...K04  
K02:     t b ; zapamiętujemy dzielnik
K03:     ba mod b ; wyznaczamy resztę z dzielenia, która staje się dzielnikiem
K04:     at ; poprzedni dzielnik staje teraz się dzielną
K05: Pisz a ; NWD jest ostatnią dzielną
K06: Zakończ  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje z pierwszego wiersza dwie liczby a i b, a następnie wypisuje w następnym wierszu ich NWD.

 

Lazarus
// NWD - wersja z resztą z dzielenia
// Data   : 12.03.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

program prg;

var a,b,t : longword;

begin
  readln(a,b);
  while b <> 0 do
  begin
    t := b;
    b := a mod b;
    a := t;
  end; 
  writeln(a);
end.
Code::Blocks
// NWD - wersja z resztą z dzielenia
// Data   : 12.03.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>

using namespace std;

int main()
{
  unsigned int a,b,t;

  cin >> a >> b;
  while(b)
  {
    t = b;
    b = a % b;
    a = t;
  } 
  cout << a << endl;
  return 0;
}
Free Basic
' NWD - wersja z resztą z dzielenia
' Data   : 12.03.2008
' (C)2012 mgr Jerzy Wałaszek
'----------------------------

Dim As Uinteger a,b,t

Input a,b
While b
  t = b
  b = a Mod b
  a = t
Wend
Print a
End

 

Rozwiązanie 3

Istnieje algorytm znajdowania NWD, w którym nie wykonuje się dzieleń – są one kłopotliwe dla małych procesorów, np. dla kontrolerów jednoukładowych, i zajmują stosunkowo dużo czasu procesora. Algorytm ten wykorzystuje fakt, iż wszystkie liczby są przechowywane w komputerze w postaci ciągu bitów. Operacje dzielenia z resztą zastępuje się przesunięciami bitów, które są proste w realizacji i wykonywane szybko, nawet na najprostszym sprzęcie komputerowym. W efekcie otrzymujemy około 60% przyrost szybkości wyznaczania NWD w stosunku do standardowego algorytmu Euklidesa. Opisywany algorytm nosi nazwę binarnego algorytmu NWD (ang. binary GCD algorithm).

Algorytm redukuje problem znajdowania NWD przez stosowanie poniższych równoważności:

  1. NWD(0, b) = b, ponieważ każda liczba naturalna dzieli zero, a b jest największą liczbą dzielącą b. Podobnie NWD(a, 0) = a. Natomiast NWD(0, 0) nie jest zdefiniowane.
  2. Jeśli liczby a i b są parzyste, to NWD(a, b) = 2NWD(a/2, b/2), ponieważ obie posiadają wspólny podzielnik 2.
  3. Jeśli liczba a jest parzysta a b jest nieparzysta, to NWD(a, b) = NWD(a/2, b), ponieważ 2 nie jest wspólnym podzielnikiem i można go pominąć. Podobnie jest w przypadku odwrotnym, gdy a jest nieparzyste a b jest parzyste, wtedy NWD(a, b) = NWD(a, b/2).
  4. Jeśli obie liczby a i b są nieparzyste, a ab, to NWD(a, b) = NWD((ab)/2, b), inaczej jeśli obie są nieparzyste i  a < b, to NWD(a, b) = NWD((b-a)/2, a). Takie same operacje wykonuje w pętli podstawowy algorytm Euklidesa – od większej liczby odejmuje mniejszą. Podzielenie różnicy przez 2 daje zawsze liczbę całkowitą, ponieważ odejmowane są dwie liczby nieparzyste.
  5. Kroki 3 i 4 należy powtarzać aż do otrzymania b = 0. Wtedy NWD jest równy 2ka, gdzie k jest liczbą wspólnych czynników 2 wyeliminowanych w kroku 2. Mnożenie 2k wykonujemy przez przesunięcie bitów zmiennej a o k pozycji w lewo.

 

Algorytm Euklidesa

Wejście

a, b  liczby naturalne, których NWD poszukujemy, a, b Z

Wyjście:

NWD liczb a i b

Zmienne pomocnicze

k – przechowuje liczbę wspólnych podzielników 2,  k Z
r
– wykorzystywane do przechowywania różnicy a i b, r Z

Lista kroków:
K01: Jeśli a = 0, to pisz b i zakończ ; NWD(0,b) = b
K02: Jeśli b = 0, to pisz a i zakończ ; NWD(a,0) = a
K03: k ← 0 ; inicjujemy liczbę wspólnych podzielników 2
K04: Dopóki a i b parzyste wykonuj kroki K05...K07 ; usuwamy z a i b wspólne czynniki 2, zapamiętując ich liczbę w k
K05:     aa shr 1 ; przesuwamy bity a o 1 w prawo
K06:     bb shr 1 ; przesuwamy bity b o 1 w prawo
K07:     kk + 1  
K08: Jeśli a = 0, to ab i idź do K18 ; NWD(0,b) = b
K09: Dopóki a parzyste wykonuj aa shr 1 ; eliminujemy podzielniki 2 z a
K10: Dopóki b parzyste wykonuj bb shr 1 ; eliminujemy podzielniki 2 z b, teraz a i b są nieparzyste
K11: Jeśli ab, to idź do K16  
K12: r ← (b - a) shr 1 ; NWD(a,b) = NWD((b-a)/2,a)
K13: ba ; zamieniamy b z a
K14: ar ; a z różnicą r
K15: Idź do K17  
K16: a ← (a - b) shr 1 ; NWD(a,b) = NWD((a-b)/2,b)
K17: Jeśli b ≠ 0, to idź do K08  
K18: Jeśli k > 0, to aa shl k ; przesuwamy bity a o k pozycji w lewo mnożenie przez 2k
K19: Pisz a  
K20: Zakończ  

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje z pierwszego wiersza dwie liczby a i b, a następnie wypisuje w następnym wierszu ich NWD.

 

Lazarus
// NWD - wersja binarna z przesuwem bitów
// Data   : 13.03.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

program prg;

var a,b,k,r : longword;

begin
  readln(a,b);
  if (a = 0) or (b = 0) then writeln(a or b)
  else
  begin
    k := 0;
    while ((a or b) and 1) = 0 do
    begin
      a := a shr 1;
      b := b shr 1;
      inc(k);
    end;
    repeat
      if a = 0 then
      begin
        a := b;
        break;
      end;
      while (a and 1) = 0 do a := a shr 1;
      while (b and 1) = 0 do b := b shr 1;
      if a < b then
      begin
        r := (b - a) shr 1;
        b := a;
        a := r;
      end
      else a := (a - b) shr 1;
    until b = 0;
    if k > 0 then a := a shl k;
    writeln(a);
  end;
end.
Code::Blocks
// NWD - wersja binarna z przesuwem bitów
// Data   : 14.03.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>

using namespace std;

int main()
{
  unsigned int a,b,k,r;

  cin >> a >> b;
  if(!a || !b) cout << (a | b) << endl;
  else
  {
    for(k = 0; !((a | b) & 1); k++)
    {
      a >>= 1;
      b >>= 1;
    }
    do
    {
      if(!a)
      {
        a = b; break;
      }
      while(!(a & 1)) a >>= 1;
      while(!(b & 1)) b >>= 1;
      if(a < b)
      {
        r = (b - a) >> 1;
        b = a;
        a = r;
      }
      else a = (a - b) >> 1;
    } while(b);
    if(k) a <<= k;
    cout << a << endl;
  }
  return 0;
}
Free Basic
' NWD - wersja binarna z przesuwem bitów
' Data   : 13.03.2008
' (C)2012 mgr Jerzy Wałaszek
'----------------------------

Dim As Uinteger a,b,k,r

Input a,b
If (a = 0) Or (b = 0) Then
    Print a Or b
Else
  k = 0
  While ((a Or b) And 1) = 0
    a = a Shr 1
    b = b Shr 1
    k += 1
  Wend
  Do
    If a = 0 Then
      a = b
      Exit Do
    End If
    While (a And 1) = 0: a = a Shr 1: Wend
    While (b And 1) = 0: b = b Shr 1: Wend
    If a < b Then
      r = (b - a) Shr 1
      b = a
      a = r
    Else
      a = (a - b) Shr 1
    End If
  Loop Until b = 0
  If k > 0 Then a = a Shl k
  Print a
End If
End

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.