Algorytmy i Struktury Danych - NWD

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\in\mathbb{Z}}\).

Wyjście:

NWD liczb \(a\) i \(b\).

Lista kroków:

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

Przykładowe programy

Uwaga:

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.

Pascal

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

program prg;

var a, b : cardinal;

begin
  readln(a, b);
  while a <> b do
    if a < b then
      b := b-a
    else
      a := a-b;
  writeln(a);
end.

C++

// NWD-wersja z odejmowaniem
// Data: 12.03.2008
// (C)2020 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;
}

Basic

' NWD-wersja z odejmowaniem
' Data: 12.03.2008
' (C)2020 mgr Jerzy Wałaszek
'----------------------------

Dim As Uinteger a, b

Input a, b
While a <> b
  If a < b Then
    b -= a
  Else
    a -= b
  End If
Wend
Print a
End

Python (dodatek)

# NWD-wersja z odejmowaniem
# Data: 03.02.2024
# (C)2024 mgr Jerzy Wałaszek
#----------------------------

arr = input().split()
a = int(arr[0])
b = int(arr[1])
while a != b:
    if a < b:
        b -= a
    else:
        a -= b
print(a)

Wynik:

18 24
6

JavaScript

<html>
  <head>
    <title>
      ...
    </title>
  </head>
  <body>
<div style="overflow-x: auto; overflow-y: hidden;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm1"
        style="text-align: center;
               background-color:
               #E7E7DA">
          <b>Algorytm Euklidesa</b><br/>
          &nbsp;&nbsp;&nbsp;
          (C)2026 mgr Jerzy Wałaszek
          &nbsp;&nbsp;&nbsp;
          <hr>
          a = <input
              type="text"
              name="inp_a"
              size="16"
              value="18"
              style="text-align:
                     right">
          <br>
          b = <input
              type="text"
              name="inp_b"
              size="16"
              value="24"
              style="text-align:
                     right">
          <hr>
          <input
          type="button"
          value="Wykonaj"
          name="B1"
          onclick="main1()">
          <hr>
          <b>Wynik:</b>
          <div id="out1">.</div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script type=text/javascript
        language=javascript>
// NWD-wersja z odejmowaniem
// Data   : 12.03.2008
// (C)2008 mgr Jerzy Wałaszek
//---------------------------

function main1()
{
  let a, b, t;

  a = parseInt(document.frm1
      .inp_a.value);
  b = parseInt(document.frm1
      .inp_b.value);
  if(!isNaN(a) && !isNaN(b))
  {
    while(a != b)
      if(a < b) b -= a;
      else a -= b;
    t = a;
  }
  else t = "Złe dane wejściowe!";
  document.getElementById("out1")
  .innerHTML = t;
}

</script>

  </body>
</html>

do podrozdziału do strony

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\), \(b\) z \({a \bmod 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\in\mathbb{Z}}\).

Wyjście:

NWD liczb \(a\) i \(b\).

Elementy pomocnicze:

\(t\) : tymczasowo przechowuje dzielnik, \({t\in\mathbb{Z}}\).

Lista kroków:

K01:	Dopóki \(b\ne0:\) wykonuj kroki K02…K04
K02:	\(t\leftarrow b\) ; zapamiętujemy dzielnik
K03:	\(b\leftarrow a \bmod b\) ; reszta z dzielenia staje się dzielnikiem
K04:	\(a\leftarrow t\) ; poprzedni dzielnik staje się dzielną
K05:	Pisz \(a\) ; NWD jest ostatnią dzielną
K06:	Zakończ

Przykładowe programy

Uwaga:

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.

Pascal

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

program prg;

var a, b, t : cardinal;

begin
  readln(a, b);
  while b <> 0 do
  begin
    t := b;
    b := a mod b;
    a := t;
  end;
  writeln(a);
end.

C++

// NWD-wersja z resztą z dzielenia
// Data: 12.03.2008
// (C)2020 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;
}

Basic

' NWD-wersja z resztą z dzielenia
' Data: 12.03.2008
' (C)2020 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

Python (dodatek)

# NWD-wersja z resztą z dzielenia
# Data: 12.03.2008
# (C)2020 mgr Jerzy Wałaszek
#----------------------------------

arr = input().split()
a = int(arr[0])
b = int(arr[1])
while b:
    t = b
    b = a % b
    a = t
print(a)
print()

do podrozdziału do strony

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:

\(\text{NWD}(0, b) = b\), ponieważ każda liczba naturalna dzieli zero, a \(b\) jest największą liczbą dzielącą \(b\). Podobnie \({\text{NWD}(a,0) = a}\). Natomiast \({\text{NWD}(0, 0)}\) nie jest zdefiniowane.
Jeśli liczby \(a\) i \(b\) są parzyste, to
\(\text{NWD}(a,b) = 2 \cdot \text{NWD}(\frac{a}{2},\frac{b}{2})\),
ponieważ obie posiadają wspólny podzielnik 2.
Jeśli liczba \(a\) jest parzysta, a liczba \(b\) jest nieparzysta, to
\(\text{NWD}(a,b) = \text{NWD}(\frac{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
\(\text{NWD}(a,b) = \text{NWD}(a,\frac{b}{2)\).
Jeśli obie liczby \(a\) i \(b\) są nieparzyste i \({a \ge b}\), to
\(\text{NWD}(a,b) = \text{NWD}(\frac{a − b}{2},b)\),
inaczej jeśli obie są nieparzyste i \({a < b}\), to
\(\text{NWD}(a,b) = \text{NWD}(\frac{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.
Kroki 3 i 4 należy powtarzać aż do otrzymania \({b = 0}\). Wtedy NWD jest równy \({2\cdot k\cdot a}\), 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\in\mathbb{Z}}\).

Wyjście:

NWD liczb \(a\) i \(b\).

Elementy pomocnicze:

\(k\) : przechowuje liczbę wspólnych podzielników 2; \({k\in\mathbb{Z}}\).
\(r\) : wykorzystywane do przechowywania różnicy \(a\) i \(b\); \({r\in\mathbb{Z}}\).

Lista kroków:

K01:	Jeśli \(a = 0,\) ; \(\text{NWD}(0, b) = b\) to pisz \(b\) i zakończ
K02:	Jeśli \(b = 0,\) ; \(\text{NWD}(a, 0) = a\) to pisz \(a\) i zakończ
K03:	\(k\leftarrow0\) ; inicjujemy liczbę wspólnych podzielników \(2\)
K04:	Dopóki \(a\) i \(b\) są parzyste: ; usuwamy z \(a\) i \(b\) wspólne czynniki \(2\), wykonuj kroki K05…K07 ; zapamiętując ich liczbę w \(k\)
K05	\(a\leftarrow a \gg1\) ; przesuwamy bity \(a\) o \(1\) w prawo
K06:	\(b\leftarrow b \gg1\) ; przesuwamy bity \(b\) o \(1\) w prawo
K07:	\(k\leftarrow k+1\)
K08:	Jeśli \(a = 0,\) ; \(\text{NWD}(0, b) = b\) to \(a\leftarrow b\) i idź do kroku K18
K09:	Dopóki \(a\) jest parzyste: ; eliminujemy podzielniki \(2\) z \(a\) wykonuj \(a\leftarrow a \gg1\)
K10:	Dopóki \(b\) jest parzyste, ; eliminujemy podzielniki \(2\) z \(b\), wykonuj \(b\leftarrow b\gg1\) ; teraz \(a\) i \(b\) są nieparzyste
K11:	Jeśli \(a\ge b,\) to idź do kroku K16
K12:	\(r\leftarrow (b-a)\gg1\) ; \(\text{NWD}(a, b) = \text{NWD}(\frac{b-a}{2}, a)\)
K13:	\(b\leftarrow a\) ; zamieniamy \(b\) z \(a\)
K14:	\(a\leftarrow r\) ; \(a\) z różnicą \(r\)
K15:	Idź do kroku K17
K16:	\(a\leftarrow (a-b)\gg1\) ; \(\text{NWD}(a, b) = \text{NWD}(\frac{a-b}{2}, b)\)
K17:	Jeśli \(b\ne0,\) to idź do kroku K08
K18:	Jeśli \(k > 0,\) ; przesuwamy bity \(a\) o \(k\) pozycji to \(a\leftarrow a\ll k\) ; w lewo → mnożenie przez \(2\cdot k\)
K19:	Pisz \(a\)
K20:	Zakończ

Przykładowe programy

Uwaga:

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.

Pascal

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

program prg;

var a, b, k, r : cardinal;

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.

C++

// NWD-wersja binarna z przesuwem bitów
// Data: 14.03.2008
// (C)2020 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;
}

Basic

' NWD-wersja binarna z przesuwem bitów
' Data: 13.03.2008
' (C)2020 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

Python (dodatek)

# NWD-wersja binarna z przesuwem bitów
# Data: 03.02.2024
# (C)2024 mgr Jerzy Wałaszek
# ---------------------------------------

arr = input().split()
a = int(arr[0])
b = int(arr[1])
if not a or not b:
    print(a | b)
else:
    k = 0
    while not ((a | b) & 1):
        a >>= 1
        b >>= 1
        k += 1
    while True:
        if not a:
            a = b
            break
        while not (a & 1): a >>= 1
        while not (b & 1): b >>= 1
        if a < b:
            r = (b-a) >> 1
            b = a
            a = r
        else:
            a = (a-b) >> 1
        if not b: break
    if k: a <<= k
    print(a)
print()

do podrozdziału do strony

NWD – algorytm Euklidesa

Problem

Rozwiązanie 1

Algorytm Euklidesa

Wejście:

Wyjście:

Lista kroków:

Przykładowe programy

Rozwiązanie 2

Algorytm Euklidesa

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Rozwiązanie 3

Algorytm Euklidesa

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy