# Show Euclid's algorithm by using Basic or Pascal

Anyone have and idea please lend me a hand---->>
Explain and show using Basic or Pascal notation how Euclis's algorithm could be presented using a programming language. The algorithm must be shown, and explain by performing a program walkthrough for the algorithm.
thank you!!
###### Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Commented:
gcd(m,n):
if n = 0
else
find gcd(n, m mod n)
0
Commented:
ozo's correct, just make sure n<m
here's an implementation in basic:

if (m<n) then t=m:m=n:n=t
while n<>0
t=n:n=m mod n:m=t
wend
'm contains gcd

?walkthrough?:
if u understand euclid's algo it shouldn't be a prob...

(4, 3) -> (3, 1) -> (1, 0) so 1...
0
Commented:
haha... anyway i'm amused that i have seen abt 5 gcd qns all over since wed i think...
0
Commented:
Suppose the two numbers are a1 and a2 and that a2<=a1. Then
a1 = q1*a2 + a3
(q1 may be just 1!)
If a3 is zero the a2 divides a1 and is theefore the gcd.

If a3 is non-zero then we would like to find a divisor of a3 and a2, say a4, such that a3=k1*a4 and a2=q2*a4 so that
a1 = q1*(q2*a4) + (k1*a4)
So the process of finding a divisor for a2 and a3 is the same process as finding the divisor for a1 and a2. Hence the recurrence relationship :-

gcd(a1,a2)=if a1 mod a2 =0 then a2 else gcd(a2,a1 mod a2) fi;

If you eliminate the mod function (occurs twice) by adding in another call level you get :-
gcd(a1,a2)=if a2=0 then a1 else a1 mod a2 fi;
0
Commented:
In Euclid's 7th book in the Elements series (written about 300BC), he gives an algorithm to calculate the
highest common factor (largest common divisor) of two numbers x and y where (x < y). This can be stated as:

1.Divide y by x with remainder r.
2.Replace y by x, and x with r.
3.Repeat step 1 until r is zero.

When this algorithm terminates, y is the highest common factor.

As an example, consider trying to find the highest common factor of 34,017 and 16,966. Euclid's algorithm
works as follows:

34,017/16,966 produces a remainder 85
16,966/85 produces a remainder 51
85/51 produces a remainder 34
51/34 produces a remainder 17
34/17 produces a remainder 0

and the highest common factor of 34,017 and 16,966 is 17.
0
Commented:
The Euclidean algorithm is implemented by the following short JavaScript program:

// Assume that a>b
function gcd(a,b)
{
// Loop until a or b is zero
while (true)
{
a = a % b;
if(a == 0) {return b;};
b = b % a;
if(b == 0) {return a;};
};
return b;
}

If you think carefully about the Euclidean algorithm you will see that at each step both numbers are formed by
adding some multiples of the original numbers. Thus there are some numbers, a and b, such that
gcd(n,m)=a*n+b*m. The Extended Euclidean algorithm can recover not only gcd(n,m), but also these numbers
a and b.
0
Commented:
Hi

If you are familiar with Delphi, I here have a form, with 3 editcompnents, and one button. The formula is gcd(a,b).
Here : a= edit1.text, b=edit2.text and edit3.text is the result(gcd(a,b)) after pressing the button.

The procedure below is for the button:

Procedure findGCD;
var
a,b,c,d,e,f : longint;
gcd : string;
numbers : array[1..20] of word;

begin
a:=strtoint(edit1.text);
b:=strtoint(edit2.text);
{the clue is now to find gcd(a,b)}

f:=0;
repeat
c:=trunc(a/b);
d:=a-(c*b);
inc(f);
numbers[f]:=d;
a:=c;
until a=0;
for a:=f downto 1 do
edit3.text:=edit3.text+inttostr  (numbers[a]);
{ex : edit3.text gives 134100 if a=12564
and b=6(12564 in base 6 is 134100)}

end;

Regards Batalf
0

Experts Exchange Solution brought to you by

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Commented:
Or maybe this is more Correct(if I understood the algorithm wrong) :

The setup for the form is like I wrote above.

procedure TForm1.Button1Click(Sender: TObject);
var
a,b,c,d,e : longint;
gcb : longint;
begin
a:=strtoint(edit1.text);
b:=strtoint(edit2.text);
repeat
c:=trunc(a/b);
d:=a-(c*b);
if b<>0 then gcb:=b;
a:=gcb;
b:=d;
until b=0;

edit3.text:=inttostr(gcb);
end;

I used this website when I worked out this function :

I have tried it in Delphi my self, and its working.(ex : gcb(37170,12564) give me the value 18 as result)

Regards
Batalf
0
Commented:
Tried my solution ?
0
Commented:
Hi ckchew666

Have you tried the answer I proposed above?

Regards
Batalf
0
Commented:
Hi ckchew666

If you don't like my answer in Delphi,
maybe this one would help more(pure Pascal):

Program Euclid   ;
USES Crt;
var
a,b,c,d,e : longint;
gcb : longint;
value1, value2 : string[10];

begin

repeat
c:=trunc(a/b);
d:=a-(c*b);
if b<>0 then gcb:=b;
a:=gcb;
b:=d;
until b=0;
writeln('GCB = ',gcb);
end.

0
Commented:
Sorry, errors in my code above
This one is correct :

Program Euclid   ;
USES Crt;
var
a,b,c,d,e : longint;
gcb : longint;

begin

repeat
c:=trunc(a/b);
d:=a-(c*b);
if b<>0 then gcb:=b;
a:=gcb;
b:=d;
until b=0;
writeln('GCB = ',gcb);
end.

Best regards
Batalf
0
Commented:
??????????????????
0
Commented:
??
0
###### It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Pascal

From novice to tech pro — start learning today.