The CompTIA Cloud+ Basic training course will teach you about cloud concepts and models, data storage, networking, and network infrastructure.

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!!

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!!

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

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.

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...

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;

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.

// 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.

Could this procedure help you(PASCAL/DELPHI)?

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+int

{ex : edit3.text gives 134100 if a=12564

and b=6(12564 in base 6 is 134100)}

end;

Regards Batalf

Experts Exchange Solution brought to you by

Your issues matter to us.

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

Start your 7-day free trialThe setup for the form is like I wrote above.

procedure TForm1.Button1Click(Sender

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 :

http://www.unc.edu/~rowlett/Math81/spreadsheets/Euclid.html

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

Regards

Batalf

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

readln(value1);

readln(value2);

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.

This one is correct :

Program Euclid ;

USES Crt;

var

a,b,c,d,e : longint;

gcb : longint;

begin

readln(a);

readln(b);

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);

readkey;

end.

Best regards

Batalf

Pascal

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with Premium.
Start your 7-day free trial.

if n = 0

answer is m

else

find gcd(n, m mod n)