How to resolve the algorithm Greatest common divisor step by step in the Modula-2 programming language

Published on 12 May 2024 09:40 PM
#Modula-2

How to resolve the algorithm Greatest common divisor step by step in the Modula-2 programming language

Table of Contents

Problem Statement

Find the greatest common divisor   (GCD)   of two integers.

Greatest common divisor   is also known as   greatest common factor (gcf)   and   greatest common measure.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Greatest common divisor step by step in the Modula-2 programming language

Source code in the modula-2 programming language

MODULE ggTkgV;

FROM    InOut           IMPORT  ReadCard, WriteCard, WriteLn, WriteString, WriteBf;

VAR   x, y, u, v        : CARDINAL;

BEGIN
  WriteString ("x = ");         WriteBf;        ReadCard (x);
  WriteString ("y = ");         WriteBf;        ReadCard (y);
  u := x;
  v := y;
  WHILE  x # y  DO
    (*  ggT (x, y) = ggT (x0, y0), x * v + y * u = 2 * x0 * y0          *)
    IF  x > y  THEN
      x := x - y;
      u := u + v
    ELSE
      y := y - x;
      v := v + u
    END
  END;
  WriteString ("ggT =");        WriteCard (x, 6);               WriteLn;
  WriteString ("kgV =");        WriteCard ((u+v) DIV 2, 6);     WriteLn;
  WriteString ("u =");          WriteCard (u, 6);               WriteLn;
  WriteString ("v =");          WriteCard (v , 6);              WriteLn
END ggTkgV.

jan@Beryllium:~/modula/Wirth/PIM$ ggtkgv
x = 12
y = 20
ggT =     4
kgV =    60
u =    44
v =    76
jan@Beryllium:~/modula/Wirth/PIM$ ggtkgv
x = 123
y = 255
ggT =     3
kgV = 10455
u = 13773
v =  7137

You may also check:How to resolve the algorithm Higher-order functions step by step in the PicoLisp programming language
You may also check:How to resolve the algorithm Pseudo-random numbers/Middle-square method step by step in the Wren programming language
You may also check:How to resolve the algorithm Angle difference between two bearings step by step in the C# programming language
You may also check:How to resolve the algorithm Count the coins step by step in the BBC BASIC programming language
You may also check:How to resolve the algorithm Show ASCII table step by step in the 6502 Assembly programming language